Codeforces Round #567 (Div. 2) + AtCoder Beginner Contest 130
- masashinakata
- 2686
- 1
- 0
- 0
こどふぉ567div2 A:x/z+y/z==(x+y)/zならお金を渡さない,そうでなければmin(z-x%z,z-y%z)を渡す B:巨大数つらい 中心あたりで切ったり,中心に近い0でない桁で切ったりを定数個試す (→)
2019-06-16 20:50:05(→) C:a[i][j]:=(i,j)から下方向にどこまで同じ色か,b[i][j]:=(i,j)から右方向にどこまで同じ色か,を求めておく.各(i,j)についてh:=a[i][j]としてi+h*3<=nかつa[i+h][j]==hかつa[i+h*2][j]>=hのとき,答えにmin_{k∊[i,i+h*3)}{b[k][j]}を加える. minはSparseTableを用意しておくとO(NMlogM) (→)
2019-06-16 20:50:05(→) D:各数の出現数を調べておく.max{出現数}*mより大きいkについてはk%mで求まる.そうでないものは,クエリソートしておいて,出現数hまで処理したときのhと,出現数がh以下である番号の所に1を書いたBITを持って順に答えを埋めていく. (→)
2019-06-16 20:50:06(→) クエリkについて出現数hであるとき,t:=k-(h-1)*mとしてBIT上でにぶたんして[0,i)の和がtになる最小のiを答えとする E1:縦を無視して区間と見て,区間が重ならないよう出来るだけ分割して,各区間の集合について今度は横を無視して区間と見て…と再帰的に分割していって全て分割できるか試す O(N²)
2019-06-16 20:50:06こどふぉ567 A: 難しくて泣きそうだった B: 面倒で泣きそうだった C: 各列それぞれ下から累積和を計算した後で左上から順に見ていった
2019-06-16 20:51:49ABC参加 AtCoder Beginner Contest 130 - AtCoder atcoder.jp/contests/abc13…
2019-06-16 20:51:57はじまるよー! twitter.com/chokudai/statu…
2019-06-16 20:55:24きょうだよ!! (開始まで連絡取れないのでがんばってください!!!) AtCoder Beginner Contest 130 - AtCoder atcoder.jp/contests/abc13…
2019-06-16 19:59:16