競技プログラミング 知識集積所

ARC230 C - Buildings

建物

問題ページ解答例

考え方

まず、なんでもいいから $1$ つ構成せよという問題だったと思って考えてみる。

一番低いビルから順に考えてみる。
そのビルの左右の区画は、その一番低いビルをどちら側に見るかが違うだけで、全く同じビルの組を見る。
ということは、そこの両サイドは $C$ の値は等しいはずである。
その $2$ 区間をマージして $C$ の値を $1$ だけ減らした問題を解ければ、元の問題も解ける。

つまり、概ね、再帰的処理として以下のように考えればよい。

さて、本来の問題を解く上では、以下のようにいくつか問題がある。

$1$ つずつ解決していこう。

まず、$1$ つめの「左右端の値をどのように適切に設定するのか」問題。
これは不変量を用いる考察で解決する。
値 $k$ に対して $2^{-k}$ という評価を対応させる。
評価値合計はマージによって不変であるので、その値は $2^0$ ぴったりでなければならない。

ということで、以下のようにして求められる。
まず、未決定の左右端を除いた範囲で、どの値がいくつあるかカウンティングする。
最大値の個数が奇数であれば、その値が $1$ つ不足していると判断し、$1$ つ追加する。
その後、最大値を $2$ 個 $1$ セットで $1$ つ小さい値に変換する。
最終的に $0$ が $2$ 個以上になってしまった場合は、そもそも不可能。
また、途中追加した数が $0$ 個である、または $3$ 個以上である場合も不可能。
$2$ 個だった場合は、その片方を左端に、片方を右端に設定し、両パターンを調査する。
$1$ 個だった場合は、それより $1$ 大きい値を両サイドともに設定する。
これで解決。

次に、$2$ つめの「同じ値があるところを貪欲にマージして問題ないのか」問題。
これは、最も大きいところを貪欲に選んでよい。
なぜなら、最も大きいところは、どれだけ待っても別の処理方法が選べるようにはならないから。

そして、$3$ つめの「同じ値が $3$ つ以上並んでいる場合はどうするべきなのか」問題。
これは、大きい値から貪欲にという前提であれば、話は簡単になる。
つまり、$2$ 個 $1$ セットにした結果、マージに使われないものが残ったら失敗である。
奇数個並んでいる場合には失敗判定でよい。
偶数個並んでいる場合には、端から順に $2$ 個ずつマージするパターンのみ考えればよい。

この $2$ 個目と $3$ 個目の話をあわせると、少し効率のいい処理ができる。
左から順にstackに積んでいき、「積む前にstackのトップとマージ可能ならマージしてから積む」でよい。
$2$ 連続の $k$ を即合成して困るのは、左右両方から合成で $k$ が奇数個ずつ生まれる場合のみである。
このstack戦略では、それは絶対に発生しない。

最後に $4$ つめの「そもそも $1$ つ構築する問題ではなく、構築パターン数を求める問題である」問題。
これは、stackに、その区間の長さと、その区間だけ埋める割り当てパターン数を合わせて持たせればよい。
長さ $L$ の区間と長さ $R$ の区間をマージするとしよう。
まず、境界にその範囲で一番高いビルを置くとして、残り $L+R-2$ 個の数を左右に振り分ける。
$L+R-2$ 個のうちどの $L-1$ 個を左に使うかは ${}_{L+R-2}\mathrm{C}_{L-1}$ 通り。
その後の、それぞれの範囲内の並べ替え個数は、既に求まっている。
これら $3$ つの数の積が、マージ後の割り当てのパターン数である。

以上で $4$ つの問題は全て解消され、解ける。
計算量は、二項係数の事前準備のもとで、$O(N)$ である。

入力例1での動作

入力を受け取る。

n: 4
c: {2, 2, 3}

まず、左右端を除いた値をカウンティングする。
$2$ が $2$ 個、$3$ が $1$ 個ある。

最大値の $3$ は奇数個なので、不足分として $3$ を $1$ 個追加する。
すると $3$ が $2$ 個になり、これらを合成して $2$ が $1$ 個増えるので、$2$ は $3$ 個になる。

次に $2$ は奇数個なので、不足分として $2$ を $1$ 個追加する。
すると $2$ が $4$ 個になり、これらを合成して $1$ が $2$ 個になる。
さらに $1$ が $2$ 個あるので合成すると、$0$ が $1$ 個になる。

したがって、不足分は $3$ と $2$ の $2$ 個であり、左右端の候補は次の $2$ 通りになる。

3 2 2 3 2
2 2 2 3 3

まず、3 2 2 3 2 を左から stack に積んでいく。
先頭の $3$ と、その後の $2$ は合成できず、最後まで全体を深さ $0$ の $1$ 要素にまとめることができない。
よって、この候補から作れる順列は $0$ 通りである。

次に、2 2 2 3 3 を処理する。
各要素について、[区間長, パターン数] もあわせて持つことにする。

最初の $2$ を積むと、stack は 2[1,1] となる。
次の $2$ は同じ深さなので合成され、1[2,1] となる。
次の $2$ は合成できないので、そのまま積む。
さらに最初の $3$ もそのまま積むので、ここまでで次の状態になる。

1[2,1], 2[1,1], 3[1,1]

最後の $3$ を積もうとすると、まず直前の $3$ と合成して 2[2,1] となる。
これはさらに直前の 2[1,1] と合成できるので、1[3,1] となる。
このとき二項係数は ${}_{1}\mathrm{C}_{0}=1$ なので、パターン数は $1$ のままである。

さらに 1[2,1] と 1[3,1] を合成する。
区間長は $5$ となり、パターン数は次のようになる。

$1\times1\times{}_{3}\mathrm{C}_{1}=3$

よって最終状態は 0[5,3] となり、この候補から作れる順列は $3$ 通りである。

以上より、答えは $3$ となる。

注意点

二項係数は $998244353$ を法として計算する。
逆階乗を求めるための除算は逆元を用いる。

剰余を取る前の乗算は int 型からはみ出るため、long long 型を用いること。

別解

特になし。