DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦
Updated:
私はオンサイトにいけませんでした。問題集としてやりました。
Source codes
Solutions
A - 正方形のチップ２
割り切れるので、四隅が入っているかどうかを判定する。
B - GCDロボット
「$Z$ と $a_i$ の最大公約数」の最小公倍数。
C - グラフいじり
私は知らなかったのだが、 「有向グラフの全てのサイクルに対し…」という問題に対しては、 DFS 木を作ってから考察するのが定石 らしい。
有向グラフだと考察しづらいので、辺 $(u, v, c)$ があったら 逆辺 $(v, u, -c)$ を追加することにする。これを 拡張グラフ と呼ぶことにする。
まずこのグラフが条件を充しているか確認する。根を $0$ として、 頂点 $v$ の深さ(高さ)を $h(v)$ とする。 任意の辺 $(u, v, c)$ に対し、この辺と DFS 木の辺からなるサイクルの和が $0$ であるための条件は、 $h(u) + c = h(v)$ である。これが成り立っていなかったらその時点で条件不成立である。よって成立しているものとしよう。任意のサイクルは、以上のサイクルの和として書ける。またこのとき、そのサイクルの和は $0$ である。以上により、「全てのサイクルの和が $0$」は「任意の辺 $(u, v, c)$ に対し、$h(u) + c = h(v)$」と言い換えられた。
さて問題は、辺の長さを変えるフェーズである。まず変えるべき辺の候補がわかったとする。この辺 $(u, v, c)$ とその逆辺 $(v, u, -c)$ を除いても、 除いた拡張グラフ は強連結である。ここは非自明なので証明：もとのグラフの強連結性より、 $v$ から $u$ へ至る道は、除いた拡張グラフにもあるはずである(この道では $(u, v, c)$ は使わないため、使ったら定義矛盾)。ここで使った道の逆道を行くと、 $u$ から $v$ への(直接辺を用いない)道ができる。あとは元のグラフが強連結であるから、除いた拡張グラフの強連結性が従う。このグラフでさっき言った判定法を行う。ダメならどうしようもない。変えるべき辺を間違えているかそもそもできない。しかし、問題ないとなったら、$c’ = h(v) - h(u)$ として $(u, v, c’)$ を追加しても問題ない。 $c \mapsto c’$ が長さを変える動作に相当する。
長さを変える候補はどのように決めれば良いだろうか。最初の「グラフが条件を充しているだろうか」の部分で、アウトになった辺 $(u, v, c)$ が見つかったとする。これと DFS 木の辺からなるサイクル上の辺が、候補である(それを修正しないとこのサイクルの和が 0 にならない)。このサイクルを真面目に考察しようとすると最小共通祖先を見つけてくる必要があり手前である。 候補なんだから少しはみ出ていいじゃないか。 $u, v$ から $0$ に至るまで全部と、辺 $(u, v, c)$ でいいではないか。
以上の計算量は、 $O(M + NM) = O(NM) = O(N^3)$ である。 $N = 300$ なら高速に処理すれば間に合う。
ポイント
逆辺追加しか思いつかなかった。これだとポイントを 3 つ逃しているので、解答までたどり着くのは絶望的だろう。まぁ勉強になったと言うことにしよう。
D - なめらかな木
数字に対して DP をしよう。 DP(今まで印をつけた bit, 2 つ前に数字を書いた頂点, 1 つ前に数字を書いた頂点) = それを充す場合の数 とする。この DP は map か hash で持つ。
元の木 $T$ の頂点のうち、次数が $5$ 以上のものがあったとする。この時点で場合の数は $0$ である。以下では全ての頂点の次数は $4$ 以下であるとしてよろしい。
ある頂点 $u$ に $i$ 、 $v$ に $i-1$ という数字を書くことにする。 この時、元の木 $T$ から $u, v$ を引いた森の連結成分は最大で $7$ つである。 この連結成分は、それぞれ、「全て数字を書かれた状態である」または「まだ何も書かれていない」のいずれかである。 なぜか？ 「数字を書かれた頂点と書かれていない頂点が両方存在する連結成分(部分木)」があるとする。書かれた数字は全て $i-2$ 以下であり、これから書く数字は全て $i+1$ 以上である。これは条件に反する。ゆえに結論が従う。
よって以下の順序で処理をすればよろしい。
- $N=1, 2$ の場合は、それぞれ答えは $1, 2$ である。以下 $N \geq 3$ として良い。
- 元の木 $T$ の頂点のうち、次数が $5$ 以上のものがあるならば、答えは $0$ である。
- $0 \leq i, j < N$、 $i \neq j$ を充す $(i, j)$ に対し、 $T \setminus \{ i, j \}$ の連結成分を bit で vector に入れておく。
- $\sum_{1 \leq i, j < N, i \neq j} \mathrm{value}(11 \dots 11, i, j)$ を計算する。ここで関数 $\mathrm{value}$ は以下メモ化を用いて定義する。
value(bit, a, b) の処理は以下の通り。
- $a, b$ を除いた連結成分が「全て数字を書かれた状態である」または「まだ何も書かれていない」であるかを判定する。
&と反転で高速にできる。ダメなら0を返す。 bitの立っている数が $2$ ならば、1を返す。ここで降下が止まる。答えが書いてあったらそれを返す。bitから $b$ 番目を折る。これをbit2とする。- $a$ 番目以外の立っている
bit2に対して($i$ 番目)、value(bit2, i, a)を計算する。和をとる。
先ほども書いたが、 DP は配列ではなく map か hash で持つ。
ポイント
綺麗な DP だった。