AtCoder Beginner Contest 044

更新日時:

AtCoder Beginner Contest 044

ソースコード

解法のメモ

A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)

$N \leq 10000$ なので、普通に $1$ 日目から $N$ 日目まで宿泊していけばよろしい。

B - 美しい文字列 / Beautiful Strings

Ruby なら hash などに入れてカウントすればよろしい。 C++ なら int cnt[26]; でよろしい。

C - 高橋君とカード / Tak and Cards

これは基礎的な DP である。 $y _1, \dots, y _m$ の平均が $A$ であることは、 $y _ 1 - A, \dots, y _m - A$ の平均が $0$ であることと同値である。そこで予め $x _i$ たちを $-A$ しておく。以下の通りに定義する。

$DP[i][j] = x _0, \dots, x _{i - 1}$ を使って和 $j$ を作る場合の数。

  • 初期状態: $DP[i][0] = 1$ 、 $DP[i][j] = 0$ for $j \neq 0$ 。
  • 答え: $DP[N][0] - 1$ (「$1$ つも選ばない」を除くため)。
  • 遷移:配る DP をやる。 $i = 0, \dots, N - 1$ に対し、 $j = -M, \dots, M$ に対し、 \[ \begin{align} DP[i + 1][j] += DP[i][j], \\\ DP[i + 1][j + x _i] += DP[i][j]. \end{align} \]

$M = 5000$ 程度あれば十分である。配る DP なので $0$ は配らないようにすれば範囲外参照はありえない。

D - 桁和 / Digit Sum

まず、

  • $n < s$ の場合は、 -1 が答え、
  • $n = s$ の場合は、 $n + 1$ が答え。

以下、 $n > s$ を仮定する。基本的には全探索するしかない問題である。 $b = 2, 3, \dots$ に対して $f(b, n) = s$ であることを確かめるしかない。しかしこれだともちろん TLE する。そこで大きい $b$ に対しては何が起きているのかを考える。 $b > \sqrt{N}$ の場合は、これは $b$ 進数表記で $2$ 桁になる。つまり、その表記を $(pq) _{b}$ とすると、 $n = pb + q$, $s = p + q$ が成立する。 $p = 0$ のときは $n = s = q$ であるので、これは既に除いている。したがって、 $1 \leq p \leq \sqrt{n}$ である( $n = pb + q \geq pb \geq p^2$ より)。 $p$ が決まれば、連立方程式なので $q, b$ について解ける。 $0 \leq q < b$ と $b$ が整数であることを確かめると、 $b$ の候補が定まる。その $b$ について $f(b, n) = s$ であるかどうか全て確かめ、最小の $b$ を出力すればよろしい。ない場合は -1 を出力する。計算量は $O(\sqrt{N})$ である。

ポイント

ポイントを一言で言えば 平方分割 であるが、言われればわかるけど、言われないと気づかないであろう。 「全探索するしかない」しかし「大きいところでの挙動は簡単である」 という時に使いやすい。

その他

コメントする