ガナリヤの競プロ帳

ガナリヤのプログラミング記録

AtCoderで青色になるまでにやったこと

f:id:ganariya:20190527140227p:plain

前回のAtCoderでついに,念願の青色になることができました!!
本来は,今年中に青色に行ければいいなと思っていたので,非常に嬉しかったです.

競技プログラミングを初めて約一年半,青色になるまでに自分のしてきたことをまとめて,振り返ってみようと思います.


出会い

競技プログラミングの出会いは,三年生の初め頃でした.

ただ,実は競技プログラミングというか,AtCoderやAOJは二年生の8月ころに始めていました.
しかし,その頃は「コンテスト」という概念を知らず,リアルタイム性もなく,ただただ過去問を解いていたためすぐに飽きてしまいました.

その後,三年生になって,AtCoderというサイトにコンテストがあると知り,それに出てみたところ非常に楽しく,それからの生活はすべて競技プログラミングを中心として回るようになりました.


始めての挫折

三年生(というか二年生の末)から,積極的に始め,この頃が毎回レートが上がっていて楽しい時間だったと思います.

というのも,これまでもゲームプログラミングや,機械学習,Web系などいろいろとやっていたため,「計算量」「アルゴリズム」が関係しない,実装問題は解くことができていたからです.

しかし,そんなに事がうまくいくはずもなく,3月ごろにいわゆる茶色と緑色の壁,点数でいうと200と300の壁に取り込まれることになります.


挫折(2回目)

300点の過去問を埋め始め,とき終わった頃にはいわゆる緑色の上位辺りになりました.

しかし,今度はいわゆる緑色と水色の壁,点数では300と400の壁に取り込まれることになります.

個人的にはこの頃が一番辛く,何をやってもレートが伸びない,なんかしょうもないミスをしてヘラっていました.


なんとか水色に

その後,なんとか400を初めてコンテスト中に通し,水色の仲間入りを果たすことができました.

時期的には,ICPCの一週間ぐらい前なので,ウキウキでICPCに望んだのを覚えています.

その後緑色に一度着弾しながら,そこからは着実に水色を少しずつ伸ばすことができました.


水色の停滞

何回目の停滞でしょうか…

水色の1400あたりで三年生の年末,ずっと停滞していました. これはおそらく,400を安定して通せない,500は基本的に通せないのが原因だったと思います.

ここらへんで,Codeforcesに手を出し始め,コンテストの復習が追いつかなくなってきた時期に突入します.

それでも頑張って毎日やってたので,着実に実力がついていたのだと思います.


そして伝説へ...(は?)

今年の3月ごろから非常に調子が良くなり,青パフォや橙パフォがでるようになりました.
原因としては,「400の過去問を埋めまくる」「こどふぉに毎回出て,実装に強くなる」「基本テクを網羅する」「朝ゴリに出る」などがあると思います.

ここ二週間,毎回良いパフォで青色になることができるはずだったのですが,Unratedなので,苦汁を飲まされていました.

なんとか今回のABC127/128で,うまく立ち回ることができ,ついに念願の青色のなることができました〜〜


青色になるには

青色になるために学んだことは

  • しゃくとり法
  • グラフアルゴリズム
  • 動的計画法
  • 二分探索
  • ビット演算
  • TSP
  • セグメント木(遅延評価)
  • BIT木(セグメントしか使ってないのでもう覚えてない)

ぐらいな気がします.

ただ,これは,いわゆるアルゴリズムの名前があるものに関しての知識なので, 例えば

  • 最大値・最小値の変換
  • 逆から考える
  • 包除原理
  • 実は全探索

など,細かい意識やテクニックは,問題をとき続けるしかない気がします.


青色を持続するには

おそらく僕は青色をキープするのがおそらく難しいです.
というのも自分は100~400の早解きはできますが,500は4割,600は2割ほどしか解けないからです. というのも,500, 600はほとんど過去問も自力で通せていないので・・・

ここらへんから自頭やアルゴリズム,実装能力など一問一問難しいのを解いて理解・定着させることが必要なのだなと思います.

