ちょっとずつ変なケアレスミスでバグらせてる時間が勿体ないねえ。
春は眠い季節だからミスも多くなるの。1)
各ビルの最終的な高さを $B$ とすると、最終的な景観としてあり得ないのは、
このような $i,j$ があったらダメ。
ビルは並び順は関係ないので、昇順にソートしておき、$i$ も振りなおす。
以下のDPを考える。
すると、たとえば $A=(1,2,5,5,7)$ において、
Ai=1 j 7 1 6 4 5 1 1 8 4 3 3 11 3 ┌ 4 4 11 2 1 ├ 4 4 ┌ 8 1 1 ┌ 2 ├ 3 3 ├ 4 0 1 1 ┴ 1 ┴ 1 ─ 1 ┴ 1 ------------------------------ i (0) 1 2 3 4 5 Ai 1 2 5 5 7
このようになる。
$A_{i+1}$ と $A_i$ の差がたとえば $3$ だったとして、$DP[i][j]$ は、$DP[i+1][j]~DP[i+1][j+3]$ の4箇所にそれぞれ1倍で遷移する。 この範囲に遷移する限り、最終的な景観があり得る状態に保たれる。
さて、このDPを愚直に計算すると $O(N A_{max})$ だが、どの遷移も「$A_{i+1}-A_i+1$ 箇所に1倍で遷移する」というのが変わらない。
つまり、最終的に必要なのは総和なので、最初から総和で管理して問題ない。
答えは、$(A_1+1) \times (A_2-A_1+1) \times (A_3-A_2+1) \times ...$ となる。
取り得る値が3つの列をいろいろ操作する問題は、「操作しても変わらない不変量」を見つけるのが解法であることが多い。
今回の場合、足したり引いたりXORしたりして試すと、
という法則が見つかる。それをもって下から計算すると、
c1+4c2+6c3+4c4+c5 -c1-3c2-3c3-c4 -c2-3c2-3c4-c5 c1+2c2+c3 c2+2c3+c4 c3+2c4+c5 -c1-c2 -c2-c3 -c3-c4 -c4-c5 c1 c2 c3 c4 c5
このように、一番下の段の値に二項係数をそれぞれかけたものが一番上の段の値となる。
この問題はそこからもう一段階ある。
二項係数は $N=4 \times 10^5$ にもなると値が非常に大きくなってやってらんないので、適当にmodをとる必要があるが、 そのときの法は「計算過程で出てくる値のどれとも互いに素な数」で無いと適切に計算できない。
例えば $\mod{1000000007}$ が $4$ になったとしても、可能性のある値は $4,1000000011,2000000018,...$ となり、 それぞれの $\mod{3}$ は $1,0,2,...$ なのでどれなのか結局わかんない。
調べると、任意modでの二項係数という記事が出てくる。
これによると、素因数分解した形で管理するといいらしい。
今回は $3$ という非常に単純な値なので、「3で割ったときに 0,1,2 となる素因数をそれぞれいくつ持つか」で管理してみる。
0 1 2 1 0 0 0 2 0 0 2 6 1 0 1 (2*3) 7 0 1 0 (7) 10 0 0 2 (2*5)
(公式解説によると、実際は「3で何回割れるか」と「その後に残る値の $\mod{3}$」の2つで管理できるらしい)
そして、二項係数 ${}_NC_r$ を順番に求める場合、以下のようにすると順次計算できる。
(例) i 0 1 2 3 ... --------------------------------- 10 9 8 10_C_i 1 x -- x - x - 1 2 3
今回は、これに従って素因数分解結果(mod3)を、かけ算なら足し合わせ、割り算なら引けば、二項係数 $\mod{3}$ を表現できる。
3つの値をそれぞれ $d_0,d_1,d_2$ としたとき、その値の $\mod{3}$ は、
これに従って、最下段の並びに、二項係数mod3をかけて足し合わせたものが、最上段の色を示す値となる。
ただし、最下段の長さが偶数の場合、正負逆転した値となることに注意。
より汎用的な 素数modの二項係数の求め方としては、Lucasの定理というのがある。
mod3の不変量を求める方針は一緒。
二項係数 ${}_nC_r$ のmod3を計算していくと、$n=3,9,27,...$ といった3のべき乗で、
'1 0 0 0 … 0 1
' のように ${}_nC_0={}_nC_n=1$ を除いて全て間が0となることを利用する。
つまり、
なので、$3^k$ 段上の状態を、一足飛びに計算してしまえる。
この操作は、最下段の長さを $N$ として $O(\log_3{N})$ 回程度ですみ、1回の操作もどんどん短くなるので、全体で $O(N)$ 程度で計算できる。
実装も短い。
一直線の木なら簡単で、1から順に埋めていくだけ。
①--②--③--④--⑤
二股に分かれていても、基本、一直線に取れる部分はこの法則より小さくできない。
①--②--③--④--⑤ └--○--○
で、残る部分が別の一直線に含まれるように変形させると、
↓~~~~~~~~⑤とのペアを考えると、5との差が3以上必要 ⑤--④--③--○--○ ←⑤とのペアを考えると、5との差が4以上必要 └--②--①
そのため、以下のようになる。5との差が3以上必要といっても、減らしてしまうと今度は②などとの整合が取れなくなるので、増やす方となる。
⑤--④--③--⑧--⑨ └--②--①
これは、DFSの訪問順で表現できる。
つまり、根を決めて、$k=1$ から、隣接する頂点に移動するたびに(訪問済みであろうと)$k$ を1ずつ増やしてDFSすると、各頂点の値は「その頂点に初めて訪れられたときの $k$ の値」とすればよい。
①--②--③--④--❺ k=5まで └--○--○ ①--②--③--❹--⑤ k=6 └--○--○ ①--②--❸--④--⑤ k=7 └--○--○ ①--②--③--④--⑤ k=8 └--❽--○ ①--②--③--④--⑤ k=9 └--⑧--❾
さて、ではその中で「最大値を最小化」するためにはどんな条件が必要か。
どの頂点を根に選ぼうが「根からDFSで全頂点を訪れ根に戻ってくる時の $k$ の値」(オイラーツアーの長さ)は変わらない。
根が中途半端な位置だった場合、根を①とするより、一番最初にたどり着いた葉を①とした方がいいのは明らかで、「根から、最初にたどり着いた葉までの $k$ の増分」は省略できる。
また、実際に頂点の値として使われるのは最後にたどり着いた葉なので、「最後にたどり着いた葉から、根に戻るまでの $k$ の増分」も省略できる。
これが最大になるように、最初と最後にたどり着く葉を選べばよい。
つまり、木の直径となる。