AGC 011 B-Colorful Creatures
B - Colorful Creatures
良問だと思います. まず, N個の入力のクリーチャそれぞれに対してそれぞれ固有の色が割り当てられますが, それぞれ固有の色であり, 色の数値の大小に対して優劣をつける操作がないため, 色を無視して大きさ順にソートをしても問題ないことがわかります.
大きさ順にソートをすると, まずいちばん大きなクリーチャは明らかにすべてのクリーチャを取り込めることがわかります. では次に大きいクリーチャはどうでしょうか. 次に大きいクリーチャは, 一番大きいクリーチャを取り込む前に, 自分より小さなクリーチャをすべて取り込んでから大きいクリーチャと勝負（？）できます. その後で二番目に大きいクリーチャの大きさが, 一番大きいクリーチャの大きさの半分以上だったならば, 条件を満たせることがわかります. 条件を満たせなかった場合, 大きい方から三番目, 四番目...とそれ以降のクリーチャはどうがんばっても条件を満たすことができません. なぜならば, それ以降のクリーチャのサイズの上界は, その条件を満たすことができなかったクリーチャのサイズでおさえられるからです. 別の言い方をすると, それ以降のクリーチャのとりうるサイズは, 条件を満たせなかったクリーチャの部分集合になっています. 逆に, 条件を満たせるクリーチャを取り込むことができれば, すべてのクリーチャを取り込むことができることも示せます(そのサイズになれれば条件を満たすことはもう判定してあるから).
以上のことをコーディングすると, 累積和sum(クリーチャのとりうる最大サイズの下界になります)をあらかじめとっておき, 入力AをソートしてAの大きいほうから条件を満たすかどうかを見てカウントしていき, 条件を満たさなくなったら直ちにbreakして結果を出力すればいいことになります. 条件を判定するときは, 自分よりインデックスの1大きいものを取り込めるかどうかだけを見ればいいです. このアルゴリズムの計算量はソートがネックとなりO(N log N)となります.
単調性が成り立っているように見えるので二分探索ができそうな気分になってしまいますが, 前後のインデックスのみを見て判定するためには一つ大きい添字の要素が条件を満たしていることが前提となるため, 実はこのアルゴリズムでは二分探索を用いて探索することができません(計算量的には二分探索してもしなくても変わりませんが...). 気持ち的には自明に条件を満たしているA[N-1]から始めるDPになるのでしょうか.
