競技プログラミング用 知識集積所
ABC422D - Least Unbalanced
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
終状態が限られているので、バックトレースが有効。
例えば
3 10
という入力で考えてみる。
終状態は
10
という状況鹿ありえない。
その直前は
5 5
であると予想される。
その直前は
2 3 2 3
とか
2 3 3 2
のようなもの。
そして始状態は
1 1 1 2 1 1 1 2
といった感じである。
このような遡り方をすれば、絶対にアンバランスさが1以下にできることがわかる。
そして、この過程のどこかで奇数が発生した場合、アンバランスさを0には絶対にできない。
そして、この過程のどこかで奇数が発生した場合、アンバランスさを0には絶対にできない。
したがって、奇数が発生するかどうかをチェックしながらこの過程をコードにすればよい。
