ARC128感想戦

🎵

大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128） に参加しました。2完でレートは下がっちゃいました。考えていたことなどを書いていきます。

A問題よりB問題のほうが考えやすく感じたので、Bから考え始めました。

R, G, B の個数を小さい順に並び替えて、a, b, c とおきます。最終的に 0, 0, x みたいになるとすると、その直前は 1, 1, x-2 となっていなくてはいけないので、なんとかして、3つのうち2つを同じ個数にしないといけないことがわかります。

例えば、a, b を同じにすることを目指すなら、a, b, c を a+2, b-1, c-1 に変化させるのがいいです。a と b の差は3ずつ縮まるので、差が 3の倍数でないときは無理です。3の倍数なら、 (b-a)/3 回操作をすればよく、このときに、もともと a, b だった値は同じ値になっています。

さらに、これらを両方 0 にするには、-1, -1, +2 と変化していけばいいです。ここで、もともと b だったものに注目すると、毎回の操作で個数が1個ずつ減るので、操作の回数は b回。これより少なく b を 0 にすることはできないので、aとb の個数を同じにできるなら、これが最小だとわかります。

後は、aとc、bとcも同じようにすればいいです。差が3の倍数だったら小さい方を+2、大きい方を-1していけばいつかは同じになります。

ただ、ここで、僕は「残りの色を -1 していったときに、0以下になると困るんじゃないか」と思っていました。例えば、「2 10 40」とかだった場合、単純に後ろ2つを合わせに行くと「-8 30 30」となってしまいます。

この場合に、「負になる場合はできない」などと勘違いして、何度かWAを出してしまいました。

実際には、マイナスになりそうなら、増やす操作をすればいいだけです。先ほどの例だと、「+2 -1 -1」の操作を最初に4回やれば「0 26 26」となります。ここから、26を0にする操作をやればいいです。操作回数は、cの動きに注目すると、毎回1ずつ減るので、c回です。

結局、b-a が3の倍数ならb回、こうならない場合で c-a か c-b が3の倍数ならc回、それ以外は無理、となります。

うーん、わかってから振り返ると簡単だけど、なかなか頭が回らなかった。

Aも結構解かれていたので、頑張って解こうと考えました。数がでかく・小さくなっていくので、どう管理すればいいのか、直感的に謎でしたが、具体的に考えればすぐにわかりました。

まず、i日目の時点で、金と銀の量を (g, s) と表すと、操作の内容から、(a, 0) か (0, b) の場合しかありません。

0日目、操作するかどうかで、(1 0) か (0 A0) のどちらかがありえます。（0-indexed で考えます）

1日目は、上の図にある通り、0日目で操作しなければ (1 0) か (0 A1) となり、操作していれば (0 A0) か (A0/A1 0) となります。

いずれにせよ、A0 が A1 より大きければ 0 日目で操作したほうがいいです。

それ以降も、そこまでで操作した回数が偶数回か奇数回かによって、「前回操作していた方が得かしてない方が得か」を判定していけばいいです。最終回は、金に換えないといけないので、操作回数が奇数回のときだけ、追加で操作します。

結局、この2問を解くだけで2時間くらいかかって終了でした。