AtCoder Beginner Contest 212 感想

#総合結果
* [Score] 2100 pts
* [Time] 64:37 + <font color="red"> 05:00 $\times$ 1 </font> = 69:37
* [Ranking] 121 st [Rated内: 35 th]
* [Performance] <font color=#FF8000> 2400 </font>
* [Rating] <font color=#0000FF> 1904 </font> → <font color=#0000FF> 1965 </font> (+61)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|07:18|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc212/submissions/24653041)||
|<font color=#808080> B問題 </font>|200 pts|04:33|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc212/submissions/24650421)||
|<font color=#808080> C問題 </font>|300 pts|08:45|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc212/submissions/24654320)||
|<font color=#804000> D問題 </font>|400 pts|14:08|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc212/submissions/24658761)||
|<font color=#00C0C0> E問題 </font>|500 pts|21:33|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc212/submissions/24663787)||
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> (2 Penalties) </font>|||
|<font color=#C0C000> G問題 </font>|600 pts|<b>64:37</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc212/submissions/24681376)||
|<font color=#FF8000> H問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc212/submissions/24714528)|
|<b>Total</b>|<b>2100 pts</b>|<b>64:37</b>|<b><font color="red"> 1 Penalty </font></b>|||

#問題ごとの感想
##<font color=#808080> A問題 (100pts, diff: 5) </font> [Alloy](https://atcoder.jp/contests/abc212/tasks/abc212_a)

純金, 純銀, 合金の条件が与えられているので, 入力と出力と比較を愚直に書けば良い.

##<font color=#808080> B問題 (200pts, diff: 64) </font> [Weak Password](https://atcoder.jp/contests/abc212/tasks/abc212_b)

入力において, $X_1X_2X_3X_4$ の間にスペースがないので, 一旦文字列として入力してから, 1文字目, 2文字目, 3文字目, 4文字目を整数に変換すれば良い.

なお, $A$ が $B$ の次の数字であるかどうかの判定で, $A=(B+1) \pmod{10}$ を判定することで, 場合分けを減らすことができる.

##<font color=#808080> C問題 (300pts, diff: 246) </font> [Min Difference ](https://atcoder.jp/contests/abc212/tasks/abc212_c)

$A,B$ は昇順に並んでいると仮定しても良い. つまり,

$$A_1 \leq \dots \leq A_N ,\quad B_1 \leq \dots \leq B_M$$

とする. なお, 以降では, 場合分けを減らすために, $B_0=-\infty, B_{M+1}=+\infty$ とする.

このとき,

$$\min_{1 \leq i \leq N} \min_{1 \leq j \leq M} |A_i-B_j|=\min_{1 \leq i \leq N} \left(\min_{1 \leq j \leq M} |A_i-B_j| \right)$$

であることから, $A_i$ を固定することにする. このとき, $B_{j_i} \leq A_i \leq B_{j_i+1}$ なる整数 $j_i~(1 \leq j_i \leq M)$ が存在する. このとき,

$$\min_{1 \leq j \leq M} |A_i-B_j|=\min(|A_i-B_{j_i}|, |A_i-B_{{j_i}+1}|)$$

であるので,

$$\min_{1 \leq i \leq N} \min_{1 \leq j \leq M} |A_i-B_j|=\min_{1 \leq i \leq N} 
 \left(\min(|A_i-B_{j_i}|, |A_i-B_{{j_i}+1}|) \right)$$

である. ここで, $j_i$ を求めるためには, 二分探索を用いることにより, 各 $i$ に対して, $O(\log M)$ で求めることができ, $i=1, \dots, N$ と動かすことにより, 最小値を $O(N \log M)$ で求めることができる.

最初に与えられる数列は昇順とは限らないことに注意すると, 最初にソートをすることにより, 問題を解くことができる. よって, 計算量は, 最初のソートも合わせて,$O(N \log N+M \log M+N \log M)=O((N+M)(\log N+\log M))$ である.


##<font color=#804000> D問題 (400pts, diff: 775) </font> [Querying Multiset](https://atcoder.jp/contests/abc212/tasks/abc212_d)

新たな変数 $Y$ を用意して, $Y=0$ と初期化する.

このとき, 操作 2, 操作 3を以下のように対応付ける.

* 操作2: $Y$ に $X_i$ を加える.
* 操作3: 最小値が書かれたボールを取り出し, そのボールに書かれている整数を $Z$ としたとき, $Y+Z$ を出力する.