また,こどふぉももっと解いて,いわゆる典型や実装がうまくならないといけないと思いました.


目標

青色を今年は常にキープして,いずれは黄色になりたいなぁ・・・(厳しい)

そのためにも早く院試を終えて,きっちりと500, 600を安定して早く通せるようになりたいです!

ganariyaでした〜〜〜

2019年4月なので

4年生が始まるので

四年生が始まるので、一応自分の区切りとして、何かしらまとめようと思います。


競技プログラミングについて

最近ちょっと、停滞というかレートがあまり伸びなかったり 具体的なテクニックをなにか学んだかというとあんまりない気がしています。 ローリングハッシュを多少学んだくらいであり、それ以外はあまりないですね・・・
それよりかはなにか多少の解き方とか、色々なバックグラウンド知識がついた感じがします。
もっと精進・強くなるためにはひたすら解いたことのない難しいやつを解いて、実装やアイディアを学ぶしかなさそうです。  

AtCoder

f:id:ganariya:20190402180022p:plain

以上をみて分かるようにそんなにレートが伸びていないですね・・・
水色になってからRatedコンテストが少なかったり、コンテストがあったとしてもいわゆる現在のレート通りの実力がそのまま出ています。

これを踏まえると自分には

  • 400を安定して通す力
  • 500をちゃんと考察できる力
  • 600を1/10でも通せる力

が必要に感じます。

考察力が特に足りず、ある解法に固執すると永遠に考えてしまったり、そもそも頭が硬すぎてお話にならなかったりするのでなんとかしたいですね・・・

考察力をつけれる・数式を立てれるようになりたいです。

Codeforces

f:id:ganariya:20190402200957p:plain

Codeforcesは一時期めちゃくそに冷えて、ものすごくテンションが下がりましたが
そこからはなんとか持ち直せた感じですね。

AtCoderよりもシンプルに実装する、みたいな問題が多いので、結構解きやすいんだと思います。

ただ、それでも解けない問題はさっぱり解けないので、そういう解けない問題をきっちり解いていこうと思います。

ICPC

現在、大体の200~300が埋まった感じです。

残り三ヶ月なので、一日1問は通すとして、当日までに300~550までを各問題二回以上通すようにしたいです。
なので、詰まったら解答をなんども移して、自分のものにしたいと思います。

一日1問は基本的にマストでやりたいと思います。

JOI

JOIも最近触り始めましたが、非常に教育的なシンプルな問題が多くていいなぁと思いました(メモリ使用量が非常に厳しいのがアですが)

ICPC当日までに、5~9は埋めたいなと思います。


学校面について

復習

線形代数離散数学の記憶がガバガバなので、もっかい講義に出ようかなと思います。

やっぱ色々と線形代数機械学習でも競プロでも使うのできっちり学び直したいです。
微積は知らん

あと、線形計画法の意味をきちんと理解したいお気持ちがあるので何かしらもっかい勉強したいです。

研究

グラフ理論とネットワーク系の研究がしたいので、それに関する知識をもっとつけていきたいですね・・・

いわゆる最近、全体最適アルゴリズムに興味があるので・・・
ただ、それをするには自分の頭が足りていないことが十分にわかっているのできっちりと勉強しないといけなそうです。

ただ、毎日パソコンに向かって研究できるので非常に楽しそうだな〜とは思います。 色々と知識をつけていきたいです。


生活面について

早寝早起き

早寝は無理なんだよなぁ(Codeforcesがあるので)

ただ、きちんと早起きをして、まあ、こどふぉがあった後の朝ゴリラは無理ですが それ以外はきちんと朝ゴリラをしたいです。

そして、二度寝を一切やめます!!!!!

朝も夜も辞めて、寝るならば机で短い睡眠のみにしようと思います。

コミュニケーション

色々な人と話せるようになりたいですね
誰が好きとか誰が嫌いとかはないので(昔の孤独から多分そういうのができなくなったんだなぁと)、緊張しないで話せるようにしたいですね・・・ う〜〜んこの


夏休みまでの目標

競技プログラミング

