AGC023 A B
A Zero-Sum Ranges
問題概要
長さNの整数列Aが与えられた時、空でない連続する部分列でその総和が0になるものの個数を求める問題。
取った方針
部分列の和を高速に求めたい場合は累積和の利用を考える。S[i] = A[1]+...A[i]なる累積和を取った時、部分列A[i]...A[j]の総和が0になる、とは、S[j]-A[i-1]が0であることに他ならない。
S[i]が0の時は先頭からの和が0になるので別途加算することとして、S[i]に含まれる数字の個数を数え、その数がn個ある場合はnC2を計算すればよい。(区間を構成するためにn個ある点のなかから2点を選ぶため)
(累積和のことをimos法だと思っていたので変数名をimosにしているけどなんか違う気がしてきた)
正しい方針
同上
得られた知見
・部分列の和を高速に求めたい場合は累積和を利用する。
解くのに必要な要素
・累積和
・部分列の和が0になる、ということは累積和の数列の中に同じ数字が複数出てくることである、という理解
周辺調査によって得られた知見
・部分列の和を求める数列が実行中に変化する場合はsegtreeというものを使うらしい
B
問題概要
盤面が与えられた時、下にA,右にBずらすことを考える。ずらした際下にkはみ出た時、k行目であるとして扱い、右にはみ出た際も同様である。
この操作をした後に任意のi,jについて盤面[i][j] == 盤面[j][i]である場合、その盤面をよい盤面と定義するとき、よい盤面となるようなA,Bの数を答える問題。
取った方針
N<=300なのでO(N3)が必要であるが、愚直にやるとO(N4)である。そこで、ランダムにN個の組み合わせだけ見ていい盤面かどうかを判定する嘘解法を書いたがまあWAだった。(見る数を増やして悪あがきしたがダメだった)(確率を考えろ)
恐らく300*300でほぼaで埋められているが一か所だけB、みたいな盤面が混ざっていたのだと思う。
その後Cに行きつつ真面目に考察してA==Bの場合よい盤面が維持されることに気づくもそこで時間切れ。
正しい方針
A==Bの場合よい盤面が維持される、というのが本質部分で、A==Bの時、つまり右下に移動する時よい盤面かどうかは変化しない。
なぜなら、盤面[i][j]と盤面[j][i]として比較される文字の組み合わせは変化しないからである。
例えば、以下のような場合を考えると、
abc def ghi ↓ (A=1,B=1) igh cab fde
比較されるのはcとg, hとf, で変化していない。
なので、A=m,B=nをイカ(m,n)と表すことにすると、
(m,n) == (m+x, n+x)が成り立つことがわかる。m+x >= Nなる場合でも、A>=NのときAはA%Nと同じであることを考えると問題ないことがわかる。
よって、(0,n)(0<=n<N)の時のみ調べて、その結果をN倍すればよい。
得られた知見
・同じとみなせる状態を考えることで計算量を落とせることがある。
・法則を見出すべく手を動かして実験をすると気づきが得られる可能性がある。
・その際、紙の上で実行するのが辛ければプログラムを書いて試すのも厭うべきではない。
・400点500点が解けるか解けないか、という今の段階なら割ける時間はたくさんあるはず
今回なら、行はA、列はBとして、よい盤面なら1、そうでないなら0を出力する表を以下のように作成し、睨んでいれば気づけた可能性がある。
解くのに必要な要素
・(n,n)を盤面に適用した場合、いい盤面かどうかは変化しない
・同じとみなせる盤面の存在に気づくことで計算量を落とせる（一般化）
・規則性だけで解けそうな場合(どういう場合？)は実験を行う
周辺調査によって得られた知見
特になし
