116. AtCoder水色になりました
昨日の AtCoder Beginner Contest 253 で無事入水できました。
実は、参加当初からコンスタントに緑パフォくらいは取っていたので、成長が明確に色へ反映されたのは今回が初めてになります。というわけで、色変記事というのを書いてみようと思います。
読んでくれる方の為になりそうな精進方法あたりの内容を先において、自分語りは後においておきます。
精進方法について
AtCoder Problems を見ると、今まで288問通していました。これは、入水まで解いた問題数でいうとおそらく少ない部類に入ります。
一方、Difficulty Pies を見ると実は水色を一番解いていて、最近は青色にも手を出し始めています。これを見てもらうと分かるのですが、私は自分にとって難しい問題を優先的に解いていく精進方法を取っています。
戦略的に解く問題を選択する
私はもう社会人ですので、競プロに当てられる時間はそう多くないです。そのため、成長に対する時間効率が必要でした。
以下は AtCoder Performances で出力したパフォーマンス遷移です。AtCoder 開始から2ヶ月後（7回目）くらいに初めて自分のパフォーマンスを見直しました。
7回目までのパフォーマンスから読み取れる情報として、以下のようなものがありました。
- パフォーマンスはほぼ毎回緑をキープできており、非常に安定している
- 緑と水の境界に壁があり、ここを超えられていない
このことから、2月下旬時点で自分の能力は以下のような特徴があると分析しました。
- 緑までの知識や実装効率はだいたいカバーできている
- それより上の知識が大いに不足している（だから上に突き抜けられない）
よって、自分に必要なのは解ける問題の幅を広げることであり、たくさん問題を解くことではないと結論付けました。自分にとって難しい問題を優先して解くとは、このことを意味します。
解いてきた問題
AtCoder Problems より、Climbing Progress Charts を載せます。
開始2ヶ月後くらいに戦略が変わったのがよく分かりますね（笑）
1～2ヶ月目
典型90問の ★5 までと一部の ★6 を解いていました。★5 までは一通り見ましたが、特に後半は通せていないものもあります。
当時はまだ競プロに慣れる段階でしたので、必要な知識の習得とライブラリの拡充を頑張っていました。この期間でライブラリ開発環境やコンテスト用ソリューションの整備を行いました。私は C# を使っているので、Priority Queue や MultiSet などコンテストで要求されたデータ構造は自作しました。
この期間の精進は、知識ベースを揃えるという意味でとても為になったと思います。感触としては、初学者はとりあえず ★5 まで一通り見ておけばよさそうに思いました。
3～4ヶ月目
先ほど述べた戦略を考えた時期です。この頃から典型90問を解くのをやめて、AtCoder Problems の Recommendation から Difficult を優先して解いていました。解くのは Moderate か Difficult の問題のみで、Easy は意味がない（いわゆる虚無）と考えて全く手を出しませんでした。
当初は緑と水で明確に難易度差を感じていましたが、少し続けていくと緑も水も同じような難易度に感じられるようになってきました。これは、難しい問題に触れ続けたことで、その難易度帯特有の考え方に慣れてきたのかもしれないです。初めは辛くても続けていくことが大切かな、と思います。
ただ、この時期はあまり精進の成果が出ず、やや停滞期に入っていました。そこで、今月初め頃にもう一度戦略を見直しました。
5ヶ月目～
4ヶ月も続けていると、コンテストごとに特徴があることに気付けていました。
- ABC / ARC で問題の傾向が明確に違う
- ABC は単純な知識、ARC は問題をアルゴリズムに落とし込む力を問われる
- 古い問題ほど、問題定義が曖昧だったり、本質的でない実装の複雑さが要求されたりと最近の問題傾向との乖離が激しい
自分が主戦場にしているのは ABC なので、最近の ABC を優先して解くのがおそらく最適です。そこで、ABC の過去問を新しい順に、緑～青下位の問題を解いていく戦略に切り替えました。青下位を入れた理由ですが、この頃には水上位でも自力で解ける問題が出始めており、青下位でも解説から一手知れば自分で通せるものが多かったからです。
問題との向き合い方
難しい問題を優先して解くので、当然ながら解けない問題はたくさん出てきます。いくら考えてもこれ以上手が出ない、となればもちろん解説を読みます。
「解けない問題」には3種類あると思っています。このうち「為になる問題」は 1. と 2. です。
- 方針は合っているが、実装力が足りず解けない問題
- 要求される知識が無くて解けない、かつ、それを知れば解ける問題
- 要求される知識が無くて解けない、かつ、そのベースとなる知識も無いので要求知識単独を知ったところで解けない問題
1. については、解説を読んで「実装力不足である」ことに気付けます。これは普通に通せるまで頑張って実装することでカバーできます。方針が合っていることは確信できているので、実装で大いに悩めばよいです。
2. が一番美味しい問題です。必要とされていた知識（問題へのアプローチ方法も含む）について、自分の中で納得できるまでしっかり考察します。このとき、解けなかった問題自体はそのままにしておきます。その知識についてたくさん調べて、どういった問題に適用できるのか考えて、必要に応じてライブラリ化します。咀嚼しきった後、数日経ってから解けなかった問題を自力で通します。数日置くのは、知識が自分の中に定着していることを確認するためです。
3. については、解説を読んでも理解できない問題が当てはまります。これは明確に実力範囲外なので、Diff を確認して「この難易度帯はまだ自分には早い」と見ないことに決めます。
メンタル的な話
レートやコンテストに対する姿勢などです。
レートは気にしすぎない方がいい
周りを見ていると、レートを気にしすぎて病んでいる人が少数ながらいる印象です。競技プログラミングなのでレートが気になるのは当然ですが、あんまり気にしすぎると本質を見失うのではないかな、と思います。
競技プログラミングを始めたきっかけは、みなさんおそらくレートでは無いと思います。自分の場合、仕事でやっているプログラミングに幅が無くなってきたので、基礎体力を付けたいという理由で始めました。人によっては「楽しそうだから」で始めることもあるでしょう。そういった主目的を忘れて「レートを上げたいから」で続けていると、それは辛いだろうな、と思います。
レートは後から付いてくるものと考えた方が気楽で、自分はコンテストすべて Rated で出ています。Unrated で参加せざるを得ないほど余裕がないタイミングは、出るだけ無駄だと思うので後から時間を取ってバーチャル参加しています。
自分に合ったコンテスト参加環境
初めの頃は、集中するため筆記試験を受けるような環境で参加していました。ところがある日、音楽を聞きながら適当な気持ちでバーチャル参加した ABC で青パフォ相当の結果が出ました。ここから、「リラックスできる環境が自分には合っているのでは？」となりました。
以来、YouTubeで音楽を流し、お香を炊きながらコンテストに参加しています。やはりこちらの方がパフォーマンスが良いです。謎ですが、自分はこっちの方が合っているみたいです。
ちなみに、主に東方Projectの音楽を流しています。声入りの曲はさすがに思考の妨げになるので、流してないです。
水色までに習得した知識など
とりあえず明確に意識するようになったのは、制約から想定される計算量を逆算することです。全探索で間に合うなら、カッコいいアルゴリズムを考えるより全探索した方が早いしパフォもいいです。
それ以外の知識的なものは以下にまとめます。C# で参加しているので、C++ と名前が違うものについては注釈を付けます。
以前から利用（理解）していたこと
- データ構造
- アルゴリズム
- 数学
- 進数変換周り
- mod四則演算
- 行列
- 計算量の見積もり方（オーダー）
AtCoderを始めてから理解したこと
- C# 標準に無くて自作したデータ構造
- グラフ
- アルゴリズム
- 数学
- ユークリッドの互除法、拡張ユークリッドの互除法
- 合同方程式*6
- フェルマーの小定理（mod逆元）
- マンハッタン距離からチェビシェフ距離への変換
- 包除原理
自分の経歴など
ここからは自分の経歴について書いていきます。
まず、現在私は社会人5年目の20代です。職業としてはプログラマーをやっていて、主に C# を書いています。C# に関しては最新の言語機能も追っており、割と高いレベルの知識があると思っています。
競技プログラミングを始めようとしたきっかけは、最近仕事で要求される知識セットに広がりがなくなり、また、プログラム以外の対人な仕事も増えてきて、技術的につまらなくなってきたからです。基礎体力をつけようという気持ちで始めてみました。
競技プログラミングについて
プログラミングは中学時代からやっていて、実は、高校の頃にパソコン甲子園という競技プログラミング大会にも参加していました（今でも開催されてますね）。当時は C++ を使っていました。
実を言うとこれで本戦まで行ったことがあるのですが、当時の競技プログラミングは今と比べようもないほどゆるふわなレベルで、所属が普通高校だったこともあり本戦出場のハードルが低めに設定されていたため、「運良く通った」というのが正しいです。今の ABC で言うと B 問題くらいまでの難易度しか解けてなかったと思います。
ただ、競技プログラミング以外にゲーム制作をやっていて、この中で AI を作っていました。ここで深さ優先探索・幅優先探索のアルゴリズムを自力で発見しました。当時はこのアルゴリズムに名前が付いていることすら知らず、グラフ上を行ったり来たりするので「旅人法」とか呼んでました。
競技プログラミングはいったんここで離れていました。大学時代は競技プログラミングや AtCoder の存在も認知していましたが（アカウントだけ作っていました）、あんまりやる意義を見出だせなくて手を出していませんでした。
嗜好について
自分を端的に表現するなら、レトロゲーマーかな、と思います。
上の方で東方Projectの話題を挙げましたが、東方Projectから入って弾幕系シューティングゲームが昔から好きです。ゲーム内のプレイヤーではなく、自身のスキルを磨いて攻略するゲームが好きで、競技プログラミングもそれに近いものを感じます。
この手のゲームを好む人は「先人のパターンをなぞる」タイプと「試行錯誤から攻略法を見出す」タイプに分かれますが、私は後者です。競技プログラミングでは、既存の野良ライブラリを使わず自分で頑張って実装する辺りが性格出てるのかなー、と思います。
学力について
理数系特化型ではなく、満遍なく点数を取るタイプでした。
中学時代は真面目だったので定期テストは常に平均9割超えでしたが、高校時代はプログラミングに傾倒しすぎて成績が不安定になりました。
数学は好きでしたが、実は得意とは言えませんでした。そこまでセンスが無かったのと演習不足で、応用力が無かったタイプです。今でいう共通一次、以前はセンター試験と呼ばれていたものでは、数IAは満点、数IIBは9割ほど取れていました（全科目でも9割取れていました）。ただ、二次試験（京都大学）は数学が最後まで足を引っ張っており、これだけ突出して偏差値が低かったです。
大学・大学院は京都大学で情報学科～情報学研究科の修士を出ています。なので、情報学についてはそれなりにちゃんと知識があると思います。ただ、大学時代も数学は「好きだけど苦手」で、数学だけ成績が低かった記憶があります。
学力とはあんまり関係ないですが、以前興味本位で受けたIQ試験（WAIS-IV）では、全知能IQは 123 と出ていました。上位 6.2% らしいので、まぁ良いけどそんなに突き抜けてもいないな、という感じです。
