AtCoder Regular Contest 114 感想

#総合結果
* [Score] 700 pts
* [Time] 22:45 + <font color="red"> 05:00 $\times$ 0 </font> = 22:45
* [Ranking] 503 rd [Rated内: 481 st]
* [Performance] <font color="blue"> 1849　</font>
* [Rating] <font color=#0000FF> 1877 </font> → <font color=#0000FF> 1874 </font> (-3)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#804000> A問題 </font>|300 pts|007:07|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc114/submissions/20930434)||
|<font color=#008000> B問題 </font>|400 pts|<b>021:45</b>|<font color="red"> </font>|[■[^2]](https://atcoder.jp/contests/arc114/submissions/20933810)<br>(強連結成分のライブラリは[naniwazu](https://atcoder.jp/users/naniwazu)さん作成)|[■](https://atcoder.jp/contests/arc114/submissions/20951403)<br>(自作のライブラリ)|
|<font color=#C0C000> C問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|<font color=#C0C000> D問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|<font color=#FF8000> E問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|<font color=#808080> F問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|Total|<b>700 pts</b>|<b>021:45</b>|<b><font color="red"> No Penalties </font>|</b>||

[^2]: 2行目に"Thanks for" とあるが, この場合, 正しくは "Thanks to" である (Thanks for ... は ... してくれてありがとうという意味).

#問題ごとの略解
##<font color=#804000> A問題 (300pts, diff: 750) </font> [Not coprime](https://atcoder.jp/contests/arc114/tasks/arc114_a)
以下の事実に気づかなければならない: 整数 $x,y$ が互いに素ではない $\iff x,y$ を両方割り切る<b>素数</b>が存在する.

この事実を利用する. $2 \leq X_i \leq 50$ という制約から, 2つの整数に共通する素数になりうる素数は $50$ 以下の素数である. つまり, $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$ の $15$ 個である. この $15$ 個の素数全体の集合を $P$ とする.

ここで, 答えになる整数を $Z$ としたとき, $Z$ の素因数分解に現れる素数は全て $P$ の元である. 実際, $P$ の元でない素因数が現れた場合, その素因数で割った整数も, 上で述べた事実から条件を満たすことがわかり, 最小性に矛盾する.

また, $Z$ の素因数分解における累乗は高々 $1$ である. これは, 上で述べた事実より, 重要なのは素因数の種類で累乗は影響しないことからわかる.

以上のことから, 整数 $Z$ は,
$$Z=2^{e_2} \cdot 3^{e_3} \cdot 5^{e_5} \cdots 47^{e_{47}} \quad (e_p \in \\{0,1\\}, p \in P)$$
と表すことができる. 

ここで, 各 $e_p$ は2択であり, $|P|=15$ であることから, 選択肢の総数は $2^{|P|}=32768$ と少ない. このことから, 全探索で上の事実を利用しながら条件を満たす全ての整数の最小値を求めると, その整数がそのまま答えになる.

##<font color=#008000> B問題 (400pts, diff: 1000) </font> [Special Subsets](https://atcoder.jp/contests/arc114/tasks/arc114_b)
$S:=[\\![N]\\!]$ から $S$ への関数 $f:S \to S$ を $f:S \to S;~k \mapsto f_k$ と書くことにする.

有向グラフ $D=(S,E)$ を $E=\\{(x,f(x)) \in S^2| x \in S\\}$ とする.  ここで, 空でない $S$ の部分集合 $T$ が条件を満たすための必要十分条件を考える.

結論から言ってしまうと, $T$ が条件を満たすための必要十分条件は, $T$ から誘導される部分グラフ $D[T]$ がいくつかのサイクル $C\_1, \dots, C\_K$ を用いて, $T=C_1 \oplus C_2 \oplus \dots C_k$ となることである.

* 十分条件: $f(T) \subset T$ かつ, $f|_T$ は単射という仮定がある. $T=\\{x_1, \dots, x_m\\}$ とする. $f(x_1), \dots, f(x_m)$ に対して, $f|_T$ は単射なので, $f(x_1), \dots, f(x_m)$ は相異なる $m$ 個の $T$ の元である. さて, $|T|=m$ であったので, 任意の $y \in T$ に対して, $y=f(x_i)$ なる $i$ が存在する. よって, $f|_T$ は全単射であることがわかった.

$f|_T$ は全単射であることがわかり, $T$ は有限集合なので, $f|_T$ は $\mathfrak{S}\_{|T|}$ の元と見なすことができる. ここで, 有限集合の置換は互いに交わらない巡回置換の積で表すことができる. これは $D[T]$ がいくつかのサイクルの直和で表せることを意味する.

* 必要条件: 1つのサイクル $C_i$ に着目する. このとき, $f(C_i)=C_i$ であることと, $f|_{C_i}$ が単射になることは明らかである. また, サイクルの直和にしても同様に条件を満たすことがわかる.

$D$ にある $K$ 個のサイクルを $C_1, \dots, C_K$ とする. これらはグラフの構成から互いに点素である. この $K$ 個から, 少なくとも $1$ 個のサイクルを選び, 直和をとれば条件を満たす. よって, 答えは空集合が禁止されていることから, $2^K-1$ である.

ここで, $D$ 上にあるサイクルは有向グラフにおける強連結成分を利用して数えることができるが, 実は $K$ は $D$ の弱連結成分の数に一致する.

* $D$ の弱連結成分には少なくとも1つのサイクルを持つこと: 弱連結成分 $U$ を固定する. $U$ の元1つを選び, それを $x$ とする. すると, 列 $(f^k(x))_{k=0}^\infty$ について, 鳩ノ巣原理から, $f^n(x)=f^m(x)$ となる $n<m$ が存在する. ここで, 列の作り方から, この列はある番号以降からは $m-n$ を周期とする列になることがわかり, サイクルが存在することがわかる.

* $D$ には2つ以上のサイクルを持たないこと: 2つ以上のサイクルを持つとする. このサイクルに交わりがあるとすると, ある頂点の出次数が2になり矛盾するので, サイクルは交わらない. ここで, 各弱成分の頂点の数と辺の数は一致するので, サイクルは1つである.

このことから, Union-Find を利用して, ならし計算量 $O(N \alpha (N))$ で計算できる.

##<font color=#C0C000> C問題 (600pts, diff: 2056) </font> [Sequence Scores](https://atcoder.jp/contests/arc114/tasks/arc114_c)
(正解でき次第更新)

##<font color=#FF8000> D問題 (600pts, diff: 2723) </font> [Moving Pieces on Line](https://atcoder.jp/contests/arc114/tasks/arc114_d)
(正解でき次第更新)

##<font color=#FF8000> E問題 (700pts, diff: 2514) </font> [Paper Cutting 2](https://atcoder.jp/contests/arc114/tasks/arc114_e)
(正解でき次第更新)

##<font color=#B87333> F問題 (900pts, diff: 3545) </font> [Permutation Division](https://atcoder.jp/contests/arc114/tasks/arc114_f)
(正解でき次第更新)

#感想

##総評

##反省点
<font color=#804000>A問題</font> の思考ミス(最初は各整数の素因数の最小値の最小公倍数と考えていた (カウンターケース: $3,6$ ))