ブログ

特になし

D - ありんこ / CODE FESTIVAL 2015 あさぷろ Hard

問題

atcoder.jp

考察

(！: よりシンプルな解法が記事の下のほうにあります！)



蟻本の蟻の問題を彷彿とさせる問題設定です。

この問題をややこしくしているポイントとして、各アリの速度がそれぞれ異なるというのがあります。そのため各アリごとに最初に衝突するアリが明らかではなく、状況の把握が困難です。

しかし、全体で最初に衝突するのは、最初に棒上で隣り合っているアリのペアです（元々隣り合っていなかったアリのペアだとすると、隣り合うアリが入れ替わる時点でより早い衝突が起きたことになります。下の図参照）。

f:id:gzlcp:20200505003826j:plain

なので全体で最初の衝突を考える限りは、各アリが進行方向で最近のアリに衝突すると思い込んでも問題なく、状況が把握しやすくなります。

ところで、この問題のような「何らかの最小値を最大化する問題」では、解を二分探索する方針がしばしば効果的です。この問題で解を二分探索すると「ある値 x について、K 匹以下のアリを取り除くことで最初にアリが衝突する時間を x 以上にできるか？」という問題を繰り返し解くことに換言されます。

結論から言えば、この換言された問題は動的計画法を用いて解くことができます。

DP[i] (1 ≦ i ≦ N) を、「左から i 番目までのアリだけを考えたときに、最初にアリが衝突する時間を x 以上にするために取り除く必要のある（ただしちょうど i 番目のアリは残す）アリの匹数の最小値」と定義します。DP[i] の値を、j < i なる DP[j] の値を用いて計算することが目標です。

残すアリを右から見て、i 番目のアリの次に残すアリの番号で場合分けをします。i の次に残すアリの番号が j である場合を考えます。

まず大前提として、i 番目のアリと j 番目のアリが衝突するまでの時間が x 以上である必要があります。この前提は成り立っているとき、この場合における、取り除く必要のあるアリの匹数の最小値は、「DP[j] + (i 番目のアリと j 番目のアリの間にいるアリの匹数)」になります（冒頭で述べた性質より、j 番目より左側に残すアリと i 番目のアリとの衝突は考えなくていいことに注意します）。

このような方針をナイーブに実装する（全ての j を素直に 1 つずつ調べる）と、全体で二乗の計算量がかかります。DP の遷移を高速化できないか考えてみます。

まず注目すべきなのは、「i 番目のアリと j 番目のアリが衝突するまでの時間は x 以上か？」という問いには、それぞれのアリの初期位置と速度から定まる値を比較することで簡単に答えることができる、という点です。具体的には、
a[i] = (i 番目のアリの初期位置) + x * (i 番目のアリの速度)
と定めたとき、上の問いの答えが YES になる条件は a[i] ≧ a[j] になることです（衝突時間を x 以上とおいた式を式変形すれば分かります）。

また新しく
DP'[i] = DP[i] + (N - i)
と定めると、
DP[i] = max{DP'[j] | j < i, i 番目のアリと j 番目のアリが衝突するまでの時間は x 以上} - (N - i + 1)
と、遷移のコストが j に依存しなくなり、単純な max 演算で DP[i] の値を計算できるようになります。

f:id:gzlcp:20200505015641j:plain

以上 2 つの性質を考えると、DP の遷移を高速化（1 つの i あたり O(log N)）することができます。つまり、まずあらかじめ a[i] の値が小さい順に（並び順とは別の）番号を振っておきます。そしてこの番号で添字付けたセグメントツリーに各 DP'[i] の値を載せていけば、DP[i] の値はこのセグメントツリーに対する RMQ の結果を用いて高速に計算できます。

二分探索とセグメントツリーで 2 つの log が付くので、けっこう TL がシビアです。



（！: ここから別の解法）

実は（？）こんなに面倒なことをしなくても問題を解くことができます。
まず二分探索はするとして、「アリの最初の衝突までの時間を x 以上にできるか？」を考えます。ここで、各アリ i の x 秒後の位置が p[i] だとします。すると、p が含む増加部分列に対応するアリを残した場合、x 秒後までにアリの衝突は起きないことが分かります。従って p の LIS を求めて、これが長さ N - K 以上であれば OK です。
（解法を教えてくださったすぬけさん、ありがとうございます m(_ _)m）

多項係数の偶奇

多項係数 \frac{n!}{k_1!~k_2!~\ldots~k_m!} の偶奇を求めたくなることはよくあると思います。
Lucas の定理を使えば形式的に計算できますが、ここでは組合せ的な方法で多項係数の偶奇を求めてみます。

まず多項係数の値は、一列に並べた n 個のボールのうち k_i 個を色 i で塗る方法の数と解釈できます。なのでそのような塗り方の偶奇を考えます。
ここで色の塗り方が左右対称でない場合、左右反転することで異なる塗り方と対応付けることができます。

f:id:gzlcp:20200424095627p:plain
この塗り方を反転すると
f:id:gzlcp:20200424095620p:plain
こうなる、逆も同じ

つまり左右対称でない色の塗り方は偶数です。よって塗り方全体の偶奇は左右対称な塗り方の偶奇に等しいです。

n が偶数のとき、 k_1, k_2, \ldots, k_m の中に奇数があれば左右対称な塗り方は存在しません。この場合、塗り方の総数は偶数と分かります。 k_1, k_2, \ldots, k_m が全て偶数なら、左右対称な塗り方の数は \frac{n}{2} 個のボールのうち \frac{k_i}{2} 個を色 i で塗る方法の数と一致します。

n が奇数のとき、 k_1, k_2, \ldots, k_m の中の奇数がちょうど 1 つでなければ、左右対称な色の塗り方は存在しません。このときも塗り方の総数は偶数と結論できます。そうでないとき、一般性を失わずに k_1, k_2, \ldots, k_m の中で k_1 だけが奇数であるとします。この場合、左右対称な塗り方の数は、 \frac{n - 1}{2} 個のボールのうち \frac{k_1 - 1}{2} 個を色 1 で、 \frac{k_i}{2} 個を色 i (2 \leq i \leq m) で塗る方法の数に等しいです。

以上のどちらの場合でも、小さい問題への帰着は各 n, k_1, k_2, \ldots, k_m の右シフトに等しくなっています。これを踏まえると、 n, k_1, k_2, \ldots, k_m をそれぞれ 2 進数で表したとき、 n で 0 になっている桁については k_1, k_2, \ldots, k_m でも 0、 n で 1 になっている桁については k_1, k_2, \ldots, k_m の中でちょうど 1 つが 1 になっていることが多項係数の値が奇数になることの必要十分条件になります。

これは k_1~\text{or}~k_2~\text{or}~ \ldots ~\text{or}~k_m = n と 1 つの式で表すことができます ( \text{or} は整数の bitwise OR)。