読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

Battle Conference U30 解説

競技プログラミング

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]の総和が答え