naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 023

4/28(土) 21:00 - 23:20
ちょっと長めの140分のコンテスト。
配点と問題の難易度が比例していない気がするがAGCってそういうものか。

二完でレート+64 (1659→1723)
f:id:n4_t:20180429012610p:plain
f:id:n4_t:20180429010736p:plain

A - Zero-Sum Ranges (200)

累積和をとって
累積和の配列の中で、始まりと終わりが同じ数であればその区間は和がゼロなはず
ってことは
累積和の配列の中にある数字 x が n個あるとしたら、xで始まりxで終わる区間は nC2個あるわけで
すべての数字についてそれを求めて合計すればよさげ
→AC (8'09'')
https://agc023.contest.atcoder.jp/submissions/2426547

B - Find Symmetries (500)

行番号列番号がmod Nみたいになるってのを問題文で読み飛ばしてて、サンプル見ながら(なんで問題にそう書いてないんだろう、なんで誰も質問していないんだろう)とか思ってたのはさておき
NxNをタイルとして縦横に無限に(と言っても2x2ぐらいで、なんなら1x2で…いやmodを使えばコピーも不要)コピーしておく
対角成分を共有するNxN行列が斜めに(1つずつずらしながら)並んでる感じで、これは全てOKか全てNGか
ずらすパターンは全部でNxN (=1+2+3+...(N-1)+N+(N-1)+...+3+2+1) 通り。対角成分を共有する斜めのセット(N個ずつ)がNセットある感じ。
なのでNセットについて最初のNxN行列を調べて、対称行列になっていれば+Nしていく感じで。
Nx(NxN) なのでO(N^3)で解ける。
→AC (29'24'')
https://agc023.contest.atcoder.jp/submissions/2427944

C - Painting Machines (800)

開いた
N-1, N-2 のときの結果を利用したDPみたいなのを考えていて(その方針に固執するも複雑さが減らないままで)時間を浪費した。
〈復習編〉

D - Go Home (1200)

開いた
だんだん大きくなるジグザグのパターンになるっぽい、ってところまでは見えたのに
それを逆に外から攻めればいい、ってところに行きつけなかった(残念)

E - Inversions (1700)

開いてない

F - 01 on Tree (1700)

開いてない