2017.01.28 Saturday
ABC053 4AC!
競技プログラミングコンテスト3回目。初めて全問解けた!
今回はごりごり実装というよりはじっくり考えることによって非常にシンプルなコードに落とし込めるという感じだった。
それほど新しく得たものはないけど、std::stringの扱い(検索とか)はチェックしといた方がいいなと思った。
問題Dをどう解いたか書いとく。
問題文
すぬけくんはカードゲームで遊ぶことにしました。 N 枚からなるカードの山があり、上から i 枚目のカードには整数 Ai が書かれています。
すぬけくんはこのカードの山に対し 0 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、N は奇数であり、少なくとも 1 枚のカードを残すことが可能であることが保証されます。
操作:カードの山から任意の 3 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード 1 枚と最小であるようなカード 1 枚の合計 2 枚を選んで食べる。その後残った 1 枚をカードの山に戻す。
制約
- 3≦N≦105
- N は奇数
- 1≦Ai≦105
- Ai は整数
最初にソートして数iの枚数niを算出する。
niが3以上の奇数ならそのカードのみ3枚選べば2枚消せる。-2, -2…を繰り返していけるので最終的に1枚に出来る。つまりniが奇数のものは1枚に出来る。
niが偶数のものも-2, -2を繰り返して2枚まで減らせる。2枚にしたら、その2枚と他の数のカード1枚を消して1枚消せる。つまりniが偶数のものが2つあれば両方を奇数に出来るので偶数ペアも1枚に出来る。
最後に偶数枚のカードがペアにならずに残っていたら1枚になっているカードを犠牲にして消さざるを得ない。
まあこういう感じの考え方。
ひとつ収穫があった。
数列中に含まれる各数の個数をカウントするときに数列をソートしてやったんだけど、他の人のコードをみたら
count[10001]={0}を用意して数列を走査しながらcount[n]++を繰り返してた。
なるほど、数列に現れる数の上限が小さければこういうことが出来るのか。
業務ではあんまりこういうことはしないよなー。