典型力
問題が部分的にしか与えられない状況で、解を導くための部品を列挙できる能力
まず自分で考えてから違いを見た方が良さそう
考えたこと
同じ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
小さい値の操作をしてから大きい値の操作をしても意味がないから
僕の解法は1〜xを使って解くことができるかを確認していた
この時に最短解も見つかることを期待したがそれは誤りであった
「1〜xで解くことができるかの判定」という部品を少しいじって「集合Sで解くことができるか」とすると有用
「1〜xで解くことができ、1〜x-1で解くことができない時、xは必須」
この部品を公式解説ではBFSもしくはDFSでやってる。僕の方法はBFSに相当。
chokudai解説
だいぶ細かく分割されているイメージ
問題文自体も分割と抽象化が行われている
問題を「問題より小さなコンポーネントの組み合わせ」と認知することで、初見の問題でも「既知のコンポーネントの組み合わせ」と捉えることができるようになっている
僕が「問題変換」と考えてた時は、問題全体を一つのコンポーネントとして認知していた そうではなく、まず問題を分割して認識することが重要
順序がなんらかの方法で決まるので、いくつ訪問済みかだけでOK