AtCoder Regular Contest 130 C,D問題メモ
変なとこでハマるのはなかなかなおらないけど、なんとか大怪我はせずに済んだ。
C - Digit Sum Minimization
問題
- どの桁も0でない2つの正整数 $a,b$ がある
- 各桁の数字を自由に並べ替えていいとき、$a+b$ の各桁の和が最小になる $a,b$ の例を1つ出力せよ
- $1 \le a,b \lt 10^{100000}$
解法
嘘で通してしまったっぽい。
繰り上がりが発生しなければ、$a+b$ の各桁の和は元の $a,b$ の各桁の和のまま変化しない。
繰り上がりが発生すると、一の位が10減って十の位が1増えるので、差し引き9減る。
なので、繰り上がり回数を最大化すればよい。
a 5599666777888
b 333222112
-----------------
5600000000000
$a,b$ で同じ桁になる数字をペアと呼ぶことにして、
- 一番右に、足して10以上になるペアが1つ（点火箇所）
- 足して9以上になるペアをなるべくたくさん
- 桁数に差がある場合、9が残っているなら一方が切れた箇所からは9を優先的に
置いていけばよい。
上記のペア数さえ最大化できれば、そのペアをどの順で並べようとよい。
点火箇所を一の位において、9以上のペアをその次から置いていくとしてよい。
では、ペア数最大化のためにはどうマッチングさせれば良いか。
- $a$ の一の位（$a_0$ と表す）を固定して、$1～9$ 全通り試すとよい。
$a_0$ を固定すると、$b_0$ は「$a_0$ と足して10以上になる、なるべく小さな数」を置いてよい。
十の位以降を考えると、$b$ には大きい数字を残した方が絶対に有利。
または、「足して10以上になるペアは作れるんだけど、敢えて作らない方が最適になる」場合は、
$a_0$ を他の値に固定した時に考慮されるので、ここで考える必要は無い。
一の位が決まれば、あとは足して9以上になるペアを最大化すれば良い。
これは「なるべく合計が小さなペア」から取っていくと貪欲で決まるらしいが、
その証明が上手くできない場合は最大流問題で解いてもよい。
USO
$a_0$ を全通り試さず「とりあえず合計が10（とか一番小さいもの）ができたらそれを採用」では嘘解法となる。
a 123
b 678899
足して10になるペアは 1+9, 2+8, 3+7 があるが……
1+9 2+8 3+7
321 132 213
889679 799868 699887
-------- -------- --------
890000 800000 700100
1+9を取ってしまった場合、結果が変わってくる
a 126
b 678
一の位に置くペアとして、一番合計が小さくできるのは 2+8 だが……
2+8 6+6
162 216
768 786
----- -----
930 1002
6+6を選んだ方が、残りで合計9のペアを多く作れる
従って、一の位は $a_0$ を固定した上で全通り試す必要がある。
いや多分、条件をきちんと考えれば、9以上ペアを最大限マッチングさせた後、足して10以上になるペアがあればそれを発火させればいいし、9ちょうどになるペアしか無ければ何らかの優先順位に従って局所的に組みなおすといいとは思うんだけど、その優先順位を漏れなく考慮するくらいなら、全通り試した方がいい、という感じ。
貪欲っぽくはあるが、本当に貪欲でやってよいのか、 貪欲でなく全通り試さなくてはいけないものはなんなのか、見極めと証明が難しい。
D - Zigzag Tree
問題
- $N$ 頂点の木が与えられる
- 各頂点に、順列 $(p_1,p_2,...,p_N)$ を割り当てる方法は $N!$ 通り
- この内、以下の条件を満たすものの個数を $998244353$ で割ったあまりで求めよ
- どの隣接する3頂点 $a,b,c$（$b$ が真ん中）を見ても、$p_a \gt p_b \lt p_c$ または $p_a \lt p_b \gt p_c$
- $2 \le N \le 3000$
解法
根を適当に固定すると、そこからの深さによって「前後より大きい頂点」か「小さい頂点」かが決まる。 （根をどちらにするかで2通りあるので、適当に根を「大きい頂点」と固定して答えを求めて、最後に2倍する）
大 ①
↙ ↘ ①→②: p1 > p2 であることを示す
小 ② ③
↗↖ ↑
大 ④ ⑤ ⑥
↓
小 ⑦
直線グラフの場合
このような問題は、直線グラフであれば類題がある。
頂点に置く値で場合分けしてDPを組むとき、 「具体的に何の数字を置いたか」ではなく、 「暫定決まっている中の何番目に小さい値を置いたか」によって場合分けすると上手くいく。
- $DP[i][j]=i$ 番目の値まで決めて、$i$ 番目の値が $j$ 番目に小さい値であるパターン数
j 1 2 3 4 5 ① [1] 1番目に小さい値を置くのが1パターン（1つしかないので当然） ＾ ② [0 1] ①より大きくないといけない。2番目に小さい値を置くのが1パターン ｖ ③ [1 1 0] 1番小さい値が1パターン、2番目が1パターン ＾ ④ [0 1 2 2] ｖ ⑤ [5 5 4 2 0]
具体的に何の数字を置いたかを持ってしまうと、 被ってはいけないので、それまでに置いた全ての値の情報が無いと以降に置く値を決められない。
値の大小だけを持つことで、直前の値が全体の何番目だったかさえわかれば、次に置く値を決められる。
直線グラフであればこの考え方でよい。
更新は、大小関係 < > によって前からまたは後ろから累積和を取る。
木への応用
さて、今回は木である。
木でも、葉から同様に求めていくことができる。分岐までは。
問題は、2つの子をマージするとき。
DP[1] = [???]
①
DP[2] = ↙↘ DP[3] =
[1 1 0] ② ③ [5 5 4 2 0]
： ：
①の下には $3 + 5 + 1 = 9$ 個（2つの子のDP配列長+自分自身）の頂点がある。
仮に、①に9個中 $4$ 番目に小さい値を置いたとして、そのパターン数はどう計算できるか。
置こうとしている値を $a$、 ②側に置いた値を $b_1 \lt b_2 \lt b_3$、③側に置いた値を $c_1 \lt ... \lt c_5$ とするとして、
1) b1 < b2 < b3 < a となる場合
③側の大小関係を満たせないためダメ
2) b1 < b2 < a < b3 ┬ となる場合
c1 < a < c2 < .. < c5 ┘
・②には2通りの値を置け、その合計は2通り（DP[2] の前2つ）
・③には1通りの値を置け、その合計は5通り（DP[3] の前1つ）
・b1,b2,c1の並び順として、3_C_2 通り
・b3,c2～c5 の並び順として、5_C_1 通り
これらを掛け合わせた150通り
3) b1 < a < b2 < b3 ┬ となる場合
c1 < c2 < a < c3 < .. < c5 ┘
・②には1通りの値を置け、その合計は1通り（DP[2] の前1つ）
・③には2通りの値を置け、その合計は10通り（DP[3] の前2つ）
・b1,c1,c2の並び順として、3_C_1 通り
・b2,b3,c3～c5 の並び順として、5_C_2 通り
これらを掛け合わせた300通り
4) c1 < c2 < c3 < a となる場合
②側の大小関係を満たせないのでダメ
計450通りの状態がある。
このように2つの子のマージは、何番目に大きい値か $k$ を固定して、 和が $i+j=k$ となる $i,j$ ごとに求めることができる。
累積和を前計算することで、 2つの子のDP配列長を $l_1,l_2$ とすると 1回のマージにかかる計算量は $O(l_1 l_2)$ で可能となる。
たたみ込みを使うこともできる。
自身が子より小さい頂点の場合はあらかじめ逆転させておく。
$DP[2],DP[3]$ を前から累積和を取ったものを $DP'[2],DP'[3]$ として、
\begin{eqnarray} DP[1][k] &=& \sum_{i+j=k} DP'[2][i] DP'[3][j] \binom{k}{i} \binom{l_1+l_2-k-2}{l_1-i-1} \\ &=& k!(l_1+l_2-2-k)! \sum_{i+j=k} \frac{DP'[2][i]}{i!(l_1-i-1)!} \frac{DP'[3][j]}{j!(l_2-j-1)!} \end{eqnarray}
と、Σの中を $i,j$ に分離できるので、 $DP'$ の各項にあらかじめ階乗の逆数をかけてからたたみ込むと、DP[1] が求められる。
