Codeforces Round #571 (Div. 2)
batya
この回Writerの不手際かなにかでBがなくて、はえこんなことあるんだになりました。
Bなくて破滅しました。
A Vus the Cossack and a Conteststandard
やるだけです。文が短くて英弱にやさしい。
C Vus the Cossack and Strings
天才用問題。嫌い
問題：0と1で構成された2つの文字列s,tが与えられる。連続するsの部分文字列で、tと一致しない箇所が偶数になる個数を求めよ
考察：知らん
解説：
偶奇さえわかればよいことに着目します
もしある文字列の一致しない箇所がx個(0or1)だったとします。
このとき文字列の中身を入れ替えてもxは変化しません
例えば片方が00や11なら、当然入れ替えても変わりません。
なので01、01の組だけ考えればよいです。これは一致しない箇所が0か2なので偶奇は変化しません。
以上から文字列の順序は関係なく、1の個数（あるいは0の個数）のみで求まります。
tの1の個数をあらかじめ計算しておき、sの|t|個の1の個数を累積和などで求めればO(N)で解けます
感想：
難しいです。解説見たうえでもすんなり入ってこないというか。本番で思いつく気がしないですね。
偶奇に着目は当然として、入れ替えてもよいなどは典型っぽいです。
Nが大きいのでO(N)かO(NlogN)ぐらいなので、シンプルな解法を想定するべきでした
D Vus the Cossack and Numbers
問題：N個の実数aiが与えられる。足して0になる。それぞれのaiを切り上げか切り捨てをして、足して0になる整数列ｂを構築せよ
考察：
まず、全て切り捨ててしまいます。
元々整数であったaiは切り上げできないらしいので、小数だったもののindexを記録します。
切り捨てたものを足して、0に届かない分を、もともとが小数だったものに足していけばよいです。
E Vus the Cossack and a Field
問題：01のN*M行列が与えられる。01を入れ替えたものを右側、下側にくっつけて、右下には同じものをつける。これを無限に繰り返したものを考える。
はじめの左上を1，1として、x1,y1,x2,y2に含まれる範囲の値を足したものを求めよ。
TLEが取れなかったので嘘解法だと思います。解説読んだら追記するつもりです。
考察：
まず与えられるx,yがかなり大きいので愚直では通りません。
状況を整理しました。与えられた行列をX0、反転させたものをY0とします
1回操作を行うと
X0Y0
Y0X0
となります。
これをX1とし、反転させたものをY1とします。
Xkの大きさは2^kN、2^k*Mで、1の数は2*k*N*Mです
クエリx1,y1,x2,y2が完全に含まれるまで、Xk ,Ykを大きくします
段階kから、4分割し
完全に含まれるなら2^k*N*Mを足す
完全に外なら何もしない
中途半端に含まれるなら再帰
といった要領で求めました。
最後のX0、Y0はあらかじめ二次元累積和をしておけば、任意の範囲の合計がわかります。
TLE
※追記
一応自力で通したので追記します。
考察２：
まず、二次元累積和的な考え方をして範囲の和を求めます。
[0,x)[0,y)の和をS(x,y)とすると求めるべき値は
S(x2,y2)-S(x1-1,y2)-S(x2,y1-1)+S(x1-1,y1-1)
となります。
このSの値が高速に求められればこの問題を解くことができます。
2n行m列を１セットで考えるとXYかYXの組になります。n行2m列のセットでも同様です。
したがって
2m*l y%2m
2n*k A B
x%2n C D
このような4つの区域に分けてみます。
Aの部分では2n*2mの行列が並んでいます。合計は2*n*m*k*lです
BとCは同じ考えで求められます。
Bだけ示します。
2n*2mのセットのx%2n行から上の和が、l個続いています。
したがって2n*2mの二次元累積和をあらかじめ計算しておくことで簡単に求まります
最後にDです。
Dでは
XY YX
YX か XY か
どちらになるかを考えなければいけません。
それが求まれば上で述べた二次元累積和を使って簡単に求まります。
Dの構成を求めるためにまずは、1～m列目の行列のXとYの周期を考えましょう
はじめはXYYXと並びます
これをX1とすると、更にX1Y1Y1X1
Y1から始まればY1X1X1Y1X1です。
ＸやＹの2(x/2n)+1番目を考えます。
この値を/4を繰り返す中で%4=1,2のとき反転して、いまがXかYかだけ考えればよいです
x%2n行の情報がわかれば同じ要領でy%2mまでを考えればＤの構成がわかります。
以上からO(Q+4NM)でこの問題が解けました。
感想：
範囲を求めるために、累積和っぽく処理する。
2n*2mごとに見る
あたりは典型っぽく感じました。
細かく場合分けすれば解けるところを、工夫して簡単にするっていうのは面白いですね。
全体の感想
Cがわからず、Bが存在しない。Eは難しくて解けないという状況で、かなりひどい結果になりました。（AC2完）
前のほうで躓くとどうしようもないので辛いですね。
時間をかけて後ろが通せると挽回できるので、そういう力もつけなきゃなあと思いました
