AtCoder Regular Contest 111 感想

##総合結果
* [Score] 1300 pts
* [Time] 77:50+<font color="red"> 05:00 $\times$ 0 </font> = 77:50
* [Ranking] 393 rd [Rated内: 368 th]
* [Performance] <font color=#0000FF> 1947 </font>
* [Rating] <font color=#0000FF> 1759 </font> → <font color="blue"> 1779 </font> (+20)

##各問題ごとの詳細
* <font color=#008000> A問題 </font> 19:51
* <font color=#00C0C0> B問題 </font> 39:03
* <font color=#0000FF> C問題 </font> 77:50
* <font color=#C0C000> D問題 </font> --:-- 
* <font color=#FF8000> E問題 </font> --:--
* <font color=#FF0000> F問題 </font> --:--

##提出コード
* <font color=#008000> A問題 </font> [■](https://atcoder.jp/contests/arc111/submissions/19282050)
* <font color=#00C0C0> B問題 </font> [■](https://atcoder.jp/contests/arc111/submissions/19284036)
* <font color=#0000FF> C問題 </font> [■](https://atcoder.jp/contests/arc111/submissions/19288182)

#問題ごとの略解
##<font color=#008000> A問題 (300pts, diff:1146) </font> [Simple Math 2](https://atcoder.jp/contests/arc111/tasks/arc111_a)
$10^N$ を $M$ で割った商を $q$, 余りを $r$ とすると, 
$$10^N=qM+r,\quad \left \lfloor \dfrac{10^N}{M} \right \rfloor=q,\quad 0 \leq r <M$$
が成り立つ. 次に, $q$ を $M$ で割った商を $a$, 余りを $b$ とすると,
$$q=aM+b,\quad 0 \leq b <M$$
が成り立つ. 今の式を上の式に代入して, 整理すると,
$$10^N=aM^2+bM+r,\quad 0 \leq b,r <M$$
である. ここで, 上の等式に対して, $M^2$ における剰余環 $\mathbb{Z}/(M^2 \mathbb{Z})$ を考えると,
$$\left[10^N \right]\_{M^2}=\left[ aM^2+bM+r \right]\_{M^2}=[bM]\_{M^2}+[r]\_{M^2} $$
となる. ここで, $b=0,1,\dots,M-1$ と固定することによって, $r$ の値が定まるが, $b$ が $1$ 増えるごとに $r$ は $M$ 減り, 剰余環は $M^2$ の周期である. 以上のことから, $0 \leq r <M$ なる $b$ がただ一つ存在して, この $b$ が答えである.

以上の手続きを $O(M+\log N)$ で求めることができた.

###さらなる解法
ここまででも正解はできるが, さらに考察をすすめることによって, 計算量を $O(\log N)$ に削減することができる.

$\left[10^N \right]\_{M^2}=\left[ bM+r \right]\_{M^2}$ であったが, $0 \leq b,r <M$ なので, $0 \leq bM+r <M^2$ となる. よって, $10^N ({\rm mod}~M^2)=bM+r$ である. よって,
$$b=\left \lfloor \dfrac{10^N ({\rm mod}~M^2)}{M} \right \rfloor $$
である.

###補足
$$10^N=aM^2+bM+r,\quad 0 \leq b,r <M$$
という等式から, この問題は $10^N$ を $M$ -進表記した際, 下から $2$ 桁目の数字はなにか? という問題に帰着できる.

##<font color=#00C0C0> B問題 (400pts, diff:1334) </font> [Reversible Cards](https://atcoder.jp/contests/arc111/tasks/arc111_b)
頂点集合を $V:=\\{1,2,\dots,4 \times 10^5\\}$, 辺集合を $E:=\\{a_i b_i,\dots, a_N b_N\\}$ とするグラフ $G=(V,E)$ を考える. このとき, $K$ 個の各連結成分 $C_1, \dots, C_K$ に対して答えを求めていく. なお, 連結成分 $C_i$ の頂点の個数を $X_i$ とする.

+ $C_i$ が木になるとき[^2]
答えは $X_i-1$ である. $C_i$ をある頂点 ${\rm root}\_i$ を根とする根付き木を考えたとき, 各辺を担うカードについて ,子になる方の色を表にすることによって, $X_i-1$ 種類の色を表にすることができる. そして, $C_i$ は木なので, 辺の数は $X_i-1$ であり, これ以上増やすことはできない.

