典型力

競技プログラミングの強みと「典型力」について - chokudaiのブログ 帰着する力と呼んでたものに近い

問題が部分的にしか与えられない状況で、解を導くための部品を列挙できる能力

まず自分で考えてから違いを見た方が良さそう AGC022C

• 考えたこと

  • 同じkについて複数回操作しても無駄
  • kの最大値Mがよほど小さくない限り全探索は無理
  • 操作の順序は結果に影響するので無視できない
    • なんらかの貪欲法などで決まる？
  • 例えば9を3と5で割る
    • 3で先に割れば0
    • 5で割って止めれば4
    • 5で割ってから3で割れば1
    • 割らなければ9
    • 素である場合には倍々で可能性が増える
  • 大きい方を先にやると仮定してOK？
  • 逆にどういう時にできない？
    • 元の数より大きくはならない
    • 元の数の半分以上の数にはなれない
  • コストが2^kであることの効果
    • x+1で一回操作するよりx以下で全ての操作をする方が安い
    • コストの安い順の探索が小さい方から選択肢を追加していくことに一致する
  • ゴールから逆算
    • 2で割る前を考える
      • ゴールがx<2である時、一歩手前は2n+x
      • スタートの半分よりも大きいものは考えなくて良い、到達不能だから
    • 次のステップで3で割る前を考える
      • 3より小さいものだけを考えれば良い(3以上の値が3で割ったあまりとして現れることはない)
    • 到達可能な数をエラトステネス的に塗っていって、スタートの数が塗られたらその数については今後考える必要はない
    • 全部のスタートが塗られたらOK
    • これで計算量度外視で最適解の有無の判定はできた
  • 問題の制約、Nが50、Mも50、割と小さい
    • 50個の数のそれぞれに50のエラトステネス的テーブルをつけてもOK
    • 最悪でも50^3にはならないから余裕だろう
  • 「テーブルに印をつける」をコストの書き込みによって表現する
    • 最短経路問題っぽさがある
    • コスト安い方から探索してゴールまでの距離が確定したら終わる的

• 公式解説確認

  • 僕の解き方じゃダメ
    • ゴールに辿り着く経路が異なるケースがある。100と011でゴールに辿り着く場合、単純にorを取ると111になるが、最短の011の他に110でも辿り着ける可能性があり、その場合の全体の最短は110
  • 2回やっても意味がない
  • 最適な操作の順番が一位
    • 小さい値の操作をしてから大きい値の操作をしても意味がないから
  • コストが2^k→辞書順最小
  • 僕の解法は1〜xを使って解くことができるかを確認していた
    • この時に最短解も見つかることを期待したがそれは誤りであった
    • 「1〜xで解くことができるかの判定」という部品を少しいじって「集合Sで解くことができるか」とすると有用
    • 「1〜xで解くことができ、1〜x-1で解くことができない時、xは必須」
      • 1〜xで足りて1〜x-1で足りない時xは必須
    • この部品を公式解説ではBFSもしくはDFSでやってる。僕の方法はBFSに相当。

• chokudai解説

  • だいぶ細かく分割されているイメージ
  • 問題文自体も分割と抽象化が行われている
  • 問題を「問題より小さなコンポーネントの組み合わせ」と認知することで、初見の問題でも「既知のコンポーネントの組み合わせ」と捉えることができるようになっている
  • 僕が「問題変換」と考えてた時は、問題全体を一つのコンポーネントとして認知していた
  • そうではなく、まず問題を分割して認識することが重要
  • 問題分割

• 状態情報の圧縮

  • 順序がなんらかの方法で決まるので、いくつ訪問済みかだけでOK