先日競技プログラミングを始めたことを記事に書いたが、今回は１ヶ月ほど経ったので経過を報告したいと思う。正直"競プロ界隈"の方々からするとカスみたいな現状ではありますが、とある初心者が進んだ道のりということで記録しておこうと思う。ここでいう競技プログラミングはAtCoderのことでほかの競技プログラミングには参加していません。
Contents
現状
5,6回ABCに参加してみましたがA問題、B問題は時間内に基本的に解けてはいるがC問題は1回くらいしか時間内にはできなかった。茶色になるまではまだまだ道のりは長そうだと感じている。一応まだコンテスト参加回数が少ないから低めに出てるよと表示されているが自分の手応え的には適切なレーティングにすでになっていそうだ。正直悲しくなるレーティングだから、もっと頑張ろうと思う。
1か月やってみた所感
解き方わかるけど書けない
「解き方わかるけど」というのは正確に言うと「やりたい手順は頭にあるけど」という意味かな。最善かどうかは別として自分のやりたい手順、ロジックを実装することができない。というか遅い。時間が気になって焦る->時間切れというパターンが多い。これに関しては慣れも必要かなと思っているので過去問で練習を続けていこうと思っている。
上記の一例として、先日行われたABC197のD問題。
頭の中では、「2点間の中心周りに回転させればよさそう。Common Lispは複素数使えるはずだから複素数平面上でやればいいかな。」と思ったのだが、そもそも複素数の作り方から調べないとわからなかった。作ってしまえば複素数の四則演算でできるのに。さらに言えば実部、虚部の取り出し方もわからないという状態だったのでやりたいこととCommon Lispでの実装能力がまったくマッチしていなかった。ただこれを機にcomplex、realpart、imagpartを覚えた。
さらに言うと結果の表示の仕方も少し戸惑った。double-floatをsingle-floatにして表示する方法とか。この点はもっときちんと理解しておく必要がありそうだ。
そもそも解き方がわからない
上でやりたい手順があるのにうまく実装できないことを書いたが、そもそもどうやって解くんだこれは？という問題も多い。そしてそういうのは解説を見てみると典型アルゴリズムだったりする。高校数学で習ったこととかはなんとか思い出せるけれど、いわゆる典型アルゴリズムは自分の今までの経験では触れることがあまりなかったのでなかなか厳しい。
- 全探索
効率の悪い初心者全探索なら組むことはできるが、C問題くらいからTLEになってしまう。 - グラフ理論関連(ダイクストラ法とかXX優先探索とか)
へぇー、そういうものがあるんですね - 動的計画法
うん。名前は知ってるよ。 - 諸々適切なデータ構造
リストばかり使いたくなってしまう初心者病罹患中 - 数学知識
このあたりのことは今後意識して学習していったほうがいいか気がする。
楽しいよ
現状のランクはしょぼいままであまり成長を感じられていないが、問題を解こうとするモチベーションはある。それはつまり楽しめているということではないかと思う。
まとめ
- 灰色脱出はまだまだ先になりそう
- 考えを実装に落とす練習を積み重ねていきたい
- 典型的なアルゴリズム、データ構造を学びたい
- 改めて競技プログラミング楽しいよ
コメント