+ $C_i$ が木にならないとき
答えは $X_i$ である. 適当な全域木を選び, 選ばれなかった辺から1つの辺 $e_i$ を選び, その端点のうちの1つを $v_i$ とする. このとき, 全域木を $v_i$ を根とする根付き木を考えたとき, 上で述べた方法で $v_i$ 以外の色を表にすることができ, 辺 $e_i$ を成すカードについて色 $v_i$ の面を表にすることによって, $C_i$ の各頂点の色を表にすることができる.

よって, 正解は木になっている連結成分の個数を $M$ としたとき $N-M$ である. ここで, $N$ 頂点の グラフ $H$ について,
$$ H:{\rm Tree} \iff H は連結で辺の数が N-1 である$$
であることに注意して, データ付きUnion-Find を利用することによって, $X:=4 \times 10^5$ として, ならし計算量 $O(N\alpha(X))$[^1] で求めることができる.

[^1]: $\alpha(k)$ はアッカーマン関数を $A(\cdot,\cdot)$ とし, $F(x):=A(x,x)$ としたとき, $\alpha:=F^{-1}$ である. 
[^2]: 1頂点, 0辺からなるグラフも木とみなす. これは, 色 $v$ が塗られているカードが存在しないことを表す.

##<font color=#0000FF> C問題 (600pts, diff:1750) </font> [Too Heavy](https://atcoder.jp/contests/arc111/tasks/arc111_c)

まず, 初期状態において, $a_i \leq b_{p_i}$ かつ, $i \neq p_i$ なる $i$ が存在した場合, 自分の荷物でないのに疲れてしまい交換不能な人がいるので, この瞬間に不可能が確定する.
また, 以下では任意の $i$ で $p_i \neq i$ と仮定する(つまり, 全員が自分の荷物ではないが疲れていない).

このとき, 人 $i$ と人 $j$ が交換したとき, $a_i \leq a_j$ ならば, 交換後も $a_j$ は疲れない. 実際, 人 $i, j$ が交換前に持っていた荷物の重さ $b_i, b_j$ について, 疲れていないので $b_i \leq a_i$ が成立し, 仮定から $a_i \leq a_j$ だったので, 合わせて $b_i \leq a_j$ となるので, 人 $j$ は疲れないことが示せた.

以下, 必要ならば添字を入れ替えて $a_1 \leq \dots \leq a_N$ としてもよい.
まず, $a_1$ について, 人 $1$ と $p_{i_1}=1$ なる 人 $i_1$ の荷物を交換することによって,　人 $1$ は荷物 $1$ を持つことができ, 人 $i_1$ は疲れていない状態にすることができた ( $p_1, p_{i_1}$ の値を交換しておく).
次に, $a_2$ について, $p_2 \neq 2$ であるとき, 人 $2$ と $p_{i_2}=2$ なる 人 $i_2$ の荷物を交換することによって,　人 $2$ は荷物 $2$ を持つことができ, 人 $i_2$ は疲れていない状態にすることができた ( $p_2, p_{i_2}$ の値を交換しておく).
$^\vdots$

これを繰り返すことにより, 全ての人が同じ番号の荷物を持つことができる. なお, 最小性については[公式解説](https://atcoder.jp/contests/arc111/editorial/520)参照.

この解き方における計算量はソートがボトルネックになり, $O(N \log N)$ である.

##<font color=#C0C000> D問題 (600pts, diff:2046) </font> [Orientation](https://atcoder.jp/contests/arc111/tasks/arc111_d)
(正解でき次第更新予定)

##<font color=#FF8000> E問題 (800pts, diff:2541) </font> [Simple Math 3](https://atcoder.jp/contests/arc111/tasks/arc111_e)
(未着手)

##<font color=#FF0000> F問題 (900pts, diff:3119) </font> [Do you like query problems?](https://atcoder.jp/contests/arc111/tasks/arc111_f)
(未着手)

#感想
##良かった点

* 難しいとされた <font color=#008000> A問題 </font>を解くことができた.
* <font color=#00C0C0> B問題 </font> をグラフの問題に帰着できた.
* 600 pts 問題を1つ正解(<font color=#0000FF> C問題 </font>)できた.

##反省点

* 全体的にもう少しスピードアップしたかった.

#お詫びと訂正
この記事をアップロードした時, タイトルが「AtCoder Beginner Contest 187 感想」になっていました. すぐに気づき, 訂正しようとしましたが, モデムの不具合により訂正ができない状況になっていました. 読者の方に混乱を招いてしまったことをお詫び申し上げます.