AtCoderでは青色になりたいです。
これはいわゆる願望であり、おそらく無理なのですが(Ratedコンテストの回数)、それでも青色になることに意義があるし、自分の目標であるので・・・

こどふぉも紫色になりたいです。
AtCoderよりもレート変動が激しく、うまく行けばワンちゃんあるので、毎回コンテストに必ず出るようにしたいです。

まずは青色をキープしろ〜〜〜

また、ICPCではA〜Eを通して、アジアに安心して行けるような、そういうのをしたいですね・・・かなり難しいですが、目指さないと出来ないので、目指していきたいと思います。

大学面

研究をきっちりやりたいです。
TwitterYouTubeはちゃんとアプリ入れて使えないようにして集中してやりたいですね(苦手なので)

ウンチコード書かないように、ちゃんとバックグラウンドを調べてコピペする人間にならないようにしたいです。

授業は、線形代数、数理計画法、離散数学代数学を取って自分の知識を増やしていこうと思います。

生活面

二度寝しない、以上


結局毎日なにすんねん

  • ニコ動・YouTubeは朝30, 夜30のみにす
  • 学校でTwitterはしない、集中する
  • 研究ちゃんとする
  • 授業は線形代数離散数学、数理計画法、代数学を取る
  • 一日一問ICPC解く
  • コンテストは毎回出て、ちゃんと復習する
  • PythonとNimを使いこなせるようにする
  • JOIもAtCoderの600までも埋める(多分埋めないと強くならない)
  • 難しい問題を解く

がんばろ〜〜〜〜(れるかな・・・?)

2018年の振り返りと来年の目標について

おはガナ・・・・・・!
ガナリヤです。

明日で今年2018年が終わり、新しい年2018年を迎えようとしています。
このままだと中途半端な新年になりそうなので、2018年になにをしてきたのか、そして来年なにを頑張りたいのか振り返っていこうと思います・・・!

ちなみに、やらないといけない課題が全然終わってない・・・


今年の振り返り

大学編

2018年は特に大学生活は何も変わってない一年だったなって思います。

なんか知らないうちに二年生から三年生になり、そしてそのまま四年次を来年迎えることになりそうです。 時間の流れは怖い・・・。

嬉しかったことは、二年生の大学の成績が全部Sだったことぐらいでしょうか(なお国立底辺大学の情弱学部の模様)

仲の良い人とばかり、交流していたのでちょっとこれは反省しないといけないかなって感じがします。
知らない人とか、少し話したことのある人と楽しく話せるようなコミュニケーション能力を付けないといけないです・・・ひえぇ・・・。

来年に四年次で研究が始まり、おそらく三年間研究をするので、もっと精進しないといけませんね・・・
あと、微分積分とか、線形代数フーリエとか全く覚えていないので復習しないと人生破滅しそうな気がします・・・

バイト編

2018年の最初三ヶ月位は、とある塾で個別指導してました。
ただ、正直、コミュニケーションとるのがしんどかったし、時間に対してお給料は良くないし、何よりこんなのでお金をとっていいのか、集団授業のほうが絶対に生徒は伸びると思い、あまり気持ちよく仕事できていませんでした。

その後、とある機会からIT系の会社二社でバイトができるようになりました。
一社の方は、ウェブ系の会社だったのですが、関数一個に800行ぐらいがあったのと、アルバイトを使い捨てみたいにしか思っていないような感じだったので、自分が成長できるとは感じることが出来ず、三ヶ月ほどでやめました。
もう一社の方では現在も楽しく働いており、こういうフレックスで働いて、アルバイトでも成長できる、社員も成長できる、そういう企業で働きたいなと思っています。
少しでも力になれるように、頑張りたいです。

サークル編

ゲームプログラミングサークルに所属しているのですが、今年はこれまで行っていた回数よりも行った回数が激減したみたいな感じでした・・・
行っても、ノートパソコンなのですることがないのと、あまり集中できる環境じゃなかったり、サークル活動後にあまり遊ばなくなった、さらにバイトも重なりなかなか時間が会わなくなった、のようにいろいろなことが重なってあんまり行かなくなりました・・・

