AtCoder Regular Contest 115 感想

#総合結果
* [Score] 1200 pts
* [Time] 29:47 + <font color="red"> 05:00 $\times$ 0 </font> = 29:47
* [Ranking] 341 st [Rated内: 324 th]
* [Performance] <font color=#0000FF> 1976　</font>
* [Rating] <font color=#0000FF> 1874 </font> → <font color=#0000FF> 1885 </font> (+11)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#804000> A問題 </font>|300 pts|19:16|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc115/submissions/21137499)||
|<font color=#804000> B問題 </font>|400 pts|10:10|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc115/submissions/21136304)||
|<font color=#804000> C問題 </font>|500 pts|<b>29:47</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc115/submissions/21139045)<br>$O(N \sqrt{N} \log N)$|[■](https://atcoder.jp/contests/arc115/submissions/21152681)<br>$O(N \sqrt{N})$|
|<font color=#C0C000> D問題 </font>|0 pts|--:--|<font color="red"> </font>|[]()||
|<font color=#C0C000> E問題 </font>|0 pts|--:--|<font color="red"> </font>|[]()||
|<font color=#AEB3B5> F問題 </font>|0 pts|--:--|<font color="red"> </font>|[]()||
|<b>Total</b>|<b>1200 pts</b>|<b>29:47</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#804000> A問題 (300pts, diff: 641) </font> [Two Choices](https://atcoder.jp/contests/arc115/tasks/arc115_a)

$M$ 問の解答の結果 $S,T$ に対して, 関係 $\sim$ を $S \sim T$ で $S, T$ において得点が同じになるような正解の方法が存在することと定義する.

ここで, この $S \sim T$ と, $S, T$ で解答が異なる問題の数が偶数問であることは同値である.

(証明) 必要ならば, 問題を並び替えて, $1$ 問目から, $k$ 問目までの解答が異なっているとしてもよい. ここで, 全ての問題が2択であることから, どちら一方のみの解答を正解にすることができ, しなければならない.

* $k$ が偶数のとき ($k=2l$): $1$ 問目から, $l$ 問目までは $S$ の解答を正解に, $l+1$ 問目から $2l=k$ 問目までは $T$ の解答を正解にすることによって, $S, T$ の正解数が同じにすることができる.
* $k$ が奇数のとき: 全ての問題において, $S, T$ のうちの一方のみを正解にしなければならないが, $k$ が奇数であることから, $S, T$ の正解数を同じにすることができない.

このことから, $\sim$ は同値関係になることがわかる.
* (反射律): 自明
* (対称律): 自明
* (推移律): $S \sim T, T \sim U$ とする. $S,T,U$ における $i$ 問目の解答を $S[i], T[i], U[i]$ とする. 以下, 演算は全て $\mathbb{Z}/2 \mathbb{Z}$ の演算とする. このとき, $S[i], T[i], U[i] \in \\{0,1\\}$ から,

```math
\begin{align*}
[S[i] \neq U[i]]
&=S[i] \oplus U[i] \\\\
&=(S[i] \oplus T[i]) \oplus (T[i] \oplus U[i]) \\\\
&=[S[i] \neq T[i]] \oplus [T[i] \neq U[i]]
\end{align*}
```

であることから, $S,U$ において解答が異なる問題数の偶奇は,
$$\bigoplus_{i=1}^M [S[i] \neq U[i]]=\bigoplus_{i=1}^M ([S[i] \neq T[i]] \oplus [T[i] \neq U[i]])=\left(\bigoplus_{i=1}^M [S[i] \neq T[i]] \right) \oplus \left(\bigoplus_{i=1}^M [T[i] \neq U[i]] \right)$$
である. ここで, $S \sim T, T \sim U$ という仮定から,
$$\bigoplus_{i=1}^M [S[i] \neq T[i]]=\bigoplus_{i=1}^M [T[i] \neq U[i]]=0$$
なので,
$$\bigoplus_{i=1}^M [S[i] \neq U[i]]=0 \oplus 0=0$$
であり, $S \sim U$ となることがわかる.

