帰着する力はどうやったら鍛えられるのだろう、という話

問題を見て解法を考えるところを言語化してみる

最近はリアルタイムのコンテスト中のメモを見て、事後的に「考えたこと」として言語化するようにしていた

しかしコンテスト中は時間のプレッシャーが強いのであんまりきちんと言語化されてない

そこで過去問を見て、いきなりコードを書くのではなく、考察を書くというアプローチをしてみる

問題の選択はAtCoder Problemによる「正解確率50%」を使う

公式解説と比較して、過不足を確認する

やってみて

計算量の見積もりミスが多い

多く見積もるケース:

「全探索は無理だろうな」→正解は全探索 ABC165C

少なく見積もるケース:

「DPで計算できるぞ」→DPでは間に合わないので問題変形でもっと軽い問題に帰着することが必要だった AGC048

問題条件の勘違いが多い

実際に解いてる時にはサンプルデータを見たり、こけたりして気づいてるのだろう。コードを書かないで文字だけにしたことで勘違いが目立つようになった

パソコンが必要ないので風呂でも食器洗いながらでもできて良い。

ACにならないからリストから消えない

たくさん(30個とか)まとめて解く予定の問題を追加するとどれが解いてないかわからなくなって混乱する

中難易度(正解確率50%)と高難易度(正解確率20%)の問題があって前者はサクサク解ける(10min/q)のだけど、サクサク解けるというのは「既に持ってる思考の部品」を当てはめてるわけなので、その事例を集めてもそこから新しい部品を見出すことが困難

と主観的には思ってたが実際に高難易度問題にどう答えてたか確認したら「サクサク解けなくて残ってた問題」が必ずしも高難易度の問題ではない

例えば高難易度の問題でもABC034C(難易度1412)やARC106D(1989)はあっさり解けてる

数式変形に帰着する問題は他の参加者と比べて僕が得意

逆に貪欲に解くことができることに気付くことが求められる問題は苦手

蟻本などを読んだ時に、貪欲法は「わかってる」と自己認識してスルーしていたが、現実には「貪欲法で解けると確信した後の実装はできる」「貪欲法で解けると気付く、証明するところが弱い」なので帰着する力の切り口では「わかってない」

難易度帯で淡々とやっていくのに飽きた

達成感が得られないからな

解説記事からリンクされてる問題を解くことにした

done

まったく同じ ABC146D AGC038A AGC036A ARC083A ARC026B ARC040C ARC024B cf17_final_C AGC024B soundhound2018_summer_qual_C panasonic2020_D ARC091B ARC040C

公式より小オーダー ABC147D ABC006C

方針は同じ、追加あり ABC070D ABC125C AGC014B AGC018A ABC132D ABC014C

ケアレスミス aising2019C

問題条件勘違い code_festival_2017_quala_C ABC109D

証明 ABC112C AGC003B

方針は違うが結果は同じ ARC062B AGC024C

大きな違い

複雑に考えすぎ

indeednow_2015_quala_C ABC016D

もっとオーダー小さい解がある

ABC121D ABC147D AGC033A

未整理

ARC054B ARC092A ARC052B

tenka1_2017C ABC105C ABC032C ABC054C diverta2019_2_C

indeednow_2015_qualc_C ABC089D ABC157D ABC012D ABC154E ARC032B ABC126D ARC081B ABC138E ABC014C

tenka1_2018_C AGC024C ARC092A ARC052B ARC024B AGC024B ARC054B nikkei2019_qual_C ABC019C ABC140D ARC042B ARC064A ARC034B ABC124D ARC037B

ARC097B ARC097A ARC036B ABC096D ABC150D

難し目の問題