ヤマカサのプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder で水色になるまでを振り返る

前提

去年の2月くらいから Java の勉強を初めて、4月から AtCoder で競プロを行うようになりました。情報科学は勉強したことはありませんが、離散数学をほんのちょびっと勉強したことはあります。数学力は普通くらいだと思います。受験のときは、センターでいうと、数1A が8割、数2B が6割の点数でしたが、今はもっと下がっているはずです。

結論

ABC の C 問題まで解こう。

レートのグラフと解いた問題数

AtCoder のレートと解いた問題に応じたポイントのグラフです。これは、AtCoder Scores の精進グラフという所で確認できます。

f:id:yamakasa3:20190216234523p:plain

また、他の競プロで解いた問題数は、Rating History で確認すると、

CodeForces: 122、AtCoder: 435、AOJ: 154、yukicoder: 348

で合計1059でした。他のサイトでも解いたものがあるんですが、主に利用しているのはこの4サイトです。

各コンテストでのパフォーマンスを AtCoder Performances で見ると、

f:id:yamakasa3:20190217000017p:plain

という感じでした。AtCoder Problems でABCの解いた割合を見ると、

f:id:yamakasa3:20190217000830p:plain

となっています。最新のコンテストの状況がまだ反映されていませんが、Cまで埋めています。

グラフを見て思うこと

2018年の7月1日にレートが839となり、水色になるのは簡単かも?と思っていました。しかし、その後は4ヶ月くらい同じレート帯をさまよっていました。このままじゃいけないと思い、2018年の10月から11月にかけて、AtCoder Beginner Contest のC問題までを埋めました。これをしたことによってレートが徐々に上がるようになりました。

AtCoder のコンテストや過去問を解いて思った事

ABC の A と B 問題について

競プロを始めてから配点が100~200の問題を解けなかったことはないです。ABCのAとBに該当する難易度で、時間をかけたり何度もトライすれば絶対に解くことができる問題だと思います。計算効率の悪いやり方でも通る可能性が非常に高いです。これらを埋めないで C 問題以降だけを埋める人もいると思いますが、僕は簡単な問題を解くことも好きなので埋めました。

また、簡単な問題でも得られる知見はあると思います。具体的に何がとは覚えていませんが、タイピング練習以上の効果はあるはずです。

C 問題について

茶色や緑色になると C 問題をいかに早く解くかがレートを上げるためのカギになると思います。C 問題まで解き終わった人たちの順位表を見るとすごい団子状態となることが多いので、早く正確に解くことが重要であるかが分かります。

コンテストで C 問題の難易度を解くためには、色々な問題を解いてアルゴリズムを学ぶ必要があります。こういう問題にはこのような解法があるというものを身に着けて、問題に臨んでいます。

C 問題から方針が立てられなかったり、解説を読んでもコードを見ても分からないということが起きました。僕はこういうときは、理解できないものは理解できないで良いと思っています。ですが、ブログの記事として残しておき、似たような問題が出れば参照できるようにしています。ブラックボックスとして受け入れることで、別の問題が解けることもあると思います。例えば、僕はグラフ系のアルゴリズムを理解していませんが、ダイクストラ法を使って問題を解くことはできます。応用性のレベルが違いますが、問題そのものと解法を知っていることで、何かの役に立てば良いという感じです。

方針は立てられたけど、実装ができないという問題は、練習を積むことで徐々にできるようになると思います。また、正解となったけど、合っていることの証明ができないといった問題は寝かせておいた方が良いのかな?と考えています。証明は向こう側がやってくれるから今は良いと思っています。もちろん、なぜこの解法が正しいのかといいった事はコンテスト終了後に再考察してはいます。

AtCoder 以外のサイトについて

yukicoder

yukicoder

今となっては AtCoder で解いた問題数の方が多いですが、競プロを始めてから勉強してしたサイトは yukicoder でした。レベル1 の問題でも手こずったり、解けなかったものもありました。プログラミングの基礎作りを行ったのは yukicoder だと思います。現在では、レベル2まで解いています。

yukicoder ではテストケースを簡単に見ることができるので、競プロを始めるなら yukicoder がオススメです。問題を解いて思った印象としては、癖のある問題がいくつかあるという感じでした。問題やコードに Fav を付けられるので、解けなかった問題や良問を管理するのに便利だと思います。僕が個人的に印象に残っている作問者さんは、nmnmnmnmnmnmnm - yukicoder の人です。初心者の僕ですら良い問題を作るなあ!と何度も関心させられました。

レベル1から埋めていくことで、プログラミング知識の抜けを減らしたり、WA を取り除く訓練になると思います。

Codeforces

https://codeforces.com/

週に2、3回コンテストが開催されます。ロシア系のサイトですが、英語でも閲覧することができます。問題ごとにタグが添付されていたり、推定された問題の難易度も見ることができます。

正直、英語があまり得意ではないので、問題文を読むのに苦労しますが、テストケースや自分の出力も見ることができるので、オススメです。

問題としては、1600点位まではなんとか解くことができる反面、800点でも良く分からないといったことが起こります。個人的には、出力される答えが複数あるという問題があるのが新鮮でした。

Aize Online Judge

AIZU ONLINE JUDGE: Programming Challenge

通称 AOJ です。日本のサイトでこの問題が螺旋本に収録されています。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

僕は、yukicoder で問題を解いていき、競プロになれてきた所で螺旋本に取り組みました。多分、去年の5月くらいから読み始めたと思います。内容が難しくて、途中でやめたり再開したりを繰り返していました。

螺旋本にはさまざまなアルゴリズムを体系的に学ぶことができます。基本的に C++ で記述されていますが、僕はそれを Java に書き直して勉強していました。全部解いてはいませんが、8割位は読んでいます。螺旋本の良い点は、問題を解くことで自分のライブラリができることです。コピペして利用することがしばしばあります。

僕はこの本でデータ構造という言葉を知りました。また、競プロの本で蟻本というものがありますが、持ってはいますがまだ解いていません。

Paiza

ITエンジニア・プログラマ向けの転職・就活・学習サービス【paiza(パイザ)】

厳密には競プロではないと思いましが、Paiza のスキルチェックもアルゴリズムの問題を解くことができます。Paiza のランクは瞬間最大で評価されるので、A 問題のうちどれか一つでも解くことができればランクが A になります。

今の僕のランクは A ですが、B から問題によっては苦戦します。S 問題は解けそうにないです。いくつかの S 問題に挑戦しましたが、ダメでした。いずれは解けるようになりたいですね。

さいごに

緑色で伸び悩むでいた僕は問題をたくさん解くことでなんとか水色になることができました。水色になるという目標は競技プログラミングを始める人にとって、やりがいがあると思います。

僕は問題に対して、解説というよりは記録や感想に近いものを書いています。色んな人がもっと解説を書いてくれたら嬉しいです。

競技プログラミングという環境は多くの人によって支えられています。コンテストの運営もそうですが、有志によるサポートや解説にも改めて感謝したいと思います。