総合結果

[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問題 ■
B問題 ■
C問題 ■

問題ごとの略解

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$ が木になるとき¹
答えは $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))$² で求めることができる.

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?