Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 166

2完

各問題

A - Replace C or Swap AB

'C' は 'A' や 'B' に変えることはできても移動させることはできないので、Y_i が C のとき X_i が C でなければ一致させることはは不可能です。よって、以下 Y について C である場所は X についても C であるときについて考え、さらにそれらで各文字列を区切った部分文字列ごとに考えることにします。

それぞれの部分文字列について、Y の B の数が X の B の数より少ない場合無理なことは自明です。また X の BC を足したものが Y の B の数より小さい場合も C をすべて B に変えても足りないので一致させることは不可能です。よってこれらのケースも以下では除外します。

操作(3) によって B の位置は左に動かすことはできますが、右に動かすことはできないため、X = BA, Y = AB のように右から見てYの方にだけBが先に出現するような文字列の場合一致させることは不可能です。ここで X の初期状態にについて B はできるだけ右にある方がよいため、X の B の数が Y の B の数より小さい場合、足りない分をより右にある C から B に変えることで補います。(残りの CA に変換します)

あとは、それぞれを右からみていって、Y における B の累積数が X における B の累積数を越えなければ一致可能ということになります。

ちなみに、X と Y の最後に C を付加すると実装が楽になります。

B - Make Multiples

前処理として、A_i にたいして、a の倍数、b の倍数、c の倍数, a と b の公倍数、a と c の公倍数、b と c の公倍数、a と b と c の公倍数にするためにいくつ足せばよいかを求めます。(それをソートしておきます)

次に、あらゆる組み合わせについて最小の操作回数を求めて、もっとも小さいものが答えです。a の倍数、b の倍数、c の倍数のときとか、a と b, c の公倍数のときとか a, b, c の公倍数のときとかいろいろありますし、順番もすべて試す必要があります。(雑

まとめ

B が方針を立てるまでにかなり時間をかけてしまった。しかも実装が若干嘘っぽいのでいいのかこれ?と思いながら投げたら通ってしまいました。各倍数について上位 3 つ以内の組み合わせをすべて試す必要があるように思うのですが、そうはできてなかったんですよね...。どうなんでしょ?