DDCC 2017 本選
作成日：2017.11.09
カテゴリー：競プロ 参戦記録
目次
コンテスト前の計画
配点は$300-500-800-1100-1300$である。
$D$までの4問は解かないと5位以内に入るのは無理そうなので、前の3問は確実にとりたい。
コンテスト中
まず$C$問題を見た。
5分くらい考えて解けそうになかったので、$B$,$A$の順に問題を見て解いた。
さすがにこれらはすぐ解けた。[B 10:07 AC][A 17:23 AC]
$C$問題に戻って考察し始めたが、なかなか解けそうにないので$D$問題も見て交互に考察した。
$60$分経った時点で順位表を見ると、$D$も$E$も誰も解いていなかった。
そこで$D$か$E$のどちらかを解く作戦に決めた。
$E$問題を見て解けそうに見えなかったので、$D$問題に取り掛かる。
しかし最後まで解けず、ほぼ全探索のコードをダメ元で提出して時間切れ。[D 115:58 WA]
コンテスト後(結果)
2完800点の60位。
最終順位を見ると、途中からとった作戦は正しかったようだ。
ただ解けなかったら意味がない。考察の方法が悪いのだろうか。復習あるのみ。
各問題の(軽い)解説
A : 正方形のチップ２
問題文
実際に切断した時にできる正方形は高々$(300/K)^2$個なので、各正方形がウェーハの内部にあるかを調べれば良い。
それは正方形の四隅を調べれば十分である。
B : GCDロボット
問題文
求める整数は$gcd(Z,a_i)$($g_i$とする)の倍数でなければならない。
これは$g_i$の倍数でない数$x$においては必ず$gcd(x,a_i)$$\neq g_i$であることから分かる。
ここで$g_i$の最小公倍数$L$を考えると、$gcd(L,a_i)$は$g_i$の倍数である。
一方$L$が$Z$の約数であることから、$gcd(L,a_i)$は$g_i$を超えないことが分かる。
以上より答えは$L$であることが分かる。
C : グラフいじり
問題文
まず辺の長さを変えない時にどのサイクルを選んでも長さが$0$(条件$A$とする)であるかを考える。
$a$から$b$への行き方が複数あるとすると、そのすべてにおいて長さは等しくなければならない(条件$B$とする)。
そこですべての頂点対間の長さが一意に定めるために、グラフの全域木のうちの1つを考える。
もしこの全域木に含まれていない辺が$B$と矛盾するならば、条件$A$は満たさない。
逆にすべての辺が$B$と矛盾しないならば、条件$A$も満たされる。
これらはグラフが強連結であることから分かる。
以上より$A$を満たすかの判定は$O(N+M)$でできる。
次に辺の長さを変えることを考えるが、この操作は長さを変える辺がないものとみなすことと変わらない。
全ての辺について確かめるのは間に合わない。
しかし、前半の考察において$B$と矛盾する辺が1つだけならば、その辺を除けば$A$を満たすことが分かる。
よって、確かめるのは初めに考えた全域木に含まれる辺だけで良い。
以上より判定は$O(N(N+M))$ででき、これは十分高速である。
D : なめらかな木
問題文
整数を順番に書き込むことを考えると、$i$を書き込むときには$i-1$か$i-2$が書き込まれた頂点とまだ整数が書き込まれていない頂点の集合が分かっていれば良い。
しかし、整数が書き込まれていない頂点の集合$S$が取る状態は多すぎるので減らすことを考える。
$S$の要素である頂点$v$の隣の頂点について考えると、$i-3$以下の整数が書き込まれていない必要がある。
すなわち、$i-1$か$i-2$が書かれた頂点で区切ってみた時に連結である各部分では、すべての頂点が$S$に含まれているかそうでないかのいずれかである。
また$i$が書き込まれた頂点の隣の頂点に書き込める整数は高々$4$個であるから、ある頂点の次数が$5$以上である木における答えは常に$0$である。
この場合を除けば、$i-1$か$i-2$が書かれた頂点で区切った時にできる連結成分は$7$個以下である。
よって$S$のうち考慮すべきものは高々$2^7$個であるから、状態数が高々$2^7 N^2$のDPに落とし込むことができる。
遷移も高々$N$個なので、十分高速である。
E : 足のばし
問題文
木の直径についてなので、中心を考える。
中心を固定した時の直径の最小値$r$は、中心から葉の距離の最大値の2倍である。
また直径が$r$となるのは、中心が頂点の場合はイタズラの回数が$r/2 \times$(葉の個数)$-$(葉と中心の距離の総和)以下の時であり、中心が辺の場合は$(r-1)/2 \times$(葉の個数)$-$(葉と辺がつなぐ頂点のうち近い方の距離の総和)以下である。
操作を適切に行えば、イタズラを葉の個数だけ加えて行うごとに直径が$2$増える。
以上より直径ごとに許容されるイタズラの最大値が求められるが、直径が$2N$を超えるとその値の増加が規則的になる。
この値は全方位木DPで$O(N)$に求まり、単調増加である。
よって、この問題は$O(N+Q)$で解くことができる。
関連
(新しい記事)＞
＜(古い記事) CODE FESTIVAL 2017 qual C