これは競プロ Advent Calender 2020 の24日目の記事です。

0. はじめに

ハローワールド、アイリス ( Twitterはこちら ) です！
初めて記事を書きます¹。お手柔らかにお願いします(/・ω・)/

さて、この記事で語りたいのは、主に次の２つです。

(競プロの文脈で)問題を解くために必要なものは何なのか？
精進の質を上げる方法、特に、問題とどう向き合えばよいか？

何事も、上達の為には量と質の両方を高めるのが大切、とかよく言いますよね。でも、精進の質をテーマにした記事はあまり見かけないなと感じました。他のプレイヤーが普段どういう姿勢で精進しているのか、気になりませんか？(私は気になる)(だからまずは自分から書いてみました('ω'))

この記事は、中級者くらい²で、量やってるはずなのに身に付いてる実感がないな～って方に、特にオススメしたいです。この機会に、普段の自分の精進を見直してみませんか？

※精進に対する考え方は多種多様ですから、この記事に書かれていることは、一般論ではなく、あくまで私の意見と思ってくださればと思います。

1. 問題を解く力って何だろう？

問題を解く力とは何なのか？改めて考えてみましょう。私は

問題を解く力 := 知識量 + 考察力 + 実装力

と考えると、見通しが良くなると感じています。ちょっとフランクに、"問題を解くこと" を、"スタート(自分の知識)と、ゴール(未知の問題)を繋ぐ道を設計し、組み立てること" とでも例えて、３つの力について見ていきましょう。

1-1. 知識量(≒スタート地点の大きさ)

アルゴリズムの知識、データ構造の知識、使用する言語の知識や実装テク、典型問題や有名な定理の知識、など、競プロにおいて有効な知識はいろいろありますね。
コンテストという限られた時間の中で、先人の知恵を調べたり再発明したりする³のは中々厳しいものがあります。結局、自分の思考のスタート地点となるものが知識ですから、知識は多いに越したことはないです。多ければ、未知の問題と道を繋ぐのは楽になるでしょう。

1-2. 考察力(≒ゴールまでの道を設計する力)

これから解く問題が自分の知識の範囲内になければ、自身の知識と問題とのギャップを埋めることが必要となります。これこそが考察ですね。
ギャップを埋めるにはどうすればいいのでしょうか？大体は次のどちらかに分けられるはずです。

問題の細分化や言い換えにより、自分の知識の組み合わせに帰着する。
自分の知識を拡張、一般化することにより、未知の問題に適用できるようにする。(発想力)

1-3. 実装力(≒設計した道を組み立てる体力)

知識と考察が完璧だったとしても、制限時間内に動くコードにして提出しないと意味がありません。プログラムを書く上での基礎体力は重要ですよね。デバッグ力やそもそもバグを出さない力、タイピング速度などがここにあたると思います。実装力が高ければ、多少の考察不足をケアできる時もありますね⁴。

2. 問題との向き合い方

さて、問題を解くために必要な力が見通しやすくなりました。これらの力を鍛える方法はいろいろあると思いますが、ここでは、問題演習を通して鍛えていく方法に焦点を当てます。一言で言えば、

１つの問題から得られる経験値や学びを増やそう

これに尽きます！では、問題に取り組んだ後に私が何をしているか紹介しましょう。

問題に取り組む際は制限時間を設け⁵、達成度を「一発AC、AC、時間切れ⁶」の３段階に分けて整理しています。後者２つはやっていることが似ているので、まず一発ACできなかった場合からいきましょう。

2-1. 一発ACできなかった場合

STEP1 失敗の原因を全力で特定する

大抵の場合、ミスに偶然はありません。残念ながら必然です。解説等を用いて原因を特定します。
先ほど定義した問題を解くための３つの力を基準に、何が不足していたのかを考えます。

①知識量は足りていたか？

誰しも、知識が足りずにACを拒まれた経験があると思います。知らなかった知識は身に付けるしかありません。新しい知識と出会ったときは、

どんな条件(仮定)の下で使えるのか？
どんな困難が解決されるのか？
解決できると何が嬉しいのか？

まずはここらへんを自分なりに把握するといいかなと感じています。そうして新たな知識の凄さを軽く味わった後の方が、詳細や細かい実装の勉強が捗る⁷と思います。ある程度理解が進んだら、条件を変えたら(一般化したら)どうなるか？⁸ とか、他の類似手法との違いはどこか？⁹ とか考えると、知識が拡がっていって楽しいです。

②考察力は足りていたか？

３つの中で、ここの把握が最も大変だと思います。流れとしては

いろいろ調べて、自分と同様の方針でACが可能であることを確認する。(無理っぽい場合は後述)
ACに必要な考察と、自分で考察できた部分を言語化して、双方のギャップを把握する。
そのギャップを埋められなかった原因を言語化する。