このように, ボールの値を加算するという操作を, 別の所で加算し, 出力の際に辻褄を合わせるようにする. 実際, 整数 $a,b,x$ に対して, $a \leq b$ であることと, $a+x \leq b+x$ であることが同値であることから, この方法は正当である.

操作1 を考える. ここで, 元の問題分において, $X$ と書かれたボールを加えることは, 新たに対応付けた操作では, $X-Y$ と書かれたボールを加えることに対応付けられる. 実際, $(X-Y)+Y=X$ である.

最後に, 整数を加えたり, 最小値を取り出すことを高速に行うために, データ構造として, ヒープを用いる (優先度付きキュー). このことにより, 計算量 $O(Q \log Q)$ で解くことができる.

##<font color=#00C0C0> E問題 (500pts, diff: 1410) </font> [Safety Journey](https://atcoder.jp/contests/abc212/tasks/abc212_e)

動的計画法で解く. ${\rm DP}[v,k]$ で, 頂点 $1$ から始まり, 頂点 $v$ で終わる長さがちょうど $k$ のパス全体の集合とする.

ベースケースは, $k=0$ のときで,
$${\rm DP}[v,0]=\begin{cases} 1 & (v=1) \\\\ 0 & (v \neq 1) \end{cases}$$
である.

次に遷移を考える. $S_v$ で, 頂点 $v$ と隣接している頂点 $u$ 全体の集合とする. このとき, 最後の頂点 $v$ がどの頂点から到達したものかという分割をすることにより

$${\rm DP}[v,k]=\sum_{u \in S_v} {\rm DP}[u,k-1]$$

が成り立つ.

この動的計画法における ${\rm DP}[1,K]$ が解答だが, このまま計算すると, 計算量が $O(N^2 K)$ となり, 間に合わない.

しかし, $u \not \in S_v$ なる $(v,u)$ の組が $M$ 個しかないことから, 以下のようにして高速化できる.

* 各 $v$ に対して, $L_v:=\\{u \mid \exists j {\rm ~s.t.~} (U_j, V_j)=(u,v) {\rm ~or~} (U_j,V_j)=(v,u)\\}$ とする.
* $F_k:=\sum_{v=1}^N {\rm DP}[v,k]$ とする.
* このとき, $S_v \coprod L_v =\\{1, \dots, N \\} \setminus \\{v\\}$ であるので, $\displaystyle {\rm DP}[v,k]=F_k-\left(\sum_{u \in L_u} {\rm DP}[u,k-1]+{\rm DP}[v,k-1] \right)$ である.

このことから, 各 $k$ において, ${\rm DP}[1,k], \dots, {\rm DP}[N,k]$ を計算量 $O(N+M)$ で求めることができるから, 解答を $O((N+M)K)$ で求めることができる.

##<font color=#C0C000> F問題 (500pts, diff: 2332) </font>[Greedy Takahashi](https://atcoder.jp/contests/abc212/tasks/abc212_f)

(正解でき次第更新予定)

##<font color=#C0C000> G問題 (600pts, diff: 2150) </font>[Power Pair](https://atcoder.jp/contests/abc212/tasks/abc212_g)

$P$ は素数である. このとき, $\mathbb{Z}/P\mathbb{Z}$ には原始根 $g \in \mathbb{Z}/P\mathbb{Z}$ が存在する. なお, 原始根とは,
$$g^0, g^1, \dots, g^{P-2} \neq [1], \quad g^{P-1}=[1]$$
を満たす元のことである.

$g \in \mathbb{Z}/P \mathbb{Z}$ を原始根とする. このとき, 以下が成り立つ.

* $g^0, g^1, \dots, g^{P-2}$ は $[1]\_P, \dots, [P-1]\_P$ の並び替えである.
* $g^a=g^b \iff a \equiv b \pmod{P-1}$ である.

この性質を利用して, 問題を解く. なお, $x \in \mathbb{Z}/P\mathbb{Z}$ に対して, $T_x:=\\# \\{y \in \mathbb{Z}/P \mathbb{Z} \mid \exists n \in \mathbb{N}_{>0} {\rm ~s.t.~} x^n=y \\}$ とする. つまり, $x$ を固定したときの $y$ の個数である.

