Toy と帽子と ADP BE

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

AtCoder Regular Contest 147

2完2WA1RE。

各問題

A - Max Mod Min

multisetを使って愚直にシミュレーションすればよいです。

multiseterase(int)を使ってしまい、1WA。何年c++で競プロやってんですか...。

(追記)

これc++の暴力で通ったらしいです。A mod B < Bなので、最初にソートしてdequeに入れて、A_k mod A_1 != 0なら先頭に入れる、を繰り返せばよいそうです。なるほど...。

(追記ここまで)

B - Swap to Sort

まず、操作Bではスワップしても位置の偶奇が変わりません。操作Aではお互いの位置の偶奇が入れ替わります。

ある奇数が偶数位置にある場合(偶奇逆ももちろん)、操作Aが最低1回必要となります。ここで、奇数が偶数位置にある場合、それに対応する奇数位置にある偶数が存在します。そして操作Aの回数を最小にしようとするとそれらを入れ替えるのが最適なので、操作Aの最小回数は偶数位置にある奇数の数です。

その実装はいろいろあるでしょうけど、N < 400に対して操作の合計回数は105回まで許されているので特に神経質にならずとも達成可能です。

自分は、まず奇数位置にある偶数と偶数位置にある奇数を操作Bで先頭に集めて、集めたものを操作Aで適切な位置に戻し、最後に操作Bでバブルソートしていきました。

さいしょ、雑にバブルソートだけをしようとしてWA、次に x -= 2 としたかったところを x-- としていてRE。(サンプルは通るし...。)

C - Min Diff Sum

まず不満度を効率良く求める方法がわかりませんでした。おわり。

まとめ

不用意なWAを出すのが相変わらずあれですが、まあ500点まで通せたのでなんとか。