Atcoder: D - Alter Altarのアルゴリズム

Alter Altarの問題ですが

Python
1n = int(input())
2C = input()
3print(C[:C.count('R')].count("W"))

で解けるみたいなのですがアルゴリズムがよくわかりません。
どうしてRの個数までの部分配列の中のWの数を求めると最小回数になるのでしょうか？

行動規範の内容に同意します

回答2件

ベストアンサー

最終的な石の並び順が「赤い石は左側に、白い石は右側に集める」状態（つまり、RR...RRWW...WWW）にならなければならないことについては、swordoneさんのご回答およびAtCoder公式解説のとおりです。

それを前提とした上でご説明します。
なお、以下はどちらかというと直感的な説明であり、数学的に厳密な証明にはなっていないかもしれません。

まず、問題文では、

入れ替え：石を2個選び (隣り合っていなくてもよい)、それらを入れ替える。
色変え：石を1個選び、その石の色を変える (赤なら白に、白なら赤に)。

の2つの操作が定義されていますが、この問題においては、実は、色変えの操作は無視することができます。

なぜなら、「任意の色変え操作について、それと比較して同等またはより有利な（＝最終的な手数が増えない）入れ替え操作が存在する」ということが言えるからです。

具体的には、例えば、「ある赤い石（Xとする）を一つ選び、その石を白に変える」という操作を行う代わりに、「赤い石Xと、Xよりも左にある白い石Yを入れ替える」ことにしても、不利になる（最終的な手数が増える）ことはありません。
（この点について、私も厳密な証明はできないのですが、色変えの代わりに入れ替えを行うことにより、「赤い石X（の位置にある石）を白に変える」ことに加えて「左にある邪魔な（白い石はなるべく右にあったほうが最終形に近づくという意味で、左にある白い石は邪魔です）白い石Y（の位置にある石）を赤に変える」ことを同時に達成できるので、同等またはより有利になる、と考えると直感的には分かりやすいのではないかと思います。）

なお、白い石を赤に変える操作についても、上記と同様のことが言えます。
また、赤い石Xよりも左に白い石が一つもない状態であれば、そもそもそのようなXに対して操作を行う必要がないので、そのような場合を考える必要はありません。

以上を踏まえ、入れ替えの操作のみで、「赤い石は左側に、白い石は右側に集める」状態を達成する方法を考えます。
すると、操作の前後で赤い石及び白い石のそれぞれの総数は変わらないことになるので、「左から順に初期状態における赤い石の総数個だけ赤い石が並び、その右に初期状態における白い石の総数個だけ白い石が並んでいる」状態が最終形であることが分かります。
したがって、各手番ごとに「左から赤い石の総数個の範囲からはみ出している赤い石（Xとする）」を1つ選び、赤い石Xを「左から赤い石の総数個の範囲に存在する白い石」と入れ替える操作を行っていくのが最善となります。

ここで、

1度の手番で「左から赤い石の総数個の範囲からはみ出している赤い石の数」を2以上減らすことはできない
逆に、各手番において上記の操作を行えなくなることはない（なぜなら、上記の操作を行えないということは、どの赤い石についても自分より左に白い石が存在しない状態になっているということにほかならず、それはつまり最終形に到達しているということなので）

ということが言えます。

したがって、最適な操作を行ったとき、各手番ごとに「左から赤い石の総数個の範囲に収まっていない赤い石の数」は1ずつ減っていくことになるので、「Rの個数までの部分配列の中のWの数」（これは、「左から赤い石の総数個の範囲からはみ出している赤い石の数」と一致します）が操作の最小回数に一致します。

投稿2020/08/03 05:00

編集2020/08/03 05:19