Pythonで解くAtCoder(ABC174:D)
こんにちは、クルトンです！
この記事では
AtCoderの「AtCoder Beginner Contest 174」のD問題をPythonを使って解説します。
問題のリンクを載せておきます。
解法
解説が分かりやすかったので、解説を参考にしてください。
別解
ふゆるさん(@Fuyuru_yumemin)の解法が非常にシンプルで面白かったので、紹介させていただきます。（ふゆるさん、ブログで紹介することを快く許可してくださり、ありがとうございます！）
まず
- 石を2個選び (隣り合っていなくてもよい)、それらを入れ替える。（以下「操作1」とする）
- 石を1個選び、その石の色を変える (赤なら白に、白なら赤に)。（以下「操作2」とする）
の二つの操作の内、操作2が必要ないことを示します。
まず、赤い石のうち一つを白い石に変える操作について考えます。
このとき、この石よりも左に白い石がない場合と、ある場合の2パターンに場合分けすることができます。
この石よりも左に白い石がない場合、この石よりも左側には赤い石しか存在しないため、この操作を行う意味はないことになります。
この石よりも左に白い石がある場合、この石とその白い石を入れ替える…①ことでこの操作を置き換えることができます。
また、操作2を使うと同時に2箇所の色を変えることができるため、①のほうが石の色を変えるよりも効率が良いことが分かります。
同様にして、白い石を赤い石に変える操作についても同じことが言えます。
以上から、操作2は必要がないことがわかります。
操作2が必要ないことが分かったので、操作1だけを使って考えます。
このとき、操作1は2つの石を入れ替えるだけなので、赤い石と白い石の個数が変わらないことが分かります。
よって、赤い石がR個、白い石がW個とすると、左から赤い石をR個ならび、つづいて白い石がW個ならんでいる状態が操作の終了後の状態になります。
またこの図から、左からR+1個目以降に含まれる赤い石の数が操作の回数に等しいことが分かります。
以上から解答はこのようになります。
まとめ
今回は
- 仕切りを使って考える
- 操作2が必要ないことに気づく
という問題でした。
ではまたお会いしましょう！さようなら～