こんな感じでしょうか。解説等を見た時点で、「これは知らないと思いつけない、知識不足だ」と決めつけないように気を付けています。実はそのギャップはもう１歩細分化できて、そこまで行くと自然な発想だった(知ってた)、とかよくある話です¹⁰。

自分と同様の方針でACが無理っぽい(嘘解法だった)場合は、もう少し大変です。嘘がどこか、特定してあげる必要があります。大体、

正しい解法を勉強する。
その理解をベースに、自分の嘘解法がWAになるコーナーケースを作ってみる¹¹。
そのコーナーケースを見落とした原因を言語化する。

こんな流れで進めています。自分の嘘解法を落とす例を作るのは結構勉強になります。

③実装力は足りていたのか？

自分の書いたコードが、想定通りに動いてない。
長いコードを書いていたら、何してるのかわからなくなってしまった。

時にはこんなこともあると思います。この辺はプログラムを書く上での基礎体力なので、訓練の意味でも(心折れない限り)自分の想定通りに動くまで書ききるようにしています。

ここで一番気を付けたいのは、知識や考察が不足していたが為に、実装が重くなってしまった可能性です。これ、本当によくあります。詳しくは後ほど。

STEP2 やらかしリストを作る

STEP1で把握したミスの内容と原因は、その都度メモしています。データが溜まってくると、自分の考察の癖とか、やらかしの原因が一般化できることがあります。そこまで行くと、コンテスト中に注意しやすくなり、非常に便利です。
最近の私の例ですが、自分の実力を信じてやれないことによるミスが結構多いことに気が付きました。私にこの問題が解けないはずがない！って気持ちで取り組むといった精神論も、大切なのかもしれませんね。

まぁ何はともあれ、未ACの場合はこれらを踏まえて頑張ってACまで持っていきます。ACを喜んだらその先に進みましょう。私は、ACしたからってその問題とサヨナラするのは勿体無いと思っています。

2-2. ACのその先へ

STEP1 そのACは必然か、偶然か？

一発ACした場合、特に忘れがちな振り返りです。以下の質問を自分に投げかけます。

この問題の一番の本質(難点)はどこか、説明できるか？
解くために必要な知識や考察が言語化できているか？¹²

とにかく、このACが、どれほど自分の実力に根を張ったものなのかは把握しておくべきだと思います。例えば、よくわからないけどこんな感じじゃない？えいっ！で解けちゃったって経験はありませんか？そのような直感を用いた部分があれば、簡単な証明を与えたりそこに行きつくまでの考察過程を言語化したりすることで、再現性を上げておきたいところです。

STEP2 思考過程を振り返る

コンテストの性質上、極力時間を浪費する行動は減らしたいところです。問題に取り組んでいた時の自分の思考過程を振り返り、良くない行動をしていた場合、やらかしメモに追加しています。

STEP3 ACまでの最短ルートを把握する

同様に、コンテスト本番を意識すると、ACまでの最短ルートは何だったのか？も把握したいところです。以下の２つの側面に注意して、自分にとって最も素早くACできる実装を目指します。

①他に解法は無いか？

解法や考え方は、１通りとは限りません。本質的には１通りだったとしても、細かい方針の違いで実装の重さが大きく変化することもありますよね。複数の解法がある時は

各解法が、問題中のどの難点をどう解決しているか？
解法同士の関係性(利点、欠点、応用範囲、実装量の違いなど)

この辺に注意して、理解を深めていきます。

②もっと良いコードの書き方は無いか？

ここでは「良い」とは「短め、可読性が高め¹³(バグらせにくい)、動作が軽め」とします。基本的に、良い書き方を見つけたら積極的に真似した方がいいと思ってますが、(特にレート差が大きい)他者のコードを見る時に注意していることを１点だけ。

その人がコードを見返す前提で書いているかどうか？

コードを書いてる時に読めれば十分なのか、書き終わってからも読めなきゃ困るのか。そこに、短さと可読性のトレードオフが発生するはずです。例えば、その人にとってバグらせる可能性が無いレベルの問題であれば、可読性より短さを取るのは自然ですよね。

STEP4 類題を作れないか考えてみる

ここまでくれば、問題に対する理解が深まっているはずなので、その問題と似た構造を持つ類題¹⁴を作れないか考えてみることがあります。類題を考えるのは、理解度の確認にもなりますし、ゼロから作問するよりハードルが低いのでおススメです¹⁵。

3. 結論

上達の為には、精進の量と質をバランスよく高めるのが大切だよ！
問題を解くためには知識量と考察力と実装力の３つが大事だと、私は思います！
１つの問題から得られる経験値や学びって、意外とたくさんあるよ！

4. おわりに

