AtCoder Beginner Contest 132
Updated:
- Review: 2020-05-18
Source codes
Solutions
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
Solution
$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$ で割った値 が答えである。
Point
ダイクストラ法でやった。計算量は $O(N \log M)$ である。
実装する際は、このグラフは有向グラフであることに注意する。
F - Small Products
Observation
さすがに $O(NK)$ は間に合わないし、状態も持てない。そこで、 次に来る数字に注目して状態をまとめる ことにし、 DP を実行する。 平方分割 のアイデアを使用する。
$1$-indexed とする。割り算は全部計算機の割り算とする。 $X = \sqrt{N} + 10$ とする。小数部分は適当に処理する。
ll N, K;
cin >> N >> K;
ll X{static_cast<ll>(sqrt(N)) + 10};
Definition
$DP[i][j] = i$ 番目まで見たときに、数字 $j \leq X$ を最後においた場合の数。
$DP2[i][j] = i$ 番目まで見たときに、数字 $j$ を 次に置くことのできる 数字を最後においた場合の数、ただし、この数字は $X$ より大きいものだけを考慮する。
$cnt[j] = $ 数字 $j$ を 次に置くことのできる 数字のうち、 $X$ より大きいものの個数。
このうち、 $cnt[j]$ は以下の通りすぐに求まり、 $j \leq X$ として問題ないこともわかる。
\[ cnt[j] = \max(N / j, X) - \max(N / (j + 1), X). \]
vector<mint> cnt(X + 1);
for (auto j = 1; j <= X; ++j)
{
cnt[j] = max(N / j, X) - max(N / (j + 1), X);
}
TLE Solution
Initial state
$DP[0][1] = 1$, otherwise $0$.
Answer
\[ \sum _ j DP[K][j] + \sum _ j DP2[K][j]. \]
Transition
遷移は以下の通り。集める DP で書く。 $i = 1, \dots, K$ に対し、 $j = 1, \dots, X$ に対し、 $i$ 番目に $j$ を置くためには、前の数字は、 $X$ 以下なら $N / j$ 以下である必要があるし、 $X$ より大きければ「次に $j$ よりも大きい数字を置ける」数字でないといけない。つまり以下の通りになる。 \[ DP[i][j] = \sum _ {1 \leq k \leq \min(X, N/j)} DP[i - 1][k] + \sum _ {j \leq k \leq X} DP2[i - 1][k]. \tag{F.1} \] $j = 1, \dots, X$ に対し、 $i$ 番目に、 $X$ より大きくて「次に $j$ を置くことのできる」数字が来るためには、その前の数字はやはり $j$ 以下でないといけない。つまり以下の通りになる。 \[ DP2[i][j] = cnt[j] \sum _ {1 \leq k \leq j} DP[i - 1][k]. \tag{F.2} \]
もちろんこのままだと、 $O(K X ^ 2)$ なので TLE する。
AC Solution by Cumulated Sum
集める DP で書けば、累積和でとても簡単に右辺を高速化できる。次式を定義する。
Definition
\[
\begin{align}
SUM[i][j] &= \sum _ {k = 1} ^ j DP[i][k], \\
SUM2[i][j] &= \sum _ {k = 1} ^ j DP2[i][k].
\end{align}
\]
Initial State
$DP[0][1] = 1$, $SUM[0][j] = 1$ for $j = 1, \dots, X$, otherwise $0$.
DP[0][1] = 1;
for (auto j = 1; j <= X; ++j)
{
SUM[0][j] = 1;
}
Answer
$SUM[K][X] + SUM2[K][X]$.
cout << SUM[K][X] + SUM2[K][X] << endl;
Transition
$i = 1, \dots, K$ に対し、 $j = 1, \dots, X$ に対し、 (F.1) 式に相当するのは
\[
DP[i][j] = SUM[i - 1][\min(X, N/j)] + SUM2[i - 1][X] - SUM2[i - 1][j - 1]
\]
$j = 1, \dots, C - 1$ に対し、 (F.2) 式に相当するのは
\[
DP2[i][j] = cnt[j] SUM[i - 1][j].
\]
あとは累積和の更新である。
\[
\begin{align}
SUM[i][j] &= SUM[i][j - 1] + DP[i][j] \text{ for } j = 1, \dots, X, \\
SUM2[i][j] &= SUM2[i][j - 1] + DP2[i][j] \text{ for } j = 1, \dots, X.
\end{align}
\]
for (auto i = 1; i <= K; ++i)
{
for (auto j = 1; j <= X; ++j)
{
DP[i][j] = SUM[i - 1][min(X, N / j)] + SUM2[i - 1][X] - SUM2[i - 1][j - 1];
DP2[i][j] = cnt[j] * SUM[i - 1][j];
SUM[i][j] = SUM[i][j - 1] + DP[i][j];
SUM2[i][j] = SUM2[i][j - 1] + DP2[i][j];
}
}
計算量は $O(XK) = O(\sqrt{N} K)$ である。
ポイント
累積和を使う問題は、集める DP で書くのがポイント だと解説放送の時に言われた。
Others
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