Toy と帽子と ADP BE

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

大和証券プログラミングコンテスト2021(AtCoder Regular Contest 128)

2完4WA。水パフォだけど、いろいろ難しく考えすぎてしまい、ちょっと負け気分・・・。

各問題

A - Gold and Silver

Aが大きいとき銀に交換して、Aが小さい時金に変換するのが得なので、Aが極大値のとき銀に変換、極小値のとき金に変換を貪欲にやればよかったりします。 最後金で終わらないといけないことに注意。

似たような問題がAtCoderCodeforcesに(あるいは両方)あったような気がします。

難しく考えすぎて

B - Balls of Three Colors

まず、どれかひとつだけを残そうとしたとき、それ以外の2つを同じ数にする必要があります。同じ数の2つを選び続ければ両方同時に0になるからです。

また、選んだ2つは1減り残った1つは2増えるので、差し引き3となります。なので、どれか2つを同じ数に揃えようとした場合、それらの差は3の倍数である必要があります。

というわけで、R, B, Gから2つを選んだの3つの組の中で、差が3の倍数のものがなければ永遠にすれ違い続けるため答えは-1です。

3の倍数のものがあればその組は答えになりえて、最終的に両方を0にする必要があるので最小の操作回数は2つのうちの大きい方です。これを3つの組全てに対して考えて、一番小さいのもが最終的な答えとなります。

自分は最初、必要ない条件を加えていて無駄に3WA出してしまいました。(例えば{1, 15, 21}のとき、21 - 15 = 6 でこれを平たくするのに2回かかるが、もう1つが1なので、その操作が不可能だと思っていました。そのケースだと、{3, 14, 20} -> {1, 18, 18} とかすればいいんでね。)

C - Max Dot

前の方は0でよく、後ろの方を最適な個数でS/mをm個並べるんだろうということはなんとなくわかりつつ、Mの条件があるときどうするかと最適な個数をどこに取るかがわからず・・・。

まとめ

うー、Aで詰まるのちょっともったいなかったし、Bでつけなくてよい条件をつけてしまっていたのもかなりもったいなかった。

まあ水パフォなのでよしとしますか。

f:id:mdstoy:20211016232423p:plain