AGC 008 B - Contiguous Repainting (400)
解法
解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる.
さて,逆順に見ていったときの最初(つまり元の操作で最後)の操作を固定する. これは2(N-K+1)通りある.
後は実験していって気づく必要があるが,それ以外のマスは自由に変えることができる(外側から1つずつずらして範囲を塗っていけばいい)
なので,これをループを回していけばいい. 1回の計算に数列の範囲の最大値が入っているので累積和を使って高速する.
コード
Mujin Programming Challenge 2018 C - 右折
解法
最初に右を向いていて,次に右折するパターンを考える.
各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる.
それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるのでこのパターンは解けた.
これを全方向実装するのはかなりめんどくさいので,迷路自体を回転してループを4回回せばいい.
メモ
公式解答は鮮やかすぎて思いつかないので...
コード
AtCoder Grand Contest 028 B - Removing Blocks (600)
解法
解説の1つの解釈として.
解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える.
ただし,確率ではなくそのような順列の場合の数を数え上げることにする.
事前準備として,n個の順列のうちで
そのうちの要素 x,y (x!=y) に関して x<y が成り立っているものは n!/2 になる.
これをもう少し考えると x_1 < .. < x_k+1 のk個の不等号があるものは n!/(k+1)! になることがわかる.
(n個の場所からx_iの場所k+1個を選ぶ) * (残りのN-k-1個は自由に並べる)
= nC(k+1) * (n-k-1)! = n!/(k+1)!
と考えても良い.
これを使って,上の順列が何通りあるかを数える.
簡単のため, i < j と仮定して
x_0 = i, x_1, ... , x_k, x(k+1) = j とする. (k = j-i-1)
ここで, 求めたい順列を束縛する不等式は i の後にx_1, x_2,.., x(k+1) が出るという条件のみを満たしていれば良いことを考えると
x_0 < ( x_1, x_2, .. , x(k+1) を好きに並べて不等号で繋いだもの ) であることがわかる.
これは, x_1,...,x(k+1) の順番が決まればk+1個の不等号が繋がっているので N!/(k+2)! 個ずつある.
このいずれかを満たす順列(つまり順列の和集合)を求めればよく,これらは全て排反であるため
合計で n!/(k+2)! * (k+1)! = n!/(k+2) = n!/(j-i+1) 個あることがわかる.
ここからは解説と一緒で,
A_j * sum_i{ n!/abs(j-i+1) } のjに関する和が答えになる.
調和級数を事前に計算しておけばO(N)
メモ
確率として典型処理するようにしたほうがいい気もする..
コード
「みんなのプロコン」2017 本選 A - YahooYahooYahoo
解法
典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる.
(は正規表現における閉包)
i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう.
それまでの最小の編集距離に注目する上では, 末尾が "yahoo" の何番目になっているかということにだけ注目すれば良い.
よって, dp[i][j] := (S[0,i) を 末尾が"yahoo"のj番目(0-index)になるようにした,最小の編集距離 ) とする.
すると, 遷移は dp[i][j] からs[i] をそのまま足して 1<=k<=5 回末尾に insert, または末尾を 1回deleate したパターンを考えればわかる.
1<=k<=5 回でなく1回だけinsertすると考えて dp[i][j] から dp[i][j+1] に遷移させることもできるが, その場合解説にあるように2周しないといけない.
初期値と答えに注意.
コード
DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2
解法
a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い.
Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない.
定跡としてこの分布をとると,(つまり cnt[a] := aの現れる回数 とする)
全ての a<=b (a,bはcntのkey) についての全探索がO(K)となって間に合う.
ただし a==bのときは abがKの倍数になるならば cnt[a](cnt[a]-1) を足すことに注意(自分自身とは組にできないため)
コード
square869120Contest #3 D - お土産購入計画2 / Souvenirs (600)
解法
- 最短路なので2人とも(0,+1) or (+1,0) で進む
- 1人だったら? -> DPで(x,y)または(何回進んだか,x)をキーとして持ってやればできる
- なぜなら(x,y)で最大のお土産を持つためには(x-1,y)or(x,y-1)で最大のお土産を持っている必要があるため
- 2人でも2人の座標を持ってやればできそう
- (x,y)両方とも持つ必要はなく, (ターン数,1人目のx,2人目のx) を持てばOK
- 漸化式は
- 2人とも同じとこにいく(nx,ny)=>+a[nx][ny]
- 2人が別のとこにいく(nx1,ny1),(nx2,ny2) => +a[nx1][ny1]+a[nx2][ny2] でOK
メモ
1人ならDPできるねーからマップを2つに分けて各々DPするか?みたいな方向に行ってしまってできなかった.
どういう状態を持つべきか,とかの訓練が足りなさそう