でもゲームプログラミングサークルはすごい好きだし、自分のプログラミングの基礎は完全にこのサークルで身についたので、今でも行ける時は行きたいです。
来年は時間見つけて行きたいですね・・・(後方老害面)

開発編

今年はいろいろなことに手を出していた、そんな時期だったなっておもいます。

去年(2016, 2017)は基本的にSiv3DやUnityなどでゲーム制作ばっかりやってました。ただ、最近思うのは自分そんなにゲーム作るの好きじゃないなってことですね(何をいまさら)

そんな中で、ゲーム作るのあんまり楽しくないならなにをやろうかな〜〜〜〜ってなって、

まあ、ウェブ系っしょwwwww

ってウェブ系の勉強をし始めて地獄を見たのを覚えています。

結局、勉強を1~3月ぐらいに行って

らへんの最低限の知識は付き、リファレンスを読みながらなら何かしら作れるみたいな状況にはなったとは思います。
ただし、CSS、テメーはダメだ。(デザインセンスがガバ)

その後、NodeJSなどで、Discordのチャットボットとか、PHPでお手軽掲示板とか作ってましたね・・・

また、これらのウェブ系の言語のおかげで、ウェブ系のIT会社でアルバイトを始められたのでそこは良いかなって思いました。(嫌になってやめましたが・・・)

その後、10月らへんに競技プログラミングChrome拡張を作成し、ゲーム以外で初めていろいろな人に使ってもらえるようなツールを作成したことを覚えています。
一番、これまでの中で多くの人に使ってもらえたので、非常にうれしかったです。
ただ、AtCoderAPIが変わったり、Codeforcesでエラーが出たりと何故か今動作がうまくしていないので、時間を見つけて修正して対応していきたいです。

また、今日もう一個拡張を作ったので後で記事にしようかなって思います。

      
そういえば、去年の後半から今年のはじめにかけて、機械学習ディープラーニングについて学んで、いろいろと作ってました。ただ、あまり面白いとは感じず、最近は何もやってないですね・・・
うまく、研究に絡められればよいのですが・・・

競技プログラミング

今年の僕の生活で、一番変わったのはこの競技プログラミングだなって思っています。

競技プログラミング自体は、2017年の中頃には知っていたのですが、一回ちょろってやって、面白さに気付けずすぐに辞めてました。

しかし、今年の1月からもう一回競技プログラミング始めっか!ってなって、AtCoderを再びやり始めましたね。

f:id:ganariya:20181230220648p:plain

画像見ていただければ分かると思うんですけど、完全に努力型のタイプです。
やり始めた今年の始めはA, Bしか解けず、Cが20%しか解けないみたいな感じでした。
もともと頭が良い方ではないので・・・(悲しい・・・)

そこから競技プログラミングに熱中し、4月頃からは競技プログラミングが主体の毎日になりました。
どうして、こんなにハマったのかはわかりませんがおそらく

  • ゲーム制作に飽きて、何かやれることがほしかった
  • アニメに飽きて、何かやれることがほしかった
  • アルゴリズムってものに興味が出た
  • レーティング上げて、俺Tueeeeeeeeしたかった

のどれかかな〜〜〜って思います。

4月ごろは、たまに空いた時間でやるかな〜〜って感じでしたが、6月頃はICPC予選が近づいたからか、本当に毎日競技プログラミングばっかやって何も開発してなかったみたいな感じでした。つらたん。

7月には、初ICPCの予選に出ました。
同じサークルかつアルバイトの二人を誘って、参加しました。
D問題が通せず、悔しい結果でした・・・(今でも思い出すと辛い)
もっともっと強くなりたい、そう思った一日でした。

夏休みは基本的に毎日競技プログラミングとアルバイトをして、それ以外大学生っぽいことをしていない気がします。
アプリ開発とか・・・は、一切やっていないのかな・・・? ただ、インターンには行ったので良しとします。

そして、8月頃、初めて水色になりました! すごい嬉しかった!!!
なお、すぐ着水した模様。
その後、現在までAtCoderを楽しんでいたと思います。

