http://codeforces.com/contest/786
http://codeforces.com/contest/787
A. The Monster
http://codeforces.com/contest/787/problem/A
t回目にAさんはb+ta秒に叫び、Bさんはd+tc秒後に叫ぶ。
同時に叫ぶのは最短で何秒後か。
B. Not Afraid
http://codeforces.com/contest/787/problem/B
N宇宙からAさん,Bさんがそれぞれ来る。
それぞれ、どちらかが嘘つきでどちらかが正直者である。
Mグループあり、全員が嘘つきになりうるグループがあるなら"YES"、無いなら"NO"
C. Berzerk / A. Berzerk
http://codeforces.com/contest/787/problem/C
http://codeforces.com/contest/786/problem/A
2人でゲームをする。
それぞれ使えるカードが決まっており何回でも使える。
0～N-1個の数字が昇順に円状に並んでいる。
AさんBさんのどちらかが先攻で、初期位置が1～N-1の全てのパターンについて、先攻がWin, Lose, Loop（最適に動かすと勝敗がつかない）のどれかを答えよ。
ゲームは以下のように進行する
- 位置がxであるとする
- (自分の手持ちのカードのある数 + x) % Nへ移動可能
- x==0へ移動させることが出来たプレイヤーが勝ち
D. Legacy / B. Legacy
http://codeforces.com/contest/787/problem/D
http://codeforces.com/contest/786/problem/B
1～Nの頂点があり、以下のクエリに従って有向辺を付けていく
1. 頂点vから頂点uへコストw
2. 頂点vから頂点[l,r]へコストw
3. 頂点[l,r]から頂点vへコストw
頂点Sを始点として各点の最短距離を求めよ
E. Till I Collapse / C. Till I Collapse
http://codeforces.com/contest/787/problem/E
http://codeforces.com/contest/786/problem/C
N要素の配列Aがある。
これを連続する要素毎にグループ分けすることを考える。
各グループ最大でもK種類の数を含むことができるようにして分けるとして、最小何グループに分割できるか。
K=1...N全ての場合について答えよ。
以下、解説
A. The Monster
http://codeforces.com/contest/787/submission/25763777
b+ta=d+sc
ta=d-b+sc
t=(d-b+sc)/a
なので、sを全列挙して最も小さいやつを計算して答えるだけ。存在しないなら-1を出力。
B. Not Afraid
http://codeforces.com/contest/787/submission/25813457
全員嘘つきにすることが出来ないのは、同じ宇宙から来た人が2人とも同じグループに属している時。
全てのグループについて、それをチェックすればよい。
グループ内に同一人物が複数いる可能性があるので注意。
C. Berzerk / A. Berzerk
http://codeforces.com/contest/787/submission/25815652
dp[p][x] := プレイヤーpが数xの時に勝つ(1)負ける(-1)ループ(0)
を構築していく。
BFSでdp更新をする珍しいパターン。
ゲーム問題でよくある「遷移先に負けが1つでもあれば勝ち、さもなければ負け」を少し拡張して解く。
「遷移先に負けが1つでもあれば勝ち、遷移先が全て勝ちなら負け、さもなければループ」
これを愚直に計算するだけだが、変化しなくなるまで全体更新をループさせるとTLEする。
TLEコードhttp://codeforces.com/contest/787/submission/25815055
これをBFSで処理して上手いこと判定する。
BFSのキューにはdpが更新された要素番号が入る。
こうすることでBFSの内容はdpの要素数分しか入らないので、BFSの中身がO(N)なのでO(N^2)で間に合う
D. Legacy / B. Legacy
MLE解法 : http://codeforces.com/contest/786/submission/25816278
区間頂点に辺を全部貼るのは無駄なので平方分割を用いて、一気に辺を張っていく。
が、これをやるとMLEするのでダメ。
本当の解法は区間頂点に辺を貼るのにセグメントツリー的なやり方を用いる。
もう、本当の解法を書く気力は残っていなかった。
https://kimiyuki.net/blog/2017/03/24/cf-786-b/
E. Till I Collapse / C. Till I Collapse
http://codeforces.com/contest/786/submission/25820652
ei1333さんの解法がすごい http://ei1333.hateblo.jp/entry/2017/03/26/192743
天才かよ。
まず2つの事実に気づかないと解くのは難しいのだが、
1. Kが増加するにつれて答えは広義単調減少する
2. 答えとなる数の種類はO(√N)
1番はまあ良いとして、2番目はどうやって気づくんだろうか。答えが疎になることを見抜く。
つまり、同じ数が連続して現れることが多いということ。
rec(L,R) := K=[L,R]の場合の答えを計算する関数
もし、K=Lでの答えとK=Rでの答えが同じであれば、その区間は全部その答えになる（こういう所で計算量が大幅に削減できる）。
違うならば、中心のK=md=(L+R)/2について答えを計算して、残りの計算はrec(L,md)とrec(md,R)に任せる。
ほぼ二分探索的だが、枝刈りがすごくできるのでこの手法で間に合う。
あとは、任意のKについて高速に答えを出したいのだが、setを使うとO(NlogN)でこれだと間に合わない。
尺取り的な手法でO(N)で計算できる方法があるので、それを用いる。
(ei1333さんのやつ見て初めて知った。すごい)
