pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Grand Contest 012 A: AtCoder Group Contest

http://agc012.contest.atcoder.jp/tasks/agc012_a

解法

入力を昇順にソートして考える。

適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。

_o__o__o__o_
000111222333

oになっているのが中央値。

これは改善ができる。

_o__o___o_o_
000111232233

改善の雰囲気から最適構造が見える。

____o_o_o_o_
012300112233