商集合 $X:=\\{0,1\\}^M/\sim$ の構成を考える. ここで, 任意の $S,T$ において, $S,T$ において異なる問題の数は奇数か偶数であることと, $(0,\dots,0,0) \not \sim (0,\dots,0,1)$ であることから,
$$X=[(0,\dots,0,0)] \cup [(0,\dots,0,1)]$$
である. 以下, $A_0=[(0,\dots,0,0)], A_1=[(0,\dots,0,1)]$ とする.

$S \in A_0, T \in A_1$ ならば, 上で述べたことから, 正解数が同じになるような事はない. また, $S,T \in A_0$ または $S,T \in A_1$ ならば, 同値類の定義から, 正解数を同じにすることができる.

以上から, 求めるべき解答は $|A_0||A_1|$ であることがわかる.

ここで, $S \in A_0$ か $S \in A_1$ かどうかの判定についてだが, $(0,\dots,0,0) \in A_0$ であることから, $S$ と $(0,\dots,0,0)$ における解答が異なる問題の数は $S$ にある $1$ の数と一致する. このことから, $S$ にある $1$ の数を $p$ とすると, $S \in A_{p \pmod 2}$ である.

以上のことを実装すると, 計算量 $O(NM)$ で求めることができる.

##<font color=#804000> B問題 (400pts, diff: 629) </font> [Plus Matrix](https://atcoder.jp/contests/arc115/tasks/arc115_b)

$I,J$ を $\displaystyle C_{I,J}=\min_{1 \leq i,j \leq N} C_{i,j}$ を満たすように取る. また, $\displaystyle \alpha=\min_{1 \leq i,j \leq N} C_{i,j}$ とする. このとき, $E=(E_i)\_{i=1}^N, F=(F_j)\_{j=1}^N$ を以下のようにする.
$$E_i=C_{i,J}-\alpha,\quad F_j=C_{I,j}$$

このとき, 条件を満たす列 $A,B$ が存在することと, 上で定義した $E,F$ が条件を満たすことが同値になる.

まず, $\alpha$ の定義から, $E_i, F_j \geq 0$ である. このことから, 必要条件は自明なので, 十分条件を示す.

また, 十分条件についても, $A,B$ から適当な1つの項の値を決定すると, 残りの項の値全てがたちまちに決定されることから, どこか1つの項を適当に決め打ちしても良い (ただし, 負の項を許容することになる). そこで, 上では $E_I=0$ とすることを意味している. ここで, もし $E,F$ が条件を満たしていないとすると, $I$ 行目と $J$ 列目を満たそうとすると, 和に関する条件を満たさないことを意味する.

この $E,F$ の構成は $O(N)$ ででき, 条件を満たすかは $O(N^2)$ で確認できる.

##<font color=#804000> C問題 (500pts, diff: 706) </font> [ℕ Coloring](https://atcoder.jp/contests/arc115/tasks/arc115_c)

以下で定義される列 $B=(B_i)_{i=1}^N$ が解答の一つである. ただし, 最小除外数については, $1$ から数えるものとする.
$$B_j={\rm mex}~\\{B_i~|~i<j,iはjの約数\\}$$
この数列の構成について, Eratosthenes の篩を利用した高速素因数分解を利用することにより, 計算量 $O(N \sqrt{N} \log N)$ で求めることができる. なお, 普通に素因数分解しても計算量は $O(N \sqrt{N})$ となるが, 定数倍の差により, 前者の方が高速である.

##<font color=#C0C000> D問題 (600pts, diff: 2325) </font> [Odd Degree](https://atcoder.jp/contests/arc115/tasks/arc115_d)
(正解でき次第加筆)

##<font color=#C0C000> E問題 (700pts, diff: 2363) </font> [LEQ and NEQ](https://atcoder.jp/contests/arc115/tasks/arc115_e)
(正解でき次第加筆)

##<font color=#AEB3B5> F問題 (1000pts, diff: 3336) </font>[Migration](https://atcoder.jp/contests/arc115/tasks/arc115_f)
(正解でき次第加筆)