ただ、まだまだ埋めてない問題が多いので、高難易度問題もしっかり考察していきたい・・・

またCodeforcesも8月頃はじめました。
AtCoder以外にもRatedコンテスト出たいなってなって、とりあえずTwitterに多かったこどふぉに出ました。
初期の頃は、英語さっぱりわからんってなってましたが、現在はなんとなく雰囲気で通せるようになりました。成長。

f:id:ganariya:20181230223953p:plain

最近冷えぎみなので、暖かいところにいきたいです・・・


来年の目標

生活編

自分の私生活を見直す!!! 来年から!今日から!今から!!

  1. 朝同じ時間に起きる!
  2. 二度寝しない!机でする!
  3. 朝・昼・夜のご飯中のみ動画見る!!!
  4. ポモドーロできっちりと時間管理!

以上を絶対に守りたい! きっちりやるぞ〜〜〜〜〜

あとは、時間を守って、自分のことをきっちりやっていきたい。
やるぞ!!!!やれ!!!!

あと毎日ゴリラ体操と、自分のやつやるぞ!!!!

開発編

まずは手を動かすことを中心にいろいろなものを作っていきたい!!!
文法よりかは、誰かの役に立つ、お金になる、他の人に自慢できる! そういうプロダクトをちゃんと作るぞ〜〜〜〜〜〜
あと作り込むぞ〜〜〜〜〜〜!!!!(途中で投げ出しがちなので・・・)

macアプリ開発もしたい!(どうやるかわからんが・・・)

競プロ編

現在のレーティングは
AtCoderは水色
Codeforcesは青色

来年中にAtCoder青色、Codeforces紫になることを目指す!!
AtCoderだと、500を安定して解けるように
Codeforcesだと、1000人が解けた問題を解けるようになり、できるだけ早く解けるようにしたい

毎回コンテストに出て、解説Scrapboxと、解説放送をする。

あと、難しい問題でも、最後まで一時間は考える。考察力を付けてこう。

来年もICPC出て、自分の実力でICPC本戦に出る!
あと、一回はオンサイトに出て、パーカーとかTシャツゲットしたい。

毎日精進していこうと思います。

私生活編

コミュニケーションとってこう!!
LINE返そう、携帯買おう!

動画編

動画見る量減らせ


最後に

今年は多少は、アプリ開発や競プロなど、文法などよりは実際に手を動かすようになりました。
来年も手を動かしながら、人の役になるものを作りたいです。
また、きっちり競プロしてこうな

真面目に書いてしまったので、来年は面白く書けるようになりたい・・・

せっかくだからSTL使おうという話

C++は競技プログラミングの役に立つ Advent Calendar 2018 の記事になります、ガナリヤです。
12月後半だと思ってたのですが、16だったんですね!!!すいませんでした!遅れました!

今回の内容はシンプルで、配列をやめないかというお話です🍆


配列 vs STL

STLの勝ち。

理由は簡単。 配列は扱いが面倒(初期化が楽ぐらい)。

STLは、サイズも取れる、イテレータも使える、速度もそこまで遅くない 初期化ぐらいmain文ですればよいのだ。


圧倒的にSTL
多くは語らない。配列はやめよう(宗教戦争)

非公式解説放送について

まえがき

投稿おくれました… もうしわけないです!

Adventerということで、今年から始めた「非公式解説放送」について書こうと思います~~
ICPCアジア参加記とどちらについて書くか悩みましたが、他の方のもありそうなので、個人的に推していきたい非公式解説放送について書いていこうと思います。


非公式解説放送とは?

某、ガナリヤは、今年の夏頃から「非公式解説放送」というのをはじめました。
AtCoderCodeforcesなど、ジャンルをしぼらず自分の参加したコンテストに関して、これからも時間がある限り動画を上げていきたいと思っています。
(最近上げていないじゃないかという声は申し訳ないがNG)


Codeforces 515 Div3 非公式解説放送

例えば、以上のような動画ですね
今はなかなか説明が下手くそなので、時間がかかっていますが、もっとシンプルに簡潔に説明できるようにしたいですね…

なんで非公式放送なの?

