AtCoder 水色になったよ

やっとAtCoder 水色になりました(っ¯꒳¯c)ｴｯﾍﾝ

さて、何書こうか迷ったんですが、単純にここまでの記録を振り返りと反省を書き綴ろうかなと思います。

軽く振り返る

記念すべき（？）第1回目のコンテスト（2018 年 6 月中旬ごろ）

周りの人がそこそこ競プロやっているのみて面白そうだなーと思いつつも、どこか難しそうだし、コンテストとかヤバそう…頭のいい人にとってはお遊び、とかパズルみたいな感じなのかな？と正直敬遠していました。

競プロやってた親しい友人の1人が「とりあえずまず AtCoder Beginner Contest に参加してみれば？？」とアドバイスしてくれたので、「まあ初回だし、爆死してもいいや、記念参加〜」みたいな軽いノリで初参加をキメました。ちょうど ABC100 です。キリがいいですね。

といっても、プログラミング歴の浅い僕は大学の講義で扱っていた Java と OCaml ぐらいしか書けませんでした。競プロをやっている友人何人かにオススメの言語を聞いてみると、多くの人は C++ で参加しているので C++ がいいぞ、とのことだったので、それまで一度も書いたことがなかったのですが、C++を選択しました。

初めてのコンテストの結果は 100 点と 300 点の問題を時間内に AC して終わりました。

緑レートくらいになるまで（2018 年 9 月末くらいまでの期間）

始めてから少しすると被験者バイトを紹介されました。AtCoder のレーティングが 600 ~ 1200 くらいの人が必要、ということだったのでちょうどいい目標だな、と思い緑レートくらいを目標に少しずつ勉強をしていきました。このバイトについては少々レーティングが足りなかったものの、パフォーマンスの値は十分あったこともあり、無事に採用されることになりました*1。

この時期にやっていたことといえば、