* $x=[0]\_P$ のとき<br>このとき, $g^0, \dots, g^{P-2}$ の中に $[0]\_P$ は存在しない. しかし, 任意の正の整数に対して, $x^n=[0]^n\_P=0$ なので, $y=[0]\_P$ しか条件を満たさない. よって, $T_{[0]_P}=1$ である.
* $x \neq [0]\_P$ のとき<br>このとき, $0 \leq a < P-1$ で $x=g^a$ とする. ここで, $y \in (\mathbb{Z}/P \mathbb{Z})^\times$ が条件を満たすかどうかを考える. ここで, $y=g^b~(0 \leq b <P-1)$ とする. ここで, 式変形をする.

```math
\begin{align*}
\exists n \in \mathbb{N}_{>0} {\rm ~s.t.~} x^n=y
&\iff \exists n \in \mathbb{Z} {\rm ~s.t.~} x^n=y \\
&\iff \exists n \in \mathbb{Z} {\rm ~s.t.~} g^{an}=g^b \\
&\iff \exists n \in \mathbb{Z} {\rm ~s.t.~} an \equiv b \pmod{P-1} \\
&\iff \exists n,k \in \mathbb{Z} {\rm ~s.t.~} an=b+(P-1)k \\
&\iff \exists n,k \in \mathbb{Z} {\rm ~s.t.~} an-(P-1)k=b \\
&\iff \gcd(a,P-1)|b \\
\end{align*}
```

ここで, $[1]\_P,[2]\_P, \dots, [P-1]\_P$ と, $g^0, g^1, \dots, g^{P-2}$ の間には, 1対1の対応 (全単射) があることから, $y \in (\mathbb{Z}/P \mathbb{Z})^\times$ について考える問題から, $b$ について考える問題に帰着された.

上での同値変形から, $T_x$ は以下と等しいとする.

> $x=g^a~(0 \leq a <P-1)$ とする. このとき, $\gcd(a,P-1)|b$ を満たす整数 $b~(0 \leq b <P-1)$ はいくつか?

なお, この問題の答えは, $\dfrac{P-1}{\gcd(a,P-1)}$ である.

$O(P)$ が通る範囲ならば, 愚直に $\gcd(a,P-1)$ を求めることによって計算できるが, $P \leq 10^{12}$ という制約から間に合わない.

しかし, $\gcd(a,P-1)$ の取りうる整数に制限があることを利用すると, 高速に求めることができる.

$\gcd(a,P-1)$ の取りうる値として可能なのは, $P-1$ の約数である. $P-1$ の約数を $d_1, \dots, d_k$ とする. このとき, $0 \leq a <P-1$ に対して, $\gcd(a,P-1)=m$ であることの必要十分条件は,

* $a$ は $m$ の倍数
* $a$ は $P-1$ の約数かつ $m$ の倍数である全ての整数 $l$ に対して, $l$ の倍数ではない.

このことを利用して, $P-1$ の各約数 $d$ に対して, $M_d$ で, $\gcd(a,P-1)=d, 0 \leq a <P-1$ を満たす整数の個数とする. ただし, $g^0=g^{P-1}$ なので, $a$ の範囲について, $1 \leq a \leq P-1$ としてもよい. このとき, $M_d$ は以下の式で表せる.
$$ M_d=\left \lfloor \dfrac{P-1}{d} \right \rfloor-\sum_{l \in E_d} M_l$$

ただし, $E_d$ は $P-1$ の約数かつ, $d$ の倍数の整数全体の集合である. この $M_d$ は, $d$ が大きい方からもとめることで, $O(k^2)$ で求める事ができる.

以上のことから, 求めるべき答えは
$$1+\sum_{d: P-1 の約数} M_d \cdot \dfrac{P-1}{d}$$
であり, 計算量は, $P-1$ の約数 $d_1, \dots, d_k$ を求めるパートと, $T_{d_i}$ を求めるパートがボトルネックになる可能性があり, 計算量は $O(\sqrt{P}+k^2)$ である. なお, $P \leq 10^{12}$ においては, $k \leq 6270$ なので, 十分高速である.

### 補足
この問題を群論の言葉で言い換える.

* 原始根の存在から, $(\mathbb{Z}/P\mathbb{Z})^\times \simeq \mathbb{Z}/(P-1)\mathbb{Z}$ である.
* $T_x$ は巡回群 $\langle x \rangle$ の位数と一致する.
* $\langle x \rangle$ の位数は, $P-1$ の約数であり (Lagrange) , $x$ の位数 $\operatorname{ord}(x)$ と等しい.