非公式解説放送を自分が始めた原因が、いろいろな方の競プロブログをみて、なかなか自分が理解できなかったというのがあったからです。

どうしても、自分は物分りが非常に悪いほうなので、文字媒体のみのブログではなかなかすんなりと入ってこず、いくら読んでもさっぱりわからないみたいなときが多かったです。

ただ、AtCoderの公式解説放送などでは、ある程度理解することができ、視覚情報や音声情報、動作や話し方で伝わる情報は一気に増えるのだなと思いました。

そういったわけで、ガナリヤはブログから解説放送にシフトしました。

最後に

ブログでの解説も非常にいいのですが(図やLaTeXなどを書いているうちに理解が深まり度が高い)、 解説放送だと、より多くの情報が一度に入ってきてわかりやすいような気もします!

できるだけこれからも解説放送をやっていきたいとおもいます!ぜひ皆さんもご検討願えれば!

AtCoderBook(Chrome拡張)

はじめに

どうも。
ガナリヤです。
ここ最近は、競プロずくめの毎日で全然開発できてないです・・・
もっと色々な開発もしたいのですが・・・

大学の授業で忙しいんですよね・・・(元も子もない)


AtCoderBook

AtCoderBook(https://chrome.google.com/webstore/detail/atcoderbook/lcojnofidkanlkoaagdbjkdnelbnlnng?hl=ja)は、ガナリヤが作成した、

  • AtCoder
  • Codeforces
  • AOJ(まだ対応してない)
  • CSAcademy(まだ対応してない)
  • yukicoder(まだ対応してない)

の問題を、コンテストサイトで、ブックして、復習に役立てよう!という拡張機能です。

こういうのがほしいなと思ったきっかけとしては、AtCoderだけでなく、こどふぉにも出始め、過去問もどんどん解いていた結果、どの問題を復習して、どの問題がやりっぱなしなのかわからなくなったからですね・・・

それで、こういうAtCoderのサイト自体で、ボタンをjQueryで作成して、それをユーザページが自分だけの復習ページを表示できればなと考えてました。


AtCoderBookの機能

AtCoderBookの機能は今の所

  • 問題のブックマーク
  • 問題の検索
  • お気に入りボタン

の機能があり、これから実装予定の機能(はよ実装しろ)が

  • 他サイト(AOJ, CSA, yuki)への対応
  • ブックマークのJSON保存
  • 解いた問題などとの同期

があります。
ICPCの対策で忙しくてなかなか作れていないので早く拡張していきたいですね・・・


構成

中身は

をふんだんにガバガバに使用してます。
正直今見たら何やってんだ?っていうコードなので、触りたくないお気持ちがお強い。 開発環境は

  • WebStorm
  • Node.js
  • Webpack + babel

やっぱり、フロントエンドでは、実際に開発している時間より、パッケージがインストールできないと嘆いている時間のほうが長い、はっきり分かんだね。


最後に

もうフロントエンド開発はこりごりなんじゃ〜〜

AtCoder Beginner Contest 097 ガナリヤ

AtCoder Beginner Contest097

こんばんえるえる〜。 ガナリヤなのじゃ・・・!

前回のAtCoder097のABCコンテストは、ABCD全部解けて非常に嬉しかったのじゃ・・・

ただ、C問題、D問題はよくわかんないけど愚直に実装したらなんとかなったみたいなところがあったのでまとめていこうとおもうのじゃ・・・。

後、三回もWA出してしまったので、次回はもうちょっとゆっくりとこうと思うのじゃ!じっくり三分プラスで考えれば防げたミスなのじゃ・・・

A問題  Colorful Transceivers

問題文 数直線上にいるAさんとBさんとCさんがトランシーバーで会話をしようとしています。 Aさんは a [m] 地点、Bさんは b [m] 地点、Cさんは c [m] 地点にいます。 二人の人間は、距離が d [m] 以内のとき直接会話が出来ます。 AさんとCさんが直接的、あるいは間接的に会話ができるか判定してください。 ただしAさんとCさんが間接的に会話ができるとは、AさんとBさんが直接会話でき、かつBさんとCさんが直接会話できることを指します。

これはもう問題文読んでなかったの・・・ 入出力サンプル見てこんな感じかな?ってやってたのじゃ・・・

AさんBさんCさんはそれぞれ一直線上にいて、AとCが会話できればオッケーなのじゃ・・・ AさんとCさんが直接d[m]以内なら当たり前にOKじゃし、AさんとBさん、BさんとCさんがそれぞれd[m]以内の場合もOKじゃな・・・

B問題 Exponential

問題文 正整数 X が与えられます。 X 以下の最大のべき乗数を求めてください。 ただし、べき乗数とは、ある 1 以上の整数 b と 2 以上の整数 p を使って b p とかける整数のことを指すこととします。

べき定数とはbpと表せるものであり、たとえば32とか、28のことなのじゃ・・・ X以下で最大のべき乗数を出せばいいわけじゃな・・・

以下実装じゃ・・・

int main() {

    int X;
    cin >> X;

    VB goods(X+1, false);
    goods[1] = true;

    for(int b=2;b<=1000;b++){
        int value = b*b;
        for(int p = 2;;p++){
            if(value>X){
                break;
            }else{
                goods[value] = true;
                value *= b;
            }
        }
    }

    RREP(i, X+1){
        if(goods[i]){
            OUT_L(i);
            return 0;
        }
    }

    return 0;
}

正直こういう計算の小難しいのは大苦手なのじゃ〜〜

C問題 K-th Substring

問題文 文字列 s が与えられます。 s の異なる substring のうち、辞書順で K 番目に小さいものを出力してください。 ただし、 s の substring とは、 s の空でない連続した部分を取り出してできる文字列とします。 例えば、 s = ababc とすると、 a, bab, ababc は s の substring ですが、 ac, z, 空文字列 は s の substring ではありません。 また、substring が異なるとは、文字列として異なることを指します。

またじゃよ!また! ガナリヤは辞書式が苦手なのじゃ〜(よくわかってない) 辞書式の理解にコンテストの時間を割いてしまったのじゃ・・・

辞書式とは?

辞書式とは、日本の国語辞典とかで、単語が現れる順番のことじゃな・・・
以下のルールによって掲載されておる。

  1. X, Yの文字列を左から見ていったとき、異なる文字が出た時は小さい文字のほうが小さい文字列である。
  2. X, Yの文字列を左から見ていったとき、片方がなくなってしまった場合は、なくなったほうが小さい。

よくわからん!!

  1. X=abcd Y=abceとする。左から見ていって、四番目で初めて異なる文字が出てきてdのほうが小さいため、Xのほうが小さい。

  2. X=ab Y=abcとする。左から見ていってXのほうが先に文字がなくなってしまう。よってXのほうが小さい。

具体例を交えると多少わかりやすくなるのぉ・・・


本題に入るのじゃ・・・

文字列sの異なるsubstringのうち小さい方からK番目を出力する必要があるのじゃ・・・

ただし、Kは1<=K<=5とかなり小さく設定されているところがポイントじゃな・・・

substringを全部試そうとすると

  1. 部分文字列の左側を決めるのにN
  2. 部分文字列の右側を決めるのにN
  3. 小さい順である必要があるため、NlogN

であるためO(N3 logN)らしいのじゃ・・・?

そのため、何か工夫をしないといけないのじゃ・・・

小さい順で1~5番目のどれかを出力するというところがポイントで、部分文字列の長さが6以上を考える必要はないのじゃ!

abcdefを考えるのじゃ・・・。仮にabcdefが1~5番目に入ろうとすると、a,ab,abc,abcd,abcdeの5つがすでに存在しているのじゃ・・・

やっぱC,D問題は気づきが勝負らしい気がするのじゃ・・・


int main() {

    string s;
    cin >> s;

    int K;
    cin >> K;

    set<string> PS;
    REP(i, SZ(s)){
        REP(j, 5){
            string ps = s.substr(i, j+1);
            PS.insert(ps);
        }
    }

    VS ANS_S;
    FOREACH(x, PS){
        ANS_S.push_back(x);
    }

    SORT(ANS_S);

    OUT_L(ANS_S[K-1]);

    return 0;
}

PS c++のsubstr(i, j)は文字列sのi番目からj個取り出すって意味じゃったんじゃな・・・
よく知らずに使っていたのじゃ・・・i+jがsの長さはみ出てもエラー出さないんじゃな・・・

D問題 Equals

Equals

問題文がうまく引用できないので、リンク先を見てほしいのじゃ・・・

なんか小難しいこと言っとるが簡単に言うとこうじゃな・・・

与えられたN個の整数を、指定された位置同士を何回でも交換して良いのじゃ・・・
何回か交換した後、順列Nのそれぞれの数字の位置があっている個数を増やしたいわけじゃな・・・

よくわからんな・・・具体例具体例・・・

N=6 で最初が613452とするのじゃ・・・ (1, 6), (2, 6)が交換できるとすると、(1,6)で交換して(2, 6)で交換すると、123456とすべて一致させることが出来るわけじゃな・・・

この問題はよく分からず自分で何個か具体例を書いたら、交換する二つの数がかぶったところは自由に値を変更できるということがわかったのじゃ・・・
例えば、(1, 2), (10, 20), (20, 5), (5,2)があったら、1・2・10・20・5の5つの位置にある数は自由にならびかえられるのじゃ・・・
これが成り立たなかったらバブルソートもできんわけじゃな

自由に並び替えられるとすると、同じ数字がかぶっているところは同じ性質を持つ・・・
→つまりUnionFind木で集合として扱うのかな?
と考えたのじゃ・・・

こういう考えで合ってたらしいのじゃ(細かい理屈はいっぱいあるらしい・・・)
UnionFindの実装が怪しいので後で見直しが必要じゃな・・・

// 素集合データ構造
//--------------------------------------------
struct UnionFind {
 
    // par[i]→データiの親の番号 i==par[i]ならiは木の親
    vector<int> par;
    // sizes[i]→iを根とする木に含まれる子の数
    vector<int> sizes;
 
    UnionFind(int n)
            : par(n), sizes(n, 1) {
        // すべてのノードがiに属すると初期化
        REP(i, n) {
            par[i] = i;
        }
    }
 
    // データxが属する木の根を得る
    int find(int x) {
        if (x == par[x]) {
            return x;
        }
        return par[x] = find(par[x]);
    }
 
    // 2つのデータx, yが属する木をマージする
    void unite(int x, int y) {
        // データの根ノードを得る
        x = find(x);
        y = find(y);
 
        // 同じ木ならマージしない
        if (x == y) {
            return;
        }
 
        // xの木 > yの木
        if (sizes[x] < sizes[y]) {
            swap(x, y);
        }
        // xはyの親とする
        par[y] = x;
        sizes[x] += sizes[y];
    }
 
    // x,yが同じ木ならtrue
    bool same(int x, int y) {
        return find(x) == find(y);
    }
 
    // xが含まれる木のサイズ
    int size(int x) {
        return sizes[find(x)];
    }
};
 
 
int main() {
 
    int N, M;
    cin >> N >> M;
 
    VI p(N);
    REP(i, N) {
        cin >> p[i];
    }
 
    vector<PII> xy(M);
    REP(i, M) {
        int x, y;
        cin >> x >> y;
        xy[i] = MP(x, y);
    }
 
    UnionFind uf = UnionFind(N);
    REP(i, M) {
        uf.unite(xy[i].first - 1, xy[i].second - 1);
    }
 
    int count = 0;
    REP(i, N) {
        if (p[i] == i + 1) {
            count++;
        } else {
            if (uf.same(i, p[i] - 1)) {
                count++;
            }
        }
    }
 
    OUT_L(count);
 
    return 0;
}

完走した感想

よくわかんないけど解けるっていうのが、少しずつ競技プログラミング慣れしてきた気がするのじゃ・・・
あとはどうスピードを早めるだとか、新しくアルゴリズム覚えるかとかじゃな・・・

理論の説明もできるようになりたいのじゃ・・・