AtCoder Regular Contest 079
Updated:
Source codes
Solutions
C - Cat Snuke and a Voyage
最初と最後から 1 回だけ伝播する。
D - Decrease (Contestant ver.)
とても難しかった。解説を読んだ。
$N = 50$ とする。 $a_i = i + (K/N)$ とする(ここで割り算は計算機の割り算)。 残りは大きいものに $1$ ずつ足す。
ポイント
これは本番では解けなかったと思う。
E - Decrease (Judge ver.)
最大の山から選ぶ必要はない。 $N$ 以上の山から好きなだけ減算処理して構わない。 全部の山について限界まで減算し、足し算する分は後からまとめて足す。
ポイント
ルールのよみかえ。同値で簡単なルールにする。
F - Namori Grundy
まずグラフの形を考察する。 $N$ 頂点 $N-1$ 辺は、木である。このグラフはそれに $1$ 本付け加えているのだから、 ループが 1 つできていることになる。このループを起点にして考える。 辺の張り方 $(p_i, i)$ から、どの頂点も入次数は 1 である。 したがって、ループ部分は一方通行である(つまり方向がぶつかったりしていない)。さらに残りの辺は、このループの頂点から外方向に木構造で逃げていることになる。
ここで、木構造の部分から考察する。大事なのは、子が全て決まれば、その頂点の数字は一意に定まるということである。具体的には、以下が成立する。
\[ a_i = \min \{ n \in \mathbb{N} \mid (\forall e = (i, j) \in E)(a_j \neq n) \} \]
だから、ループに付随する木構造の部分は完全に決定されるのでまずこれを計算しておく。 残るは、ループ $L$ の部分である。ループの各頂点は、1つの未知の頂点を子の抱えている他は、子は全て決定されている。だから次の $2$ パターンしかない。
- 「一番小さい」パターン。つまり、以下の通り。
\[ X_i = \min \{ n \in \mathbb{N} \mid (\forall e = (i, j) \in E)(j \in L \lor a_j \neq n) \} \]
- 「二番目に小さい」パターン。つまり、以下の通り。
\[ Y_i = \min \{ n > X_i \mid (\forall e = (i, j) \in E)(j \in L \lor a_j \neq n) \} \]
これを各頂点ごとに試す必要はない。ループ内に含まれるある頂点 $l \in L$ に対し、この 2 通りを試せば良い。$a_l$ が仮決定されると、ループ部分の頂点の数字も一意的に定まるからである。この状態で、 $a_l$ の仮数字だけ消して、また $a_l$ を計算し直す。仮数字とこれが一致していたら、ほころびがないグラフが完成したことになる。
ポイント
自分で全部考察して自分で解答がかけた。とても良かった。 冷静にグラフの形を考察できたのがまず良かった。
Others
C - sample: 4, tle: 2.000, time: 03:06, from_submit: 136:14
D - sample: 5, tle: 2.000, time: 35:31, from_submit: 100:43
E - sample: 5, tle: 2.000, time: 19:15, from_submit: 81:28
F - sample: 4, tle: 2.000, time: 81:28, from_submit: 00:00
D と E は答えを見たので参考程度。