##総合結果
- [Score] 1300 pts
- [Time] 77:50+ 05:00 $\times$ 0 = 77:50
- [Ranking] 393 rd [Rated内: 368 th]
- [Performance] 1947
- [Rating] 1759 → 1779 (+20)
##各問題ごとの詳細
- A問題 19:51
- B問題 39:03
- C問題 77:50
- D問題 --:--
- E問題 --:--
- F問題 --:--
##提出コード
#問題ごとの略解
## A問題 (300pts, diff:1146) Simple Math 2
$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$ 桁目の数字はなにか? という問題に帰着できる.
## B問題 (400pts, diff:1334) Reversible Cards
頂点集合を $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$ が木になるとき1
答えは $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))$2 で求めることができる.
## C問題 (600pts, diff:1750) Too Heavy
まず, 初期状態において, $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$
これを繰り返すことにより, 全ての人が同じ番号の荷物を持つことができる. なお, 最小性については公式解説参照.
この解き方における計算量はソートがボトルネックになり, $O(N \log N)$ である.
## D問題 (600pts, diff:2046) Orientation
(正解でき次第更新予定)
## E問題 (800pts, diff:2541) Simple Math 3
(未着手)
## F問題 (900pts, diff:3119) Do you like query problems?
(未着手)
#感想
##良かった点
- 難しいとされた A問題 を解くことができた.
- B問題 をグラフの問題に帰着できた.
- 600 pts 問題を1つ正解( C問題 )できた.
##反省点
- 全体的にもう少しスピードアップしたかった.
#お詫びと訂正
この記事をアップロードした時, タイトルが「AtCoder Beginner Contest 187 感想」になっていました. すぐに気づき, 訂正しようとしましたが, モデムの不具合により訂正ができない状況になっていました. 読者の方に混乱を招いてしまったことをお詫び申し上げます.