B - Balls of Three Colors(ARC128)

問題

感想

わかりませーん。緑diffですが、解けませんでした。「同じ数字が二つ生まれればいける」みたいなところも気づいたが、全く気にも留めずにスルー。こういうのって日頃から頭を使っていない証拠なのだろうか...

解法

まず、Ｒ,G,Bの組み合わせで同じ数字の組み合わせを作るというところをゴールにどうすればよいのか考える。ボールの個数の遷移を考えると(-1,-1,+2)みたいな動きしか生まれない。つまりは二組のボールの差は3しか変化しない。（お互いに-1,-1ずつで差はひらかないパターンもあるがそこは問題にならない）
ということは、二組の数字を同じ数字にするためには差が3の倍数でなければならないというところが見えてくる。なので、まず実現可能かは3の剰余が0であることを確認すればよい。
次はその回数について。
実はよくよく考察すると(0,10,7)みたいなときには(-1,9,9)みたいな遷移を避けるため(1,9,6)みたいなものを一度挟むみたいな処理を特段考慮する必要はないということがわかる。
以下、（R,G,B）としＲをそろえる場合を考える。結構がばがば解説なのであてにしてはいけない。

G>=Rの時

これは素直に行けそうかなと思います。上記の考え通りに行う。

G<Ｒの時

要は二組の数字を最小回数で同じものにそろえる場合、動きうるボールの遷移は以下の二通りを決まった回数回行う。

（R-1,G-1,B+2）
（R+2,G-1,B-1）

ここで、最小回数について考慮すると結局は１と２の回数は決まっているということに気づく。もし、操作順ならこの部分も考慮しないとですが今回はあくまで回数のみ
丁寧に解説するなら、例とか挙げるべきですがちょっとお疲れ気味なのでいったん端折ります。
ともすると、この上記二つのパターン分けをする必要もなさそうなので、あとは数えていきます。

さて、結局は

どのボールに合わせるかを決める
残りのボールが3の倍数差か確認する。
上記を満たす場合、同じ数字にそろえるまでの回数　と　すべてを一つのボールに変更する回数　を足す。
これをそれぞれのケースで3通りずつ試していく。その最小値を記憶して出力

といった感じになる。
同じ数字にそろえるまでの回数:差は３ずつ埋まっていくので、(X-Y)%3回分（X,Yは最終的にはすべて同じボールに変換される色のボールの個数）
すべてを一つのボールに変更する回数:二つのボールの合計値の半分。
以上を計算して、最小値を算出、出力すればOK

感想

システマチックに考えたいです