日立コン2020C 解法の正当性
日立製作所 社会システム事業部 プログラミングコンテスト2020 C問題
正当性を確認せずACしたので、証明を考えてみる。
問題概要
$N$頂点の木が与えられる。$1$から$N$までの整数の順列$p$であって、以下の条件を満たすものが存在するか判定し、存在するなら一つ見つけよ。
全ての頂点の組$(i,j)$について$\mathrm{dist}(i,j) = 3$なら$p_i,p_j$の和または積が$3$の倍数になる。
解法
適当に根を取り根付き木として扱う。$\mathrm{cnt}_p(i) $を木の頂点であって、その深さが$p$を法として$i$と合同になるようなものの個数とする。 順列の値としては$3$で割ったときの余りのみが重要であるため、各頂点に$N_0 = \left\lfloor \frac{n}{3} \right\rfloor$個の$0$、$N_1 = \left\lfloor \frac{n+2}{3} \right\rfloor$個の$1$、$N_2 = \left\lfloor \frac{n+1}{3} \right\rfloor$個の$2$を割り当てる問題に帰着できる。 解として正しいケースとして以下の場合がある。
- 深さが偶数(または奇数)である頂点全てが$0$である場合。
$\because$ 距離が$3$離れた2頂点は深さの偶奇が異なる。したがって深さが偶数または奇数の頂点を全て$0$にできれば全ての該当する2頂点の積が$3$の倍数となる。 - 任意の頂点$i$について$p_i$が$0$または$w_{\mathrm{depth}(i) - s \bmod 6}$である場合。ただし列$w = (1,2,1,0,1,2)$であり、$s$は$0$以上$6$未満の整数。
$\because$ 距離が$3$離れる2頂点は、深さの差が$1$または$3$となる。$w_i$と$w_{i+1 \bmod 6}$、$w_i$と$w_{i+3 \bmod 6}$は和または積が$3$の倍数となる。また$p_i$が$0$である場合、積が$0$となる。したがってこの場合条件を満たす。
上記のケースを作れる条件は
深さが偶数（または奇数）の頂点を全て$0$にできること。つまり$\min(\mathrm{cnt}_2(0),\mathrm{cnt}_2(1))\le N_0$
$s$を決めると各頂点は
$0$にする/$0$または$1$にする/$0$または$2$にする
の$3$つのグループに分けられる。$2$つ目のグループが$N_1$個以上、$3$つ目のグループが$N_2$個以上あることが条件。すなわち以下の条件を満たす$s$が存在することが条件。
このような条件を満たす入力については解けた。これを実装するとACする。
解法の正当性の確認
次が確認できれば十分である。
$(\bigstar)$ 長さが$6$,総和が$N$となる任意の非負整数列$\mathrm{cnt}_6$に対して、上記の$2$つの条件の少なくとも一方は満たされる。
新たに
\[\begin{align*} X = \mathrm{cnt}_2(0) &= \mathrm{cnt}_6(0)+\mathrm{cnt}_6(2)+\mathrm{cnt}_6(4), \\ Y = \mathrm{cnt}_2(1) &= \mathrm{cnt}_6(1)+\mathrm{cnt}_6(3)+\mathrm{cnt}_6(5) \end{align*}\]を定義する。
背理法で示す。すなわち長さ$6$,総和$N$の非負整数列$\mathrm{cnt}_6$であって、上記の$2$条件をともに満たさないものが存在すると仮定する。$1$つ目の条件を破るから
\[X > N_0 \land Y > N_0\]である。$N_1\le N_0+1$に注意すると
\[X \ge N_1 \land Y \ge N_1\]が得られる。$s=0$について$2$つ目の条件を破るから
\[X < N_1 \lor \mathrm{cnt}_6(1)+\mathrm{cnt}_6(5) < N_2\]が成立する。 前者は偽なので
\[\mathrm{cnt}_6(1)+\mathrm{cnt}_6(5) \le N_2 -1\]である。$s=2,4$についても同様の不等式を立てると$3$つの不等式から
\[2Y \le 3(N_2 - 1)\]が得られる。$s=1,3,5$についても同様に
\[2X \le 3(N_2 - 1),\]である。したがって
\[X+Y \le 3(N_2-1)\]となる。 $X+Y = N$であるから
\[N \le 3(N_2-1)\]である。しかし、$N_2 = \lfloor (N+1)/3 \rfloor$より$3N_2 \le N +1$であるから $ N \le 3N_2 -3 \le N-2 $ となり矛盾。したがって$(\bigstar)$は示された。
結構めんどくさかった。解説を読むと似たような発想で、もっとわかりやすい方法が書いてある。最初に深さをmod3で分類することを考えてしまったが、mod2で考えればもっと簡単だった。でも、怪しげな解法をチェックする能力がARCやAGCで必要な気がするからこの記事はその練習ということで