##<font color=#FF8000> H問題 (600pts, diff: 2741) </font>[Nim Counting](https://atcoder.jp/contests/abc212/tasks/abc212_h)

この石取りゲームは, Nim と呼ばれるゲームである. この Nim には以下のような必勝判定法がある.

> $M$ 個の山にはそれぞれ $S_1, \dots, S_M$ 個ある. このとき,
> 先手必勝 $\iff S_1 \oplus \dots \oplus S_M \neq 0$
> 後手必勝 $\iff S_1 \oplus \dots \oplus S_M=0$
> ただし, $\oplus$ は Bit 毎の排他的論理和

このとき Hadamard 変換 $\mathcal{H}$ と逆 Hadamard 変換 $\mathcal{H}^{-1}$ を用いることにより正解を導くことができる. ここで, Hadamard 変換, 逆 Hadamard 変換は以下のような性質がある.

* (線形性): 実数 $s,t$ と長さ $2^n$ の実数列 $A,B$ に対して,
$$\mathcal{H}(sA+tB)=s \mathcal{H}A+t \mathcal{H}B,\quad \mathcal{H}^{-1}(sA+tB)=s \mathcal{H}^{-1}A+t \mathcal{H}^{-1}B$$
* (逆写像の関係): 実数列 $A$ に対して, $\mathcal{H} \mathcal{H}^{-1}=\mathcal{H}^{-1} \mathcal{H}=\mathcal{I}$ である. ただし, $\mathcal{I}$ は恒等写像.
* (畳み込みと積): $A=(A_i), B=(B_i), C=A*B$ としたとき, $\mathcal{H}C=(\mathcal{H}A) \cdot (\mathcal{H}B)$ である. ここで, 畳み込み $A*B$ とは, $C=A*B$ としたとき
$$C_k=\sum_{\substack{0 \leq i,j <2^n \\\\ i \oplus j=k}} A_i B_j$$
である. また, $P=(P_i), Q=(Q_i)$ に対して, $P \cdot Q=(P_i Q_i)$ (各点積) とする.

ここで, (畳み込みと積) から, 以下の事がわかる.
$$\mathcal{H}(\underbrace{A*\dots*A}\_{m~{\rm times}})=\underbrace{(\mathcal{H} A) \cdot \dots \cdot (\mathcal{H} A)}_{m~{\rm times}}$$

よって, $\underbrace{A*\dots*A}\_{m~{\rm times}}$ のことを $A^{\*^m}$ と書くことにすると, 

$$(A^{\*^m})\_k=\sum_{\substack{0 \leq i_j < 2^n \\\\ i_1 \oplus \dots i_m=k}} A_{i_1} \dots A_{i_m} $$

であるが, $A^{\*^m}=\mathcal{H}^{-1}((\mathcal{H} A)^m)$ になることが分かった.

---
このことから, 以下のように計算することで正解を導くことができる.

長さ $l:=2^{16}$ の列 $L$ (0-index) を

$$L_i=\begin{cases} 1 & (\exists j {\rm ~s.t.~} i=A_j) \\\\ 0 & ({\rm otherwise}) \end{cases}$$

としたとき, $(L^{\* m})_i$ のは石の数が $m$ のときに各山の石の xor 和が $i$ になるような方法の数を意味する. よって,

$$E:= \sum_{m=1}^N L^m=\sum_{m=1}^N \mathcal{H}^{-1} ((\mathcal{H} L)^m)=\mathcal{H}^{-1} \left(\sum_{m=1}^N (\mathcal{H} L)^m \right)$$

であることから, 1回ずつのHadamard 変換 と 逆 Hadamard 変換によって $B$ を求めることができる.  ここで, 各点積について, 

$$\sum_{m=1}^N r^m=\begin{cases} \dfrac{r(r^N-1)}{r-1} & (r \neq 1) \\\\ N r & (r=1) \end{cases}$$

である.

よって, 求めるべき答えは

$$\sum_{i=1}^N E_i$$

である. 計算量は長さ $N$ のHadamard 変換 と 逆 Hadamard 変換で $O(l \log l)$ なので, 全体の計算量は $O(l (\log l+\log N))$ である.