http://agc011.contest.atcoder.jp
以下、解説
A. Airport Bus
http://agc011.contest.atcoder.jp/submissions/1156216
貪欲にバスに乗せていく。
まず、到着時間をソートしておく。
バスにその人を乗せるが、
- バス1人目であれば、そのバスの限界待機時間limitをA[i] + Kとしておく
- バスに乗るときに、そのバスの限界待機時間を超えているか、乗員制限を超えているならば、そのバスは出発させて、次のバスの1人目とする
これを到着順からシミュレートする
B. Colorful Creatures
http://agc011.contest.atcoder.jp/submissions/1156722
二分探索+貪欲法で解く。
以下、大きさはソートされているとする。
bool chk(int i) := i番目の生き物が最後の1匹になれるか
大きさはあるサイズを境として最後の1匹になれるかどうかが分かれる。
なので、何番目の生き物までが最後の1匹になれるかを二分探索して求める。
chk関数の実装は貪欲法で実装していけばよい。
i番目の生き物に小さい順で生き物を合わせていって、合わさらないならなれないとする。
C. Squared Graph
http://agc011.contest.atcoder.jp/submissions/1159180
頑張って考察する。プロはなぜ早いの？
まず、無向グラフを連結成分に分ける(divide関数)
そして、各連結成分を「孤立点,二部グラフ,それ以外」に分ける。
二部グラフの判定は2色の彩色問題であるので、dfsで貪欲に塗っていって矛盾すればダメみたいにする。
この個数をカウントして配列cntを作る
- cnt[0] := 孤立点
- cnt[1] := それ以外
- cnt[2] := 二部グラフ
すると答えは「N * N - (N - cnt[0]) * (N - cnt[0]) + (cnt[2] + cnt[1]) * (cnt[2] + cnt[1]) + cnt[2] * cnt[2]」となる。
完璧に投げやりなんだけど、考察というか実験するとそうなった。
（本番は二部グラフを木と考えて死んだ）
www.youtube.com
解説放送を見ましょう。とても分かりやすいです。
D. Half Reflector
http://agc011.contest.atcoder.jp/submissions/1159508
シミュレーターを書いて結果を見ると操作に規則性がある（俺は書いたけど分からんかった）
以下に従って操作を行っている
1. 先頭が'A'であれば先頭を'B'にする
2. そうでないなら、全体を反転 → 左に1つシフト(溢れは消す) → 末尾に'A'を足す
最終的にBABABABABAみたいになれば結果が収束していく。文字列が奇数個であれば、ABABA -> BBABA -> ABABA -> ... のように振動する。
結果が収束するまでに要する回数は最大2N回くらい（間に合う）
なので、結果が収束するまでシミュレーションをすれば良いのだが、愚直にやると毎回O(N)くらいかかってダメなので、効率良くやる。
文字列をdequeに入れておく。
deqはまだ処理が終わっていない文字列。
cntは何回目の処理をしたか。
revをdeque内の文字列が反転されているかに対応付ける（偶数なら非反転,奇数なら反転）。
doneは処理済み（ans末尾でABABAみたいになっている）の文字列数
まず処理をする前に右側が既にABABAの形になっていれば、deqから出して決定しておく。
次に変換をするが、deqの先頭を反転込みで見て、'A'ならば処理1、そうでないなら処理2。
処理1はdeqの先頭を反転するだけ。
処理2は「全体を反転」は「rev++;」に対応、「左に1つシフト」は「deqの先頭を削除」に対応、「末尾に'A'を足す」は「ansに1つ確定」に対応する。
処理回数がKと等しくなったら処理を中断してdeqをansに入れて出力。
収束パターンになったら、文字列が奇数で残りの試行回数が奇数ならば、振動パターンの先頭Bなので、それに変更して出力。
E. Increasing Numbers
http://agc011.contest.atcoder.jp/submissions/1159606
解法はyoutubeで見た解説を書いた。答えを二分探索する。
bool chk(k) := k種類以下の増加列でその数を表現できるか
「(9N+Kの各桁の総和) <= K」の真偽が表現できるかに一致する（詳しくはyoutubeへ）。
（不等号になってるのはkってのはある程度微調整できる（多分そういうこと（にしておこう）））
あとは、Nは超デカイ数なんで、C++だと専用に処理を書かないといけない。
9倍(関数mul9)と和(関数add)だけなのでそんなに難しい処理でもない。
