Codeforces Round #578 (Div. 2)
21:35~の健康コドフォありがてぇてぇ
A. Hotelier
問題：10個の部屋で、客の出入りを記録したい。以下はクエリの説明
L：一番小さい部屋で空いている部屋に客が入る
R：一番大きい部屋で同上
x：整数ｘの部屋から客が出る。
考察：
長さ10の配列をもって愚直に更新していけばよいです。O(10N)
B. Block Adventure
問題：N列に、それぞれhiのブロックがある。ブロック1の上からNの上に行きたい。隣のブロックの上には高さの差がk以下のとき移動できる。また最初にｍ個ブロックを持っていて、自分が乗っている列のブロックは増減できる。最後までいけるか判定せよ
考察：
次のブロックの高さ-kまでなら減らしてよいです
また足りなければブロックを置く必要があります
簡単な実装として
m+=h[i] - (h[i+1] - k)
とできます。
このとき小さくとも0までしか減らせないので、
m+=h[i] - max(0 , h[i+1]-k)
とする必要があります。
C. Round Corridor
問題：円の内側がN個、外側がM個に区切られている。外側と内側に壁がないとして、部屋xとyが連結かQ個のクエリに答えよ
考察：
まず、1周をなにかの長さで表し、壁の位置を整数に変換しようとします。
このとき1周の長さは最小公倍数lcm(n,m)です
しかしこれではオーバーフローしてしまいます。
壁がある位置はlcm(n,m)/n と lcm(n,m)/mのみです。これはgcdで表せそうです。
x/gcd(n,m),y/gcd(n,m)などが独立な範囲番号になるため、これが一致するかを判定すればよいです。
D. White Lines
問題：N*Nのグリッドの一部分が黒で塗られている。K*Kの範囲を1つ選び白で塗りつぶすとき、全て白になる行と列の個数を最大化せよ
考察：
二次元累積和を使って解くことができます。
ある行を白にするためにK*Kの左上がなければならない範囲
この範囲を全ての行と列で求めて二次元累積和を取り最大値がO(N^2)で求まります
元々白い行や列はカウントしておきましょう。
上の範囲が具体的にどうなるか考えます
ある行ｉを見て、一番左の黒と、一番右の黒だけ見ればよいです。
それぞれｘ0、ｘ1とすると
imos[i-k+1][x1-k+1]++;
imos[i-k+1][x0+1]--;
imos[i+1][x1-k+1]--;
imos[i+1][x0+1]++;
こうなります。x1-x0+1＞kなら実現できないため飛ばしましょう。
コツはお絵かきだと思います。
E. Compress Words
問題：N個の文字列Siをマージして最小の長さにしたい。Siの最後の部分とSi+1の最初の部分が一致すればマージできる。詳しくはコドフォのページを見てください
解説：
接頭辞との一致ということでZ-Algorithmを使いました
既にマージした文字列をansとします。
str=Si+'$'+ansをZ-Algorithmで一致箇所を求め、最長のところでマージを行えばよいです。
しかしこれでは計算量が全体の長さ^2かかってしまします
以下Twitterで見た解法
一致する長さは最大でもSiなので、ansの後ろSi文字をstrに追加すればよいです
こうして全体の長さの高々2倍で解くことができました。
感想：
明らかに要らない部分を切り捨てて計算量削減って感じでしょうか。
こういうパターンはよく見る割に自分じゃ全然思いつけないので要反省です。
マージテクの典型って感じなので是非覚えたいですね。
大きさを小さい方に合わせる
F. Graph Traveler
問題：いま持っているスコアをｘとする。Ｎ頂点の有向グラフで頂点ｉにたどり着いた後行くことのできる頂点はei[(x+k)%m[i]]で表される。各クエリで与えられた初期頂点、スコアで、閉路にたどり着いたとき、その閉路の大きさを求めよ
考察：
状態がm[i]個ありそうなので拡張します
ただしこれは嘘で、m[i]=2、m[i+1]=3のとき、1と3で色々と状況が変わることがわかります。
これに気づくのに結構時間かかっちゃったのがまずかったですね。
ではどう拡張すればよいでしょうか。m[i]は1~10なので1~10のlcm分拡張すれば十分そうです。
辺は高々頂点数分で、かなりシンプルなグラフになります。
k足すなどしてうまく調整して辺を張って、各頂点から動いて閉路を見つけ数えればよいです。
ただし閉路の状態数ではなく頂点の種類を数えることに注意しましょう
サンプル合わず死亡。さよなら。
※ 追記
辺の作り方で、mod m[i]を参照みたいな感じにしたんですけどシンプルにできたので変えました。通りました。
inputを先に終わらせてから色々した方が考えること減って良いですね。
感想
45分4完で結構良い順位でした～
そして、紫になれました！うれしいー
AtCoderのほうがかなり停滞気味なのでCFでレート上げられているのは助かってます。
ただこれもそろそろ頭打ちになりそうです…
今日の問題セットに関してですが、Dは実装重かった割にすんなり書けたので良かったと思います。
Eは典型考察としてしっかり覚えます。Fは考察できていたけど実装でつまづいたので要練習です。
結構学びある良いセットだったと思います。やっぱりCFは最高っすね～
暖色目指してがんばろーオー
