競技プログラミングでの問題の解き方

競プロの先輩方のブログにはいつも助けてもらっています。

一方で、この手のチートシートはまとめる過程自体が勉強になることが多いので、自分でも思考の整理を兼ねて整理していきます。

コンテストに臨む前段階

• よく寝る

9時からと遅めなので、まずはよく睡眠をとっておく。当日は時間があったら精進より睡眠。

• ペンと紙（方眼紙）の用意

書き殴りながら整理するための用意。２次元のグラフやら数直線やらを書くのに、方眼紙があると特に考えなくても綺麗に書けるので良い。

問題を理解する

問題読解

• まずは問題文をよく読み、求めたいものを明確にする。

制約も含めて、問題の意図を理解してからアプローチを考え始める

• 問題とテストケースの状態を図示する。

視覚化することで情報が整理できたり、そもそも自明だったりする。一度紙に落として図示する。

計算量見積もり

• あり得る答えの可能性を全探索することを考える

だいたい最初はこれ。簡単な問題ならだいたいこれなのでこの思考過程は絶対通ると固定してしまっても無駄になるよりも特になる機会の方が多いと思う。

これで直接的に解けるパターンとしては答えとしてあり得る状態が10⁶程度まで。ただそれ以外のケースでもどこの変数を軽くしないといけないかが明確になるなど、次の方針が立てやすくなるのでどっちにしろ損にはならない。

特に、英語はa-zの26パターンしかない、格子点を全部チェックするなど、一見ややこしそうでも大して選択肢ないじゃん、となることは結構ある。

• 通すのに必要な計算量の見積もり

全探索の可能性を考えた後に、落とすべき計算量を考える。

O(n³)を変数1つ固定してO(n²)にする、O(n²)をO(nlogn)にする（この時点で二分探索っぽいなー）など

データの前処理

• 言及されていない条件は都合よく整えるのに使う。

ソートしても問題ないものであればソート済みとして扱う。複数の文字列を1つとしてみても問題がないなら先に変換をかけてしまう、など扱いやすい形にデータを整形する。

問題を解く計画を立てる

基本（汎用性高い考え方

• 全探索で無理なことを確認した上で、①なんらかのルールで貪欲に出せないか②DPで処理をまとめることができないかを考える

全探索→貪欲→動的計画法の思考の流れは、基本問題の多くがこれを使うんじゃ無いかというくらい汎用性が高い。

全探索→貪欲→動的計画法の順序で書いたのは初めてだけど、これはこれで良いのよね。
全探索→動的計画法がアルゴリズム的には繋がりが良いのだけど、貪欲を挟む事で、「自明な改善が出来ないケースでDPが有効」ってストーリー性を持たせやすくなる。

— chokudai(高橋 直大)🍆 (@chokudai) February 21, 2020

複雑な条件

• 状況を分解して、いくつかの小さな部分問題を解決するとして考える

よくあるのが上下左右の処理を、それぞれ上、下、左、右の4つに分けるみたいなやつ。２次元のデータを一旦1次元の配列として見るとかも。

汎用的に使える問いかけ

• 「定義は何か？定義から、追加で使える条件はないか？」

三角形の内角の和はπ、a,bが互いに素ならax+by=1を満たす(x,y)が存在する、など問題文には書かれていないけど暗黙に条件として与えられているものがないかを考える。

処理別

組み合わせ

• 全量が決まっている時、何らかの変数を固定することで他の変数が自明な状態にならないか？

n²やn³のループから1つ次元を落としたい時に使う。合計金額が分かっていて、xの金額が決まれば、残りのyの金額は探索するまでもないじゃん、ってやつ。

操作、構築

• 操作の終了条件、終了した時の状態を考える

最終的にどうなったら終わるのかがわかると、それがそのまま最後の状態になる。

• 最終状態からさかのぼって考えてみる

ゲーム理論のように、最終状態はそれまでの判断が全て決定しているので大体一位に判断が決まる。そこで最終的な状態から遡っていくと芋づる式で解ける場合はまあまあ多い。

• 操作を行った前後の影響を考える

一度使ったカードはまた使えるのか一度きりなのか、切り離したり連結したら端はどうなっているか、並び替えた時にインデクスはどうなっているか？など変化するところ（逆にしないところ）に注目する

数字処理

• 桁ごとに分けて処理をかけたいときは文字列として扱う

桁ごとの合計や回文を作るなど、1塊の数字としてではなく、桁ごとの値を独立して扱いたい時は、文字列として扱っておくと桁を指定して処理がしやすい。

番外編

できた問題

• 何が問題を解く上で肝だったのか説明できるまで他の人の解説を読む

問題を解いているとテストケースがあっていれば良いという意味で、何となく解けてしまうこともある。。
一方で、再現性を持って対応ができるためには明確に指針を持って解ける状態にしておく必要がある。そのために必ず「ここが本質的に難しいポイントでここを考えると見える」って部分を捉えるまで考える。

自分の場合具体的な運用は、過去問の進捗と使ったアルゴリズムをまとめているシートに、上記部分を実際に書いてみる。

ちなみにこの考え方は、chokudaiさんも言及しています。

しいて言うなら、問題を解いた後に「この問題の肝はどこだったか？」というのをしっかり考えることは大切です。一色下の人に対して、30文字ぐらいで伝えようとしたときのヒントが、この問題の肝だと思います。

AtCoder社に行ってchokudaiさんと話したお話 - ひゅ～Menの雑記帳

できなかった問題

• 具体的に何ができなかったのを明確にする

解法を丸暗記してもそのまま次に出るわけではないので、何が原因で解けなかったのかを振り返る。「何らかの前提知識が足りなかった」「持っている知識が使えることに気づかなかった」「方針はたったが、何らかの実装がついてこなかった」あたりになるかな。

参考

良い数学のテキストはアプローチの説明が丁寧

総合的研究 数学I+A (高校総合的研究)

数学ガールシリーズが好きなのですが、その著者が参考にしていると聞き。何度も読み返す本です。

いかにして問題をとくか