ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

【TopCoder】1つ上の色のコーダーになるために

初めに

この記事はCompetitive Programming Advent Calendar 2014の19日目の記事です。

どうも、ぱーぽーです。
この記事では「TopCoderアルゴリズム部門であるSRM(Single Round Match)で1つ上の色コーダーになるためにはどのようにすれば良いのか」について考えていきます。

対象読者は、SRMに参加したことのある灰・緑・青コーダーの人です。

黄・赤コーダーの人でこの記事を見てくれている人は「ここはこのようにすべきだ」等のアドバイスをしてくれると嬉しいです。

突然話が変わりますが、本題に入る前にまず私が何者でどの程度の能力なのかを知ってもらわないといけません。

f:id:purple_jewel928:20141218225336p:plain

恥ずかしさがあるのであまり見せたくはないですが私のSRMにおけるレート推移です。
2012年からスタートして参加回数は70回程、現在(12/19)のレートは1404です。Twitter上には超人がたくさんいて感覚が狂いそうになりますが、私のような凡人はこのくらいの能力です。レートは一応右肩上がりですがノビがないです。
このレート推移をどう見るかは皆さん次第です。(しょぼいとか思わないで)
SRMにそこそこ参加していて、少しくらいはSRMが何なのかを知ってそうな奴だな程度に思ってもらえればよいかなと思います。

今回はあくまで対象となる皆さんと近い目線で書いていければ良いと思っています。

これから書く内容は自分の体験やTwitterで見た、聞いた内容が元となっています。
Twitterでは特に@evima0さんから様々なことを教えてもらった気がします。感謝です。

※この後の内容では「○○をどのくらいの頻度で解ければよい」のような書き方をする場合がありますが、問題の難易度によってそれらは変化するのであくまで目安として考えてもらえればと思います。

※今回は撃墜フェーズことチャレンジについての説明は省きます。レートの増減につながります。


緑コーダーを目指す

以下をこなせるようになりましょう。
① div2 easyを安定して早解き
② div2 mediumをゆっくりでもいいのでたまに解く

div2 easyについてです。
div2 easyは問題文で問われていることを単純に実装する問題が多いです。文字列が入力で与えられる問題が多い印象があります。
基本的にはif文やfor文、配列の使い方といったようなプログラミング言語の基礎ができていれば解くことができます。

たまに以下のような変則的な問題もたまに出てくるので注意する必要があります。
TopCoder SRM 633 Div2 Easy : Target - ぱーぽーのぷろぐらみんぐ記

また、問題文がやたら長くてよく分からないこともたまにあるので注意です。

少し私の話をします。
今となってはdiv2 easyなら240pt前後は安定して取ることができますが、最初のSRMを始めたばかりのときはそんなことありませんでした。普通に落とすこともありましたし、点数も全然稼ぐことができませんでした。

div2 easyが解けない原因として考えられるのが3つほどありました。
SRM自体に慣れていなかった
・英文読解のミス
・コンテスト独特の緊張感

1つ目については過去問を解くなどして慣れていきました。「慣れ」はとても大事です。
2つ目については翻訳ソフトを使うなどして対処することが多かったです。
問題なのは3つ目です。それまでAOJ(Aizu Online Judge)で問題を解いていたことはあってもコンテストに出たことがほとんどありませんでした。このような勝負ごとでの緊張は競技プログラミングに限らずよくある話だと思います。これも慣れの問題かもしれませんが、私は本番でかなり緊張するタイプの人間なのでとても悩ましい問題でした。というか今でも結構緊張します。Twitterをやっている人はコンテスト前にTwitterを眺めて少し気を紛らわせてみるのもよいかもしれません。「SRM!!SRM!!」や「よしこーなー」というツイートを見ることができます。

div2 easyが安定しない人で私と似たような体験をしている人がいるかもしれません。div2 easyは慣れと読解ミスに気をつければきっと解くことができると思います。

div2 mediumの詳細については後述しますが、参加者の結構な割合で解かれているような簡単な問題であれば解く必要があります。


青コーダーを目指す

以下をこなせるようになりましょう。
① div2 easyを安定して早解き
② div2 mediumを安定して早解き
(③ div2 hardを極たまに解く)

div2 easyは引き続き安定して早解きしましょう。

div2 mediumについてです。
div2 mediumはgreedyに解くような問題が多いような気がします。数学系や二分探索の問題もたまに出ます。
この方法が良いとは一概には言えないですが、問題文を読んだらまず「greedyで解けるかな?」と考えても良いかもしれません。

正答率の低いような問題なら解けなくても大丈夫ですが、解いている人がそこそこいるような問題であれば早解きする必要があります。

ここも正直「慣れ」と言ってしまいたいところですが、div2 easyほど早く慣れるのは難しいかもしれません。
レート900から1100付近まではdiv2 easyを早解きして、div2 mediumをぼちぼちのスピードで通せばいけると思いますが、そこから青になるまでは大変だったような記憶があります。ここからはいかにdiv2 mediumを早解きするかが重要になります。

そしてdiv2 hardについてです。そこまで重要ではありません。
div2 hardはグラフやDP、数学系など様々なジャンルの問題が出ます。

まずdiv2 hardを本番でバンバン通せるような人は実質黄コーダー以上の実力はあると思います。対象読者から除外です。
今の段階ではdiv2 easy, mediumを確実に通すことに注力してもらって構いません。
ですが全く見ないのは勿体無いです。解ける可能性のある問題も出ることがあります。
私自身、div2にいた頃にdiv2 hardを本番で2回ほど通したことがあります。(どちらもこれ本当にhardか?と思うような問題だった記憶があります。しかしどちらの回もmediumを落としたので3完したことはありません。つらい。)
また、div2 easy, mediumを早解きできるようになった頃にはdiv2 hardを読む時間は十分にあります。
挑戦してみましょう。


黄コーダーを目指す

ここからが私にとっての本題です。私は現在(12/19)青コーダーです。
自分のことを棚に上げて「こうすれば黄コーダーになれます」と書いてもよいですが、実際自分は黄コーダーになれていないので、皆さん一緒に考えていきましょう。そして黄コーダーになりましょう!

以下をこなせるようになりたい
① div1 easyを安定して早解き
(② div1 mediumをたまに解く)

先にdiv1 mediumについてです。そこまで重要ではありません。
これはもはやスルーしてもよい気がします。
Twitter上でも「medium解けなくても黄コーダーになれる」という意見を複数聞きます。
もちろん解くことができればよいですが、今はスルーします。
そもそもまともに解けないので説明できません。

div1 easyについてです。
div1 easyはgreedyや数学系の問題が多い印象です。div2 mediumと同じ問題だったり、それの制約を変えて難しくした問題です。
最近ではコーナーケースがたくさんあるような問題も結構な頻度で出ています。赤コーダーでも普通に落とすようなものも含まれています。怖い。

これを180~200ptくらいで安定して解くことができれば黄コーダーになれるはずです。
しかしこれが難しい...。200ptは大体15分程度で提出する必要があります。

正直なところ練習しまくるしか方法はないとは思いますが、最近私が意識していることとして「解ける問題は落とさない」というのがあります。
そもそも私のdiv1 easyの正答率が低いことから、上がらなくて当然だという感じがしています。
上で触れた赤コーダーでも落とすようなものはしょうがないにしても、そうでないものをまず確実に通すというのを意識しています。点数云々はそこからかなーという感じがしています。
意識の問題ですが、これを意識しだしてからdiv2落ちしていないです。どうしても点数を稼ぎたいと焦ってしまうとくだらないミスをしてしまいます。2013年12月頃ですが、一気にレートを落としました。チャレンジ失敗による負の点数ですね。「焦らない」、「レートが減らなければ感謝」という気持ちも大事そうです。
あと青コーダーが早解きできていて、黄・赤コーダーが提出していない、または再提出しているような問題は要注意です。

今こうやって記事を書いていて、ホントどうすれば安定して解けるようになるかなーとか迷いだしています。
上のレート遷移見て分かるように、青コーダーの期間が長すぎます。
練習時間が確保できていない等の理由はありますが、少しやり方を見なおしたほうがよいと思っています。

私と似たようなレート遷移で黄コーダーになった人はどんな練習していたんでしょう。気になります。


練習法について

練習法は人それぞれですが、自分の体験を交えてオススメするとすれば
「自分が早解きしたい問題+遅くてもよいからとにかく解けるようになりたい問題」
を解くのがよいと思います。

緑コーダーを目指すのであればdiv2 easy, medを、
青コーダーを目指すのであればdiv2 med, hardを、
黄コーダーを目指すのであればdiv1 easy, med, div2 hardの練習をすればよいのかなと思います。

div2 hardを練習することについてですが、@evima0さんが「div2 hardは教育的な典型問題が多いから練習するとよい」とアドバイスしてくれたことがあります。
editorialを見ながらでも良いので解いてみるとよいかもしれません。

実は私がレート1100台でうろついているときにアドバイスしていただき、div2 hardをeditorialを見ながら解いていた時期がありました。
結果は上のレート遷移の通りですね、私の中では効果があったと思います。

また、コンテストに出て解けなかった問題の復習をすること、継続的に練習することも非常に重要だと思います。
これは私自身できていない点でもあるので気をつけたいです。


終わりに

長々と書いてしまいすみません、いかがだったでしょうか。
「この記事を読んだら○コーダーになれました!」って言ってもらえたらとても嬉しく思いますが、結局のところ頑張るのは自分自身です。
練習して1つ上、2つ上のコーダーになれるように頑張りましょう。

ここからはこの記事の存在を否定するような内容になりますが、
レートを上げることだけが競技プログラミングではないと思っています。
私自身レートを気にしすぎていてしょんぼりな時期もありました。

競プロエンジョイ勢としては、まず競プロを楽しむことを第一に考えたいです。

競プロを楽しんで、なおかつレートも上げれば最高にハッピーですね。

明日は担当はnhirokinetさんです、お楽しみに!!




※貰えたスターの分だけレート上がる気がする