http://bcu30.contest.atcoder.jp
以下、解説
A. すごろく
http://bcu30.contest.atcoder.jp/submissions/1155381
問題文にある通り実装するだけ
B. 数学パズル
http://bcu30.contest.atcoder.jp/submissions/1155395
3つの条件をチェックするだけ
C. クロスワード
http://bcu30.contest.atcoder.jp/submissions/1155419
事前計算をしておく(pre関数)
1文字目がiのとき2番目における文字集合: cand[i]
1文字目がi, jの時2番目に来ることのできる文字数: cnt[i][j]
| A | C |
| B | D |
辞書の単語をABに入れる全探索を考える。
cand配列を使って、ACが単語となるようにCを全探索で入れる。
あとは、Dを埋めるだけだが、Dに置くことのできる文字も全探索すると、TLEしてしまう。
これは置くことのできる文字の個数はcnt[B][C]なので、事前に計算しておくことでO(1)で間に合う。
D. 数直線
http://bcu30.contest.atcoder.jp/submissions/1155424
配列Xをソートして、累積和sm[i] = A[0] + A[1] + ... + A[i]を計算しておく。
位置Tが、A[i] <= T < A[i + 1]にあるとすると、
- A[0]～A[i]とTとの距離は (T - A[0]) + (T - A[1]) + ... + (T - A[i]) = T * (i + 1) - sm[i]
- A[i+1]～A[N-1]とTとの距離は (A[i+1] - T) + ... (A[N-1] - T) = (sm[N-1] - sm[i]) - T * (N - i - 2)
あとは端の処理を上手いことやって答え。
典型ではあるが、やや難しい。
E. スライドパズル
http://bcu30.contest.atcoder.jp/submissions/1155431
事前計算をしておく(pre関数)
B[y][x] := '#'なら1, '.'なら0
BB[y][x] := B[0][0]～B[y][x]の累積和（二次元累積和）
以下の様な関数を用意する
bool chk(int ax, int ay) := 駒の左上が(ax, ay)の時に駒をおけるか
(ax, ay)～(ax + K - 1, ay + K - 1)の範囲の和が0なら壁が1つもないので駒をおける
この判定に配列BBを使う
よくあるBFSで連結成分を彩色 coloring() して、
各クエリについて彩色された色を使って判定すれば答え。
F. 数列と計算
http://bcu30.contest.atcoder.jp/submissions/1155796
＜＜この問題は1-indexedで説明しています。＞＞
Naive解法から解説するが、このNaiveにたどり着くまでがまず難しい。
まず、全パターンを足した結果を求めよという問題の典型解法として「ある部分的な結果が全体で何通り出てくるかを使う」という方針がある。
この方針を使ったことが無いと、今回の問題を答えるのは難しい。
- 「+A[L]*A[L+1]*...*A[R]+」という数式を考える
- 全パターンのうち、一部にこの数式が出てくる数式の組合せは2^(max(0, L - 2) + max(0, N - R - 1))通り
- [L,R]の範囲の積は2^(max(0, L - 2) + max(0, N - R - 1))回全体で足される
- つまり、区間[L,R]の積が全パターンで足された和は ([L,R]の積)*2^(max(0, L - 2) + max(0, N - R - 1))
- pat(L,R) := ([L,R]の積)*2^(max(0, L - 2) + max(0, N - R - 1))
愚直解ではpat(L,R)を全区間計算して総和を取ればよい。
この解法の高速化をしなければ通らないが、まず、この実装ができていないとダメなので、プロ以外はこういう愚直解が出来上がった段階でまず実装をして、サンプル（今回は比較的大きいやつもあったので）くらいは通しておこう。
これではO(N^2)で間に合わないので、高速化を図る。
dp[i] := [i,N], [i+1,N], ... , [N,N]の区間での([L,R]の積)*2^(max(0, L - 2) + max(0, N - R - 1))の和
dp[1]はNaive解法で愚直に計算します。漸化式は以下の感じ
i == 1のとき dp[i + 1] = (dp[i] - pat(i,i)) / A[i]
i == 2のとき dp[i + 1] = (dp[i] - pat(i,i)) / A[i] * 2
漸化式での*2は範囲より前の数式で+,*の2通り使われるパターンが増える的な感じ
すると、dp[1]～dp[N]の総和が答え
