DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選
Updated:
DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選
Source codes
Solutions
A - チップ・ストーリー ～無色編～
$4^N$ を出力する。 puts 4 ** gets.to_i で終わる。
B - チップ・ストーリー ～漆黒編～
各マスに対して、頂点の 4 点がいずれも黒マスかどうかを判定する。 $0$ - indexed とする。 $(x, y) \in N^2$ に対し(ここで $N = \{ 0, \dots, N - 1 \}$ は集合の意味である)、 $(x, y)$, $(x + 1, y)$, $(x, y + 1)$, $(x + 1, y + 1)$ がいずれも黒色の領域 $D$ に含まれていればそのマスは黒色に塗りつぶされている。 $(x, y) \in D$ であるための条件は、 $- x + N / 2 \leq y \leq - x + 3N / 2$ かつ $x - N/2 \leq y \leq x + N / 2$ であることである。
ポイント
計算機の除算は切り捨てなので、最初から $X = 2x$, $Y = 2y$ とするとよろしいかと思う。この場合条件は $- X + N \leq Y \leq - X + 3N$ かつ $X - N \leq Y \leq X + N$ である。
C - チップ・ストーリー ～白銀編～
$0$ - indexed とする。 $L = 10$ とする。まず条件は \[ (\forall i \in L)(\forall j \in L)(P _i Q _j \leq N) \] である。最大値の定義により、これは以下と同値である。 \[ \max _{i \in L} P _i \max _{j \in L} Q _j \leq N. \tag{C.1} \] そこで $k = 1, \dots, N$ に対し、$\max _{i \in L} P _i = k$ かつ (C.1) を充たす数を高速に求めればよろしい。 $\max _{i \in L} P _i = k$ を充たす $(P _0, \dots, P _{L - 1}) \in {\mathbb{N} _+}^L$ の個数は $k^L - (k - 1)^{L}$ 個である。このもとで (C.1) 式は $\max _{j \in L} Q _j \leq N / k$ であることと同値である(ただし割り算は計算機の割り算)。よって $(Q _0, \dots, Q _{L - 1}) \in {\mathbb{N} _+}^L$ の個数は $(N / k)^L$ 個である。したがって答えは以下で与えられる。 \[ \sum _{k = 1}^N (k^L - (k - 1)^L) (N / k)^L. \]
ポイント
DP とかでなくて助かった。
D - チップ・ストーリー ～黄金編～
考察
$L = 31$ とする。 $2 \leq p < L$ とする。 $x$ の $p$ 進展開を $x = \sum _i A _i p^i$ とする。このとき、 \[ x = \sum _i A _i p^i = \sum _i A _i = a[p] \text{ in } \mathbb{Z}/(p - 1)\mathbb{Z} \] が必要である。したがって、 $x$ の候補は中国剰余定理の復元方法で求めることができる。
今回は安直な実装を試みる。
理論と実装方法
$p _1, \dots, p _K \in \mathbb{N}$ を 全て素数 とする。今回の場合 $2, 3, 5, \dots, 29$ である。 $b _1, \dots, b _K \in \mathbb{Z}$ とする。 $x \in \mathbb{Z}$ であって、 \[ x = b _i \text{ in } \mathbb{Z}/p _i \mathbb{Z} \ \ (i = 1, \dots, K) \tag{D.1} \] を充たすものを 1 つ求める。 $x$ を、 $t _0, \dots, t _{K - 1} \in \mathbb{Z}$ を用いて \[ x = \sum _{i = 0}^{K - 1} t _i \left( \prod _{j = 1}^i p _j \right) \tag{D.2} \] の形で求める。 (D.2) を $\mathbb{Z}/p _1 \mathbb{Z}$ に落とすと(標準全射で両辺を移すと)、 \[ t _0 = x = b _1 \text{ in } \mathbb{Z}/p _1 \mathbb{Z} \tag{D.3} \] となる。次に、 $t _0, \dots, t _{k-1}$ を求めた段階で $t _k$ を求める。(D.2) を $\mathbb{Z}/p _{k + 1} \mathbb{Z}$ に落とすと、 \[ x = \sum _{i = 0}^{k} t _i \left( \prod _{j = 1}^i p _j \right) \text{ in } \mathbb{Z} / p _{k + 1} \mathbb{Z} \tag{D.4} \] である。よって、 \[ t _k = \left(b _{k + 1} - \sum _{i = 0}^{k - 1} t _i \left( \prod _{j = 1}^i p _j \right) \right) \left( \prod _{j = 1}^k p _j \right)^{-1} \text{ in } \mathbb{Z}/p _{k+1} \mathbb{Z}. \tag{D.5} \] と求まる。以上で $x$ が求まる。具体的には最初に $x = 0$, $m = 1$ としておき、以下のように実装すれば十分である。
def calc_x()
primes.each{|q, b|
t = ((b + q - x % q) * Solve.inv(m, q)) % q
@x += m * t
@m *= q
}
end
素数 $p \in \mathbb{N}$ に対し、 $\mathbb{Z}/ p \mathbb{Z}$ は体である。 $y \in (\mathbb{Z}/ p \mathbb{Z})^\times$ に対し、その逆元は、フェルマーの小定理から $y^{-1} = y^{p - 2} ~ \text{in} ~ \mathbb{Z}/ p \mathbb{Z}$ である。これは安直に求めることができる。
(D.3), (D.4), (D.5) より、上で求まった (D.2) の $x$ は (D.1) の解である。よって中国剰余定理より、 (D.1) の解全体は \[ S = \{ x + Mn \in \mathbb{Z} \mid n \in \mathbb{Z} \} \] である。ここで $M = \prod _{j = 1}^K p _j$ である。今回の場合 $M \approx 6 \times 10^9$ であるから、 $N \in S$ かつ $1 \leq N \leq 10^{12}$ を充たすものはせいぜい $200$ 個程度である。このうち条件を充たすものが見つかったら出力し、そうでないならば “invalid” を出力すればよろしい。
参考文献
ポイント
考察の部分ができてなかったので、得点できなかったのはどうしようもなかろう。
どうでもいい余談
私はフェルマーの小定理で逆元求めるのあまり好きではない。いつもは拡張ユークリッド互助法で求めている。その理由は、実にくだらないのだけど……
私の卒業してしまった高校は、田舎の底辺高校で、それでも県内最高の自称進学校だから、保護者からカネを集めて、東京の大手予備校に高いカネを払って講師を派遣してもらって授業するというのをやる。もちろん大手予備校からすればこれは絶好のカモで、東京の受験業界では大したことでなくても、少し進んだことを少し授業するとありがたがってもらえる。楽な仕事というわけである。そこで大抵高校 1 - 2 年生向けに選ばれるのが( $\mathbb{Z}/p\mathbb{Z}$ の)フェルマーの小定理だったりするわけです。それを教わった生徒で「俺はフェルマーの小定理を習ったんだぞ〜」と言って自慢しているのを見て、なんて低レベルなんだろうと思い出す。田舎でしか自慢できないようなことを、自分で勉強したことならともかく、他人から習ったことを自慢するなんて、情けないと思う。
実際フェルマーの小定理を独学して使いこなしてプロコンの問題を解くような中学生・高校生はこの世にたくさんいるわけで。そういうこと思い出すので今まであまり使いたくはなかった。今回の場合法 $p$ が変わり、かつ、 1 つの法 $p$ に対し 1 つの逆元を求めればいいので、フェルマーの小定理がよかろうと思う。
なお、フェルマーの小定理は、専門的には「数論の定理」ではない。「大学 3 年生(大学によっては 2 年生)の必修で習うような群論の定理」である。中国剰余定理も同様のレベルの環論の定理である。これらを数論として語るのは、あまりにも数論を専門とする人に申し訳ない。そのつもりはないということを申し添えておく。念のため中国剰余定理を書いておく。
定理(中国剰余定理)： $R$ を単位元を持つ環とし、 $I _1, \dots, I _K \subset R$ を互いに素なイデアルとする。 $I = \bigcap _{i = 1}^K I _i$ とする。このとき、写像 $p \colon R \to \prod _{i = 1}^{K} (R/ I _i)$, $p(x) = (x + I _1, \dots, x + I _K)$ は全射であり、 $\ker p = I$ である。すなわち同型 $R / I \cong \prod _{i = 1}^K (R/ I _i)$ が成立する。
Others
多分本戦に進めたと思う。 1 年ぶりか 2 年ぶりかな。