はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Grand Contest 011 解説

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)だけなのでそんなに難しい処理でもない。

Fは提出状況見た感じもうちょっと強くなってから