• C++ に慣れるために Aizu Online Judge ( https://onlinejudge.u-aizu.ac.jp/home )のプログラミング入門、アルゴリズムとデータ構造入門を少しずつ進めた
• とりあえずコンテストは毎週あるので参加する

ぐらいで正直言うと熱心な人と比べたら本当にゆるふわ*2にやってる感じでした。

水色になるまで

9月末、自分自身があまりにも自己流で学習を進めていてよろしくないことと、競プロが楽しくなってきたこともあり、ようやく蟻本を購入し、体系的に勉強をするようになります。企業コンテストも多く、本戦に出場している人が交流していたり、楽しそうにコンテストに参加するのを見て少しずつ憧れを抱くようになります。

さて、この時期に勉強していたことですが、とにかく基礎を固めました。 おおまかに対策した順番に並べると、

1. 純粋に全探索をする問題をまず完璧にする
2. DFSやBFS系の問題をたくさん解く
3. 貪欲法の問題を解く
4. DPのうち易しい問題や（蟻本に出てくるくらいの）典型的な問題を解く
5. 数え上げ問題や整数問題系の問題に慣れる
6. Union-Find や二分探索、累積和、素因数分解あたりの AtCoder 300~400点によく出てくるテクニックを身につける
7. 1~6 までがいくつか組み合わされた問題を解けるようにする(難易度にして400点くらい)

といった感じでしょうか。とにかく、ABC のC問題の打率を9割以上、D問題を頑張って時間内に通すことに焦点を当てていました。

反省

競プロ開始直後

A. 言語選択

競プロをしていく上で途中で言語を乗り換える、なんて人はほとんどいないと思いますし、最初に選ぶべき言語は非常に重要だと僕は思います。結論から言うと、僕は C++を選んで正解だったと思います。理由としては、

1. 解説のサンプルコードや、他の人の提出や解説を見ても C++ が圧倒的に多い
2. 実行速度が速く、問題文の制約等も C++ 基準で設定されていることが結構ある
3. ライブラリ等が充実している

ということが挙げられます。1 は独学する人も、友人と一緒に勉強していく上でもかなりメリットになると思います。 2 については、「Python だと想定解なのに TLE ギリギリでヒヤヒヤする」みたいな余計な心配等をしなくて済みます。他のコンテストだと「Python でコンテストに参加している人は、PyPy を選択してほしい」みたいな記述もあったりします。

実は自分もコードの書きやすさから Python で進めていくことも考えていました。 もちろん Java、C#、Python などを使い、かなり高いレベルに達している人もいますが、スムーズに学習を進めるためにも僕は C++ を強くおすすめします。

B. とりあえず ABC から

AtCoder Beginner Contest ほど初心者向きの問題が出題されているコンテストはおそらくないと思います*3。普段から開発とかその他もろもろでコード書きまくっている人もとりあえずABCから始めるのが良さそうです。回数もかなり頻繁に開催されています。

C. Twitter を積極的に活用しよう

始めた頃は「強い人に見下されたくないなぁ…」「あの人クソザコだ、みたいに思われたら嫌だ…」「みんな強くて怖い」と思ってしまいがちですが、強い人の多くの人はめちゃくちゃ優しいです。

なので、Twitter で「これくらいの実力の人とつながりたい」とか呟いたり「今日はこの問題が解けた！うれしい！」みたいに進捗をつぶやくと、いろんな人が「お、この人頑張ってるな」みたいな感じで拾ってくれると思いますし、疑問点をつぶやくと、つながりがあればかなりの確率でリプライが期待できます。こういう何気ない繋がりが結構モチベーションの維持につながると思うので、恐れずに自分の成果とかコンテストの結果とか疑問点とかつぶやいてみるといいかもしれないです。

緑レートまでの振り返り

かなり基礎的な部分に不安があったため、Hello, world! をスタートするくらいのレベルから本当にスタートしてました。この辺で文法とか標準入出力（整数、文字列、浮動小数点数）といった初歩的なことはほぼ大丈夫になります。これについてはできないとどうにもならないのでやるしかなかったと思います。

あとは今後に備えて、環境構築もきちんとしておきました。Mac の VSCode に C++ の基本セットを入れてあとはテストケース実行（Code Runnerとか）できるようにするだけですぐに終わります。それまでは Wandbox を使っていました。

その後は、ソートとか最大公約数、map や vector などの使い方をやっていました。この時は全く気づかなかったのですが、問題を解く上で一番基本的な考え方である「全探索」「貪欲法」「動的計画法」あたりは完全に抜けていました。これは非常にまずかったと思います。有名どころである蟻本とかを持っていなかったせいもあると思います。

問題を解く上でまず全探索を考え、制約を見て間に合いそう（制限時間 2 sec で O(10⁶) 程度までにおさまる）ならそれで十分、間に合わないなら工夫をする、という考え方が完全に抜けていたので、当時は全探索の問題が全く解けていませんでした。

また、貪欲法については、「なんとなくこれでいける」みたいな雰囲気で書いてしまい、それが通ることも多かったので深い考察をすることもなくコードを提出していることが多かったです（のちに痛い目にあいます）。

動的計画法については、AtCoder では Typical DP Contest とか Educational DP Contest とか開かれるくらいには重要な項目だし、この時期に取り組んでおけばもう少し成長が早かったのかな、と思っています。

個人的には大丈夫だったので、特に勉強はしていませんでしたが、緑目指すくらいの人のうち、「答えはあっているはずなのにどうしてTLEになるのかわからない」という人は、時間計算量の感覚を灰色〜茶色くらいで必ずマスターした方がいいと思います。

水色になるまでの振り返り

全探索から始め、AtCoder 400点くらいの難易度まで対策をして自分なりの考察フローチャートが自然に出来上がっていた気がします。自分の考察手順としては、全探索をまず第一に考え、それで間に合うならそれ以上のことはしない、間に合わないならどういうデータ構造やアルゴリズムを用いて計算量を落とすか、貪欲に行けるかどうか、貪欲でまずそうなケースはないか、余計な計算をしているところはないか、今まで自分が勉強してきたものに帰着できないか、というように考察をしていました。

先ほど挙げた 1~6 の内容だけでもきちんとものにすればビギナーは卒業できると思います。 ここまでたどり着くのに挫折してしまう人はいっぱいいます。ここまできたなら十分自信を持っていいと思います。

あと、蟻本の例題を解くために POJ に登録したのですが、コンパイラが古く、UI もイマイチでとにかく気に入らない点が多かったので、こちらの Qiita の記事を参考に勉強を進めていました。蟻本の例題を AtCoder の問題で置き換えてくれています。すごく役に立ちました。

qiita.com

中級編、上級編も存在しています。

その他

体調管理

夜に開催が多いのでつらいかもしれないですね。 体調悪い時はコンテストの参加は見送りましょう。ぼくは熱出ている時に参加して普段の半分のパフォーマンスになった経験があります(ABC113)。

部分点解法

もし、コンテストで制約が小さい部分点解法の結果だけジャッジを知ることができたら良い、という場合はその制約にそぐわない入力が来たら即プログラムを終わらせる、みたいなことをすると、ジャッジが返ってくるのが少し早くなります。例えば、Nを正の整数として「1 <= N <= 200 を満たすデータセットに正解すると 300 点が得られる」といったときに、1 <= N <= 200 なら普通に実行して、201 以上の値が来たらすぐ main で return 0みたいな感じです。

最近は部分点が設定されている問題はほぼないですね。

コンテスト中にSNSは控えた方がいいかも

順位表から分かる情報はつぶやいても大丈夫、ではありますが、うっかり「なんでこれTLEするんだ？」とか「5ケース落ちてる…」みたいなツイートをコンテスト後にTLを遡ってみるとたまに見かけることがあり、これはまずいのではと思うことがあります。特に鍵アカウントの人はRT等されないため、普段から意識をしていないとダメだと思います。

目標を見失わない

正直、水色になるまでに同じ大学の他の人のレート変動を見て「この人5回で青色になってる…」とか才能と努力の差を見てものすごく凹んでいた時期がありました。凹んでいても突然天才になったり脳みそが急に覚醒したりするようにはなりません。直近のパフォーマンス等を見ながらそれよりちょっと上ぐらいの目標を立てて一歩ずつ前に進む方が精神的にいいかもしれません。

*1:自分が始めてからそれほど期間が経っていなかったことと、短期間でUnrated コンが2回発生したため特例

*2:毎日やっていたとかではなく、3日ごとに少しずつ進める、みたいな超マイペース

*3:最近では Codeforces Div.3 というものがあるのですが、いきなり飛び込むとレートが下がりまくるので萎える人が多そうです。