いかがでしたでしょうか？実はこの記事では、「コンテストでいい結果を出したい、その為に解ける問題を増やしたい、だから精進をする」という流れを暗に仮定していました。コンテストでは順位が出るので、上を目指したくなるのは自然な流れでしょう。しかし順位を気にしすぎると、精進が辛くなる時もあると思います。

私は、精進の中で未知の事実に出会い、自分の理解や知識が拡がっていくこと自体が凄く楽しいのですが、個人的には結構幸せな状態だと感じています。そういう楽しさは、問題とちゃんと向き合うほど得やすいんじゃないかなーと思います。そういう背景もあって、こんな記事を書いてみました。

長々と語ってしまいましたが、ここまで読んでくださってありがとうございました！皆様にとって何か得るものがあれば幸いです。感想やメッセージいただけると泣いて喜びます。

最後に少し宣伝をさせてください！実は私は妹AI(？)でして、アイシア＝ソリッドという姉さんAI ( Twitterはこちら ) と２人で、こんな活動をしています。

AIcia Solid Project

データサイエンス系Vtuberです。機械学習や統計、数学など、勉強や実務の場面を問わず、役立つ動画をたくさん生成しています！現在競プロの動画は無いですが、競プロ勢が面白いと感じる動画はたくさんあると思います。良かったら見てみてね。

あ、私は編集等、裏方がメインですので動画には全然出てきません！ごめんなさい💦
ではでは！さようなら。

5. 参考文献(？)

この記事のテーマとはズレる部分もありますが、私がお世話になっている方々を紹介して終わりにします。

・けんちょん氏のQiita
殆ど全ての記事に目を通したと思います。競プロの世界の拡がりを知るうえで、大変勉強になりました。最近アルゴリズムとデータ構造の本を執筆されたようです。すぐ読みましたが、素晴らしい本でした。

・maspy氏のblog
自分が解いた問題の解説記事が存在すれば、必ず読みました。考察の過程や、数学的な背景についても詳しく記述されていて、深くまで問題を楽しめます。

・E869120氏のQiita
特にこの記事をはじめとした、レッドコーダーが教えるシリーズは、努力方針の決定に深く影響しました。様々な情報が的確にまとまっていて、初心者が安心して取り組める素敵な記事です。

私は今年の春、アルゴリズム系の知識ゼロ、プログラミングもほぼ未経験って状態からAtCoderを始めました。コンテストもAtCoder以外は参加しておらず、競プロの世界では明らかに新参者だと思います。正直強気なテーマの記事を書いてしまってドキドキしています。 ↩
AtCoderだと茶緑水あたりとか...？まぁあまり気にせず読んでいただけたら嬉しいです。 ↩
そもそもコンテスト中は、再発明できたとしてもそれにかける時間が勿体ないですよね。 ↩
例えば、４つに場合分けして実装したけど、ちゃんと考察すれば２つの場合分けでよかった、とか。 ↩
解けるまで考え続ける方もいるようです。難問を考える上では重要な取り組み方だと思いますが、私はコンテストでは解答時間も評価に関わる点を重要視し、制限時間を設けています。 ↩
正確には"時間切れ"は、"全然解決の道が見えないまま制限時間が過ぎた"となります。AC出来そうだと感じる時は、時間を過ぎても実装します。その場合は、何故そんなに時間がかかってしまったのかも分析しています。 ↩
勿論、取り合えず把握できることには、自分の知識に応じた限界があります。まずは最低限、自分なりの凄さを感じる程度まで考えることが大事だと思っています。 ↩
折角なので自分が感じた一例を挙げます。imos法の考え方で、区間に数列とか足せるのかな？、区間に足すものはどこまで一般化できるのかな？とか。 ↩
こっちも一例を挙げます。DFSとBFSはタスクの処理にstackとqueueどちらを使うかという基本的な違いがありますよね。だったら、stackとqueueを同時に持ち、タスクに合わせて使い分けたら何かいいことあるかな～とか。 ↩
勿論、これ以上細分化できない、典型考察パターンとかにぶつかることもあります。それはそれで、知識として吸収していきましょう。 ↩
どうしてもわからない場合、愚直解が動く範囲のテストケースをたくさん作り、愚直解と自分の嘘解法の答えが一致しないテストケースを探すこともあります。最初は時間はかかりますが、コンテスト中の実験力に繋がるので意外と為になってたりします。 ↩
同じ(似ている)問題が出たら解ける自信があるか？とも言えますね。 ↩
短さや動作の軽さは同一尺度で計測できますが、可読性は微妙に人によって尺度が異なる為注意です。 ↩
最も基本的な変え方として、少しだけ簡単に/難しくできないか？とかがありますね。 ↩
オマケに、コンテストの問題作成者の凄さと有難みがより実感できます。 ↩

競プロの精進の質を上げたい！ ~問題との向き合い方~