Tenka1 Programmer Contest 2019
Updated:
Tenka1 Programmer Contest 2019
Source codes
Solutions
C - Stones
最終形は「白マス $i$ 個 + 黒マス $N - i$ 個」しかありえない。累積和を使って $i$ について全探索すると $O(N)$ でできる。
ポイント
これしか解けなかった。これを解いた後 F に進んでそれで終わった。
D - Three Colors
解法
それぞれの色の合計値を $A, B, C$ とする。全ての辺の合計値を $S$ とする。このとき三角形を「なさないため」の条件は、 \[ A \geq \frac{S + 1}{2} \lor B \geq \frac{S + 1}{2} \lor C \geq \frac{S + 1}{2} \tag{D.1} \] である。割り算は計算機の割り算である。 or で繋がれているので、答えは包除原理を使用すれば求めることができる。対称性を考慮すると、具体的には、
$K = A$ の合計が $(S + 1) / 2$ 以上である場合の数、
$L = S$ が奇数の場合は $0$ 、偶数の場合は、 $A = S / 2$ かつ $C = 0$ である場合の数
とすると、答えは \[ 3 ^ N - 3K + 3L \] である。以下 $K, L$ を求めるが、これは DP で求めることができる。以下 $0$-indexed とする。
$K$ の求め方
$dp[i][v] = i$ 番目以下までの $a _ j$ たちを用いて、 $A = v$ かつ $B, C$ にはなんら制約を貸さない場合の数
とする。初期状態： $dp[0][0] = 1$, otherwise $dp[i][v] = 0$ 。答え：
\[
K = \sum _ {v = (S + 1) / 2} ^ S dp[N][v].
\]
遷移： $i = 0, \dots, N$ に対し、 $v = 0, \dots, 90000$ に対し、 $dp[i][v] > 0$ ならば
\[
\begin{align}
dp[i + 1][v + a[i]] & \mathbin{ {+} {=} } dp[i][v], \\
dp[i + 1][v] & \mathbin{ {+} {=} } 2 \times dp[i][v].
\end{align}
\]
念のためいうと、 $a[i]$ を配る先は $A$ または $B, C$ しかないから上の通り遷移するのである。配る DP だから $0$ は枝刈りすれば配列外参照も起きない。
$L$ の求め方
$DP[i][v] = i$ 番目以下までの $a _ j$ たちを用いて、 $A = v$ かつ $C = 0$ であるような場合の数
とする。初期状態： $DP[0][0] = 1$, otherwise $DP[i][v] = 0$ 。答え： $S$ が奇数なら $0$ 、偶数なら
\[
L = DP[N][S / 2].
\]
遷移： $i = 0, \dots, N$ に対し、 $v = 0, \dots, 90000$ に対し、 $DP[i][v] > 0$ ならば
\[
\begin{align}
DP[i + 1][v + a[i]] & \mathbin{ {+} {=} } DP[i][v], \\
DP[i + 1][v] & \mathbin{ {+} {=} } DP[i][v].
\end{align}
\]
以上で解答が求める。
ポイント
三角不等式ばかり考えていて (D.1) に気づかなかった。
E - Polynomial Divisors
解法
まず $p$ を素数とし、しばらく固定する。 $K = \mathbb{Z} / p \mathbb{Z}$ とする。任意の $x \in \mathbb{Z}$ に対し、整数
\[
f(x) = \sum _ {i = 0} ^ N a _ i x ^ i \tag{E.1}
\]
が $p$ で割り切れるための必要十分条件を求めたい。するとフェルマーの小定理により $x ^ p = x \text{ in } K$ により、多項式 $f(x)$ は、
\[
\begin{align}
f(x) = & a _ 0 \\
+ & (a _ 1 + a _ p + a _ {2p - 1} + \dots ) x \\
+ & (a _ 2 + a _ {p + 1} + a _ {2p} + \dots ) x ^ 2 \\
+ & \dots \\
+ & (a _ {p - 1} + a _ {2p - 2} + a _ {3p - 3} + \dots ) x ^ {p - 1}
\end{align}
\]
と書かれる。ここで $p$ が素数であり、かつ、相異なる $p$ 個の元 $x = 0, \dots, p - 1 \text{ in } K$ が $f$ の根になっていることにより、 $f = 0 \text{ in } K[x]$ である(下に証明をしてある)。すなわち、 $K$ の元として、
\[
\begin{align}
& a _ 0 = 0 \\
& a _ 1 + a _ p + a _ {2p - 1} + \dots = 0, \\
& a _ 2 + a _ {p + 1} + a _ {2p} + \dots = 0, \\
& \dots \\
& a _ {p - 1} + a _ {2p - 2} + a _ {3p - 3} + \dots = 0
\end{align} \tag{E.2}
\]
が成立する。これが求める必要十分条件である。
以下 (E.2) を、どのような素数 $p$ が充しうるか考える。 $p \leq N$ については素数を全て列挙して愚直に調べて問題ない。 $p > N$ なる素数については、 (E.2) は全部 $a _ k = 0$ の形 ($k = 0, 1, \dots, N$) になるので、特に $a _ N = 0$ が成立する必要がある。どれでもいいのだけれども $a _ N \neq 0$ であることは問題文の仮定から保証されるので、これを使おうという訳である。つまり $\mathbb{Z}$ 上 $p | \lvert a _ N \rvert$ となる素数 $p$ を全列挙してそれらを調べれば良い。これで間に合う。
解法の正当化
以下、環は $0 \neq 1$ を充たす可換環とする。
命題 1： $R$ を環とする。 $f(x), g(x) \in R[x]$, $g(x) \neq 0$ とする。 $d = \deg g$ とする。 $g(x)$ の最高次係数は $R$ の可逆元とする。このとき、 \[ f(x) = q(x) g(x) + r(x) \] かつ $\deg r < d$ を充たす $q(x), r(x) \in R[x]$ が一意的に存在する。
証明：省略する。適当な代数学の参考書を参照。
命題 2 (剰余定理)： $R$ を環とする。 $f(x) \in R[x]$, $a \in R$ とする。このとき、 \[ f(x) = (x - a) q(x) + r \tag{E.3} \] を充たす $q(x) \in R[x]$, $r \in R$ が一意的に存在し、さらに $r = f(a)$ が成立する。
証明：命題 1 より、前半が従う。後半は (E.3) に $x = a$ を代入すると従う。
系 3 (因数定理)： $R$ を環とする。 $f(x) \in R[x]$, $a \in R$ とする。このとき、 $(x - a) | f$ と $f(a) = 0$ は同値である。
証明：命題 2 の後半より直ちに出てくる。どちらも $r = 0$ と同値である。
定理 4： $R$ を整域とする。 $f(x) \in R[x]$ とする。このとき、次の (a) または (b) が成立する。
(a) $f(x) = 0$ である。
(b) $f(x)$ の根の個数は $d = \deg f$ 個以下である。
証明： (a) でないと仮定する。(b) の成立を $d \in \mathbb{N}$ についての帰納法で示す。まず $d = 0$ のとき、 $f(x)$ は $0$ でない定数であるから、 $f(x)$ は根を持たない。ゆえに結論は成立する。そこで $k \in \mathbb{N}$ に対し、 $d = k$ での成立を仮定し $d = k + 1$ での成立を示す。いま $f(x)$ は根 $\alpha \in R$ を持つと仮定する。このとき、命題 3 より、 $f(x) = (x - \alpha) q(x)$, $\deg q = k$ を充たす $q(x) \in R[x]$ が存在する。 $\beta \neq \alpha$ を充たす $\beta \in R$ が $f$ の根であると仮定する。このとき $0 = f(\beta) = (\beta - \alpha) q(\beta)$ が成立する。 $R$ は整域であるから $q(\beta) = 0$ である。したがって $\beta$ は $q(x)$ の根である。帰納法の仮定により、このような $\beta$ は $k$ 個以下である。よって $f(x)$ の根は $(k + 1)$ 個以下である。これが示すことであった。
問題に戻る。 $p$ が素数のとき、 $K = \mathbb{Z} / p \mathbb{Z}$ は体であるから整域である。よって上の定理 4 を適用できる。 $f(x) \in K[x]$ は相異なる $p$ 個の根 $0, 1, \dots, p - 1$ を持つので、 (1) の $f$ は $K[x]$ の元として $0$ であるとわかる。
以下の本を参照した。
私のように代数学が専門でなく得意でない人が基本事項を調べるときは、できるだけ具体例が証明付きで述べられている本を持っておいて必要に応じて参照するといいと思う。
ポイント
「冷静に考えれば解ける」と rng さんがおっしゃっていましたが、確かに解けるように思う。ただし多項式環の定理を忘れていたので自信を持っては答えられなかっただろう。