Kazune Takahashi

Ygnaiih… ygnaiih… thflthkh’ngha

AtCoder Beginner Contest 132

Updated:

AtCoder Beginner Contest 132

  • 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

You May Also Enjoy