🪴 Quartz 4.0

Search

SearchSearch

帰着訓練

Dec 01, 2023, 5 min read

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

  • 問題を見て解法を考えるところを言語化してみる
    • 最近はリアルタイムのコンテスト中のメモを見て、事後的に「考えたこと」として言語化するようにしていた
    • しかしコンテスト中は時間のプレッシャーが強いのであんまりきちんと言語化されてない
    • そこで過去問を見て、いきなりコードを書くのではなく、考察を書くというアプローチをしてみる
    • 問題の選択はAtCoder Problemによる「正解確率50%」を使う
    • 公式解説と比較して、過不足を確認する

やってみて

  • 計算量の見積もりミスが多い
    • 多く見積もるケース:
      • 「全探索は無理だろうな」→正解は全探索 ABC165C
    • 少なく見積もるケース:
      • 「DPで計算できるぞ」→DPでは間に合わないので問題変形でもっと軽い問題に帰着することが必要だった AGC048
  • 問題条件の勘違いが多い
    • 実際に解いてる時にはサンプルデータを見たり、こけたりして気づいてるのだろう。コードを書かないで文字だけにしたことで勘違いが目立つようになった
  • パソコンが必要ないので風呂でも食器洗いながらでもできて良い。
  • ACにならないからリストから消えない
  • たくさん(30個とか)まとめて解く予定の問題を追加するとどれが解いてないかわからなくなって混乱する
  • 中難易度(正解確率50%)と高難易度(正解確率20%)の問題があって前者はサクサク解ける(10min/q)のだけど、サクサク解けるというのは「既に持ってる思考の部品」を当てはめてるわけなので、その事例を集めてもそこから新しい部品を見出すことが困難
    • と主観的には思ってたが実際に高難易度問題にどう答えてたか確認したら「サクサク解けなくて残ってた問題」が必ずしも高難易度の問題ではない
      • 例えば高難易度の問題でも[ABC034C]や[ARC106D]はあっさり解けてる
        • 数式変形に帰着する問題は他の参加者と比べて僕が得意
      • 逆に貪欲に解くことができることに気付くことが求められる問題は苦手
        • 蟻本などを読んだ時に、貪欲法は「わかってる」と自己認識してスルーしていたが、現実には「貪欲法で解けると確信した後の実装はできる」「貪欲法で解けると気付く、証明するところが弱い」なので帰着する力の切り口では「わかってない」
        • 貪欲法の証明パターン
  • 難易度帯で淡々とやっていくのに飽きた
    • 達成感が得られないからな
    • 解説記事からリンクされてる問題を解くことにした

done

難し目の問題

AGC031B AGC022B AGC032B

Graph View

Backlinks