AtCoder Beginner Contest 132

更新日時:

AtCoder Beginner Contest 132

ソースコード

解法のメモ

A - Fifty-Fifty

sort して S[0] == S[1] && S[1] != S[2] && S[2] == S[3] かどうかを判定する。

B - Ordinary Number

各部分列において、元は全て異なっているので、 $\{ p _ {i - 1}, p _ i, p _ {i + 1} \}$ のうち $p _ i$ が $2$ 番目に小さいということは、 $p _ {i - 1} < p _ i < p _ {i + 1}$ または $p _ {i - 1} > p _ i > p _ {i - 1}$ であるということである。これを直接数えればよろしい。

C - Divide the Problems

sort すると答えは $d[N/2] - d[N/2 - 1]$ である。

D - Blue and Red Balls

mint solve(int i); を $O(1)$ で求めれば十分である。 $i$ 個の青色のエリアがあるということは、その中に $i - 1$ 個の赤色のエリアがある。そしてその両端にも赤色のエリアがあるが、個数は $0$ でもよろしい。その他は $1$ 個以上が必要である。これらをまず $1$ 個おいておく。つまりそこで $B = K$, $R = N - B$ として $r = R - (i - 1)$, $b = B - i$ とする。すると $r, b < 0$ のときはおかしいので答えは $0$ である。残りは $r$ 個を $i + 1$ 個のグループに分ける場合の数を求めればいいが、空間が $r + i$ 個あって、仕切り板を $i$ 個おけばよろしい。青も同様であるから、答えは以下の通り。 \[ solve(i) = \begin{cases} 0 & r < 0 \lor b < 0, \\\ \begin{pmatrix} r + i \\\ i \end{pmatrix} \begin{pmatrix} b + i - 1 \\\ i - 1 \end{pmatrix} & \text{otherwise}. \end{cases} \]

E - Hopscotch Addict

解法

$0$-indexed とする。 $C = 100001$ とする。グラフを構築するが、頂点に状態を持たせる。

  • 頂点 $i \in N$ :頂点 $i$ に長さ $0 \in \mathbb{Z}/3\mathbb{Z}$ で到達した状態。
  • 頂点 $i + C$ for $i \in N$ :頂点 $i$ に長さ $1 \in \mathbb{Z}/3\mathbb{Z}$ で到達した状態。
  • 頂点 $i + 2C$ for $i \in N$ :頂点 $i$ に長さ $2 \in \mathbb{Z}/3\mathbb{Z}$ で到達した状態。

すると、元のグラフでの $i \mapsto j$ とは、 $i \mapsto j + C$ と $i + C \mapsto j + 2C$ と $i + 2C \mapsto j$ を張ることに対応する。あとは長さが全部 $1$ の辺だけなので BFS で求まる。頂点 $S$ から $T$ へ到達しなかった場合は -1 が答えで、その他の場合は距離の $3$ で割った値が答えである。

ポイント

ダイクストラ法でやった。計算量は $O(N \log M)$ である。

F - Small Products

さすがに $O(NK)$ は間に合わないし、状態も持てない。そこで、次に来る数字に注目して状態をまとめることにする。

$1$-indexed とする。割り算は全部計算機の割り算とする。 $X = \sqrt{N} + 10$ とする。小数部分は適当に処理する。

$DP[t][j] = t$ 番目まで見たときに、数字 $j \leq X$ を最後においた場合の数。
$DP2[t][j] = t$ 番目まで見たときに、数字 $j$ を 次に置くことのできる 数字を最後においた場合の数、ただし、この数字は $X$ より大きくないといけない。
$cnt[j] = $ 数字 $j$ を 次に置くことのできる 数字のうち $X$ より大きいものの個数。

$cnt[j] = \max(N / j, X) - \max(N / (j + 1), X)$ である。途中から $0$ になるので、 $cnt$ の index は $[1, C)$ を動くものとする。

解答の考察 TLE

初期状態: $DP[0][1] = 1$, otherwise $0$. 答え: $\sum _ j DP[K][j] + \sum _ j DP2[K][j]$. 遷移は以下の通り。集める DP で書く。 $t = 1, \dots, K$ に対し、 $j = 1, \dots, X$ に対し、 $t$ 番目に $j$ を置くためには、前の数字は、 $X$ 以下なら $N / j$ 以下である必要があるし、 $X$ より大きければ「次に $j$ よりも大きい数字を置ける」数字でないといけない。つまり以下の通りになる。 \[ DP[t][j] = \sum _ {1 \leq i \leq \min(X, N/j)} DP[t - 1][i] + \sum _ {j \leq i \leq C - 1} DP2[t - 1][i]. \tag{F.1} \] $j = 1, \dots, C - 1$ に対し、 $t$ 番目に、 $X$ より大きくて「次に $j$ を置くことのできる」数字が来るためには、その前の数字はやはり $j$ 以下でないといけない。つまり以下の通りになる。 \[ DP2[t][j] = cnt[j] \sum _ {1 \leq i \leq j} DP[t - 1][i]. \tag{F.2} \]

累積和で高速化 AC

集める DP で書けば、累積和でとても簡単に右辺を高速化できる。次式を定義する。

\[ \begin{align} DP \_ sum[t][j] &= \sum _ {i = 1}^j DP[t][i], \\\ DP2 \_ sum[t][j] &= \sum _ {i = 1}^j DP2[t][i] \end{align} \]

つまり処理は以下の通りになる。初期状態: $DP[0][1] = 1$, $DP \_ sum[0][j] = 1$ for $j = 1, \dots, X$, otherwise $0$. 答え: $DP \_ sum[K][X] + DP2 \_ sum[K][C - 1]$. 遷移: $t = 1, \dots, K$ に対し、 $j = 1, \dots, X$ に対し、 (F.1) 式に相当するのは \[ DP[t][j] = \begin{cases} DP \_ sum[t - 1][\min(X, N/j)] & j \geq C, \\\ DP \_ sum[t - 1][\min(X, N/j)] + DP2 \_ sum[t - 1][C - 1] - DP2 \_ sum[t - 1][j - 1] & j < C. \end{cases} \] $j = 1, \dots, C - 1$ に対し、 (F.2) 式に相当するのは \[ DP2[t][j] = cnt[j] DP \_ sum[t - 1][j]. \] あとは累積和の更新である。 \[ \begin{align} DP \_ sum[t][0] &= 0, \\\ DP \_ sum[t][j] &= DP \_ sum[t][j - 1] + DP[t][j] \text{ for } j = 1, \dots, X, \\\ DP2 \_ sum[t][0] &= 0, \\\ DP2 \_ sum[t][j] &= DP2 \_ sum[t][j - 1] + DP2[t][j] \text{ for } j = 1, \dots, C - 1. \\\ \end{align} \]

ポイント

累積和を使う問題は、集める DP で書くのがポイント だと解説放送の時に言われた。

その他

Assignments:
A - sample: 4, tle: 2.000, time: 02:14, from_submit: 92:24
B - sample: 2, tle: 2.000, time: 02:11, from_submit: 90:13
C - sample: 3, tle: 2.000, time: 02:07, from_submit: 88:06
D - sample: 2, tle: 2.000, time: 08:06, from_submit: 80:00
E - sample: 4, tle: 2.000, time: 20:24, from_submit: 59:36
F - sample: 3, tle: 2.000, time: 59:36, from_submit: 00:00