ABC313 (第四回日本最強プログラマー学生選手権-予選-)
19分3完+1WA 1713th performance:1272
パフォがどろどろ溶けて死んでいる
A 2人目以降の最大値を取得し比較するだけ (21:01)
atcoder.jp
B グラフ探索っぽさがあるが、「誰かより弱い」という情報がない人間はすべて最強の可能性があるので、M個の情報から弱い人間を最強候補から外すだけでよい。 (21:04)
atcoder.jp
C multisetとかで貪欲にやるのかと最初考えたが、総和が変わらないことに注目すると、最終状態は「MがN-X個、M+1がX個」の状態になり、Mは平均（切り捨て）、Xは総和をNで割った余りである。とりあえず全部Mにする操作回数を求めて、Xだけ引いたが、WA。M以上の値であればM+1にするのは操作回数が1減るが、そうでなければ1増えるのでM以上の値の個数を求めて厳密に求める必要がある。(21:14->21:19)
atcoder.jp
D N+1回聞けるならいけるな～と思いながらあれこれして実装もグチャグチャになって時間だけが過ぎる。そこからEにいって時間が足りない、とかいう戦略ミス。
2つの質問で、1つの位置以外共通であるとき、その2つを比較することで異なる位置の数字が一致するかが分かる。K個質問することで、前K個の一致関係が分かる。このK個の和を質問することで、K個の値が確定する（1番目を0としてK個決めておき、その総和と答えが異なる場合、すべて反転させればよい）。残りについては、確定している数字K-1個と未知のものを聞いていくことで確定できる。
atcoder.jp
E 1以外の数字が連続するとき、操作は無限回になる。後ろから見て、i文字目について「その前の数字が1個になる」までの操作回数をDPする。i文字目が1の場合は+1するだけ。1以外の場合、「1をK個」挿入する操作が「それまでの操作回数+1」回行われる。1はK-1個ずつ増えるので、(K-1)(DP+1)個1が増え、Kが消えるのも含め(K-1)(DP+1)+1回操作を必要とする。
atcoder.jp
