JOI春合宿2017 Day1 手持ち花火（Sparklers）の別解と上位問題の解法

こんにちは。今回はタイトル通りのことについて気づいたので紹介していこうと思います。
一応注意をしておくとネタバレを含むので、見たくない人は見ないでください。
また、この記事を書くにあたってsnukeさんに多大な助言をいただきました。この場で感謝します。

この問題の詳細はこちらをどうぞ。
JOI 2016/2017 春季トレーニング合宿課題

読み進めるとわかりますが、一部想定解法は上記にある解説ページがベースになっています。
また、のちのちSegmentTreeが現れますが、かなりざっくりとした説明ですので、SegmentTreeを知らないと読めないと思います。

問題文

まずはこの問題の問題文を整理するところから始めます。

${N}$ 人の人が一直線上に並んでおり、それぞれの人が一つずつ花火を持っている。
それぞれの花火に火はついていない。
${K}$ 番目の人は時刻 ${0}$ に自分の花火に着火する。
花火を持っている人と花火を持っていない人が同じ時刻に同じ場所にいれば花火を持っていない人に花火を着火することができる。ただし、同時刻・同場所にいても花火を着火させないこともできる。
それぞれの花火は着火後 ${T}$ 秒で消えてしまう。
それぞれの人の花火は1度までしか着火できない。
次のことができる各人の移動速度の上限 ${s}$ として最小のものを求めよ : 時刻 ${0}$ より適切にそれぞれの人を移動させることによって、それぞれの人の花火が一度点火される。

整理

入力は ${N,K,T}$ と各人の時刻0での位置 ${x[i]}$
出力は最小の移動速度の上限 ${s}$

重要な制約

${N \leq 10^5}$

解法

基本的にはスライドを参照すればよいが、ここで簡単におさらいする。

記法 : 以下 ${x[i]}$ の最大値を ${U}$ とする。

${O(N^2 \log U)}$ 時間解法

まずは二分探索したいので、移動速度の上限 ${s}$ を決め打ち、ある上限速度 ${s}$ ですべての花火が点火されるかを判定する問題を解くことにする。この問題もそれなりに難しく、正当性を確かめるのに少し苦労はするが、次のような結果を得る。

まず、 ${L \leq K \leq R}$ となる ${L,R}$ を用意する。
このとき、区間 ${[L,R]}$ に入るすべての人に花火をつけるためには ${(x[R] - x[L]) / (R - L) \leq 2sT}$ である必要がある。

逆にこれを達成するためには、 ${L=R=K}$ からはじめて( ${L}$ をデクリメント) or ( ${R}$ をインクリメント)のどちらかの操作を繰り返し、上記式を常に達成できれば良い。

つまり、すべての ${L,R}$ について ${(x[R] - x[L]) / (R-L) \leq 2sT}$ をチェックし、その結果をoxを用いてグリッドに書き込めば、
そのグリッドの左下から右上まで oのみを使って到達できるかどうかを判定する問題になる（下図参照）。

f:id:tokoharu-sakura:20170410224334p:plain

これで ${O(N^2 \log U)}$ 時間で計算できることがわかる。

${O(N \log U)}$ 時間解法（解説スライドにおける想定解法）

上記の解法に工夫を加えて ${O(N)}$ 程度に落とすために、まずは式変形をして、
${x[R] - 2sTR \leq x[L] - 2sTL}$ とする。
この式は非常に都合がよく、 ${X[i] := x[i] - 2sTi}$ とおけば
${X[R] \leq X[L]}$ で判定可能である。

これを眺めるとうまい性質がわかる（らしい）ので、それを用いると貪欲的に解けるという主張になる。
（あとはスライドを読んでください）

別解

ここからは考えた別解について説明していきます。
その際、書き込んだoxの性質についてみていきます。

oxの並び方の観察

まず、次の性質が簡単に示せます。

性質1 : 次の図のような配置はありえない。

証明はXを用いれば簡単にできる。
oxが書き込まれる条件を思い出せば
${X[j_2] \leq X[i_2]}$ ,
${X[j_1] \leq X[i_1]}$ ,
${X[i_1] < X[j_2],}$
${X[i_2] < X[j_1]}$ が得られる。
これらをすべて足せば ${0< 0}$ が現れるため矛盾する。

次に、ある種貪欲的に進めてうまくいくことを示す。
そのために次の性質2を示す。

性質2 : まず、到達可能性を定義しておく。 ${(L,R)=(l,r)}$ に到達可能であるとは、 ${(L,R)=(K,K)}$ より始めて ${L}$ をデクリメントもしくは ${R}$ をインクリメントを続けて、x印を通らずに ${(L,R)=(l,r)}$ に到達できることと定義する。
仮に、 ${(L,R)=(i,j)}$ が到達可能かつ、 ${(L,R)=(i,j+1)}$ が到達不可能であるとし、さらに ${i}$ より小さい ${t}$ に対して ${(L,R)=(t,j+1)}$ にo印であったとする。この ${t}$ は最小(図で考えると一番上)のものをとることにする。
このとき ${(L,R)=(t,j+1)}$ に到達可能であることが言える。
特に、下図の赤印のような関係になっていることが言える。

この証明は性質1を用いればできる。つまり、図の赤o印の箇所を ${(i_2,j_1)}$ とおき、 ${j_2=j+1}$ とおく。 ${i_1}$ は ${(i_1,j_1)}$ がo印になっているようにとる。
このとき、性質1より

ox
xo

のような位置関係は禁止されているが、
上記のように ${i_1,i_2,j_1,j_2}$ を定めれば

ox
?o

のような位置関係になっていることがわかる。
性質1より'?'はo印にしかなりえない。
これを繰り返せば赤印のような箇所にo印をつけることができるため、
結局 ${(t,j+1)}$ も到達可能であることがわかる。

アルゴリズム

さて、以上の性質2を使えば、次のような遷移をして右上マスに到達すればOKであることがわかる。

最初は ${(L,R) = (K,K)}$ とする

o印である限り、 ${L}$ を減らす(上へ進む)

Rをひとつ増やす。

もしoであれば上記のように ${L}$ をできるだけ減らす

そうでなければ ${L}$ を増やして(つまり下に進んで)o印が書かれている箇所を見つける(性質2より、これをみつければ必ず ${(K,K)}$ から到達可能。)

もしそのようなo印がなければ失敗。最初に定めた制限速度 ${s}$ では不可能であることがわかる。

最後に ${(L,R)=(1,N)}$ に到達すればOK

要するに、各 ${R=r}$ に対して到達可能な ${(L,R)=(l,r)}$ である ${l}$ のうち最小のもの（一番上にあるもの）を求めていることになる。

単純に進めるだけでは時間計算量の上界は ${O(N^2)}$ であるが、 ${N^2}$ 回程度の移動回数を必要とするような入力はこのアルゴリズムに気づかなければ構成が難しい。
ということで最悪で ${O(N^2)}$ 時間かかるコードを実装して提出してみたが、春合宿で用意されたデータセットすべてに正答することができた。

改良アルゴリズム

さて、改良できそうな箇所は最も近いx印の場所を求めたり最も近いo印の場所を求めることである。

これは次のようなアルゴリズムで実現可能である。
都合上片方のケースのみで考えるが、問題は次のように言い換えるとわかりやすい。

「配列 ${X}$ とインデックス ${i}$ が与えられる。ただし ${X[R] \leq X[i]}$ であるとする。
${i}$ より小さい ${j}$ のうち、 ${X[R] > X[j]}$ となるような最大の ${j}$ を求めよ。」

これは次のようなデータ構造を持てばできる。
例えば最小値を持つRMQを用いて二分探索のようなことをする。
まず ${O(\log N)}$ 個くらいの調べたい範囲を持ってきて、それぞれの最小値を調べる。
これらの中ではじめて最小値が ${X[R]}$ を下回る箇所を持ってくる。
この範囲で、segment tree上で二分探索をすればできる。
これは1クエリあたり ${O(\log N)}$ 時間で計算できる。

この解法から現れる上位問題

さて、ここまででtokoharuの考えた別解を紹介しましたが、想定解法のアルゴリズムをちゃんと理解している人であれば想定解法の方が好ましいと考えるかと思います。なぜなら想定解法の方が（たぶん）シンプルにほぼ線形時間アルゴリズムを構築できるからです。

とはいえ、この別解からは面白いことがわかります。
それはSparklersの上位問題が解けてしまうからです。

ここで上位問題の問題文を記述することにします。強調した部分以外は同じ文章になります。

${N}$ 人の人が一直線上に並んでおり、それぞれの人が一つずつ花火を持っている。
それぞれの花火に火はついていない。
誰か一人が時刻 ${0}$ に自分の花火に着火する。
花火を持っている人と花火を持っていない人が同じ時刻に同じ場所にいれば花火を持っていない人に花火を着火することができる。ただし、同時刻・同場所にいても花火を着火させないこともできる。
それぞれの花火は着火後 ${T}$ 秒で消えてしまう。
それぞれの人の花火は1度までしか着火できない。
次のことができる各人の移動速度の上限 ${s}$ として最小のものを求めよ : 時刻 ${0}$ より適切にそれぞれの人を移動させることによって、それぞれの人の花火が一度点火される。

太文字で強調した通り、 ${K}$ が消えてしまい、スタートが誰でも良くなってしまい、難易度が上がります。
しかし別解と同様の方針で考えればこの問題でも解くことが可能です。

これを確かめるために、もう一度「性質1」と「性質2」を確認してみます。
よく考えるとこの二つの性質は図を180度回転しても成立することがわかります。
つまり、性質2で出てきた到達可能性について ${(L,R)=(1,N)}$ を始点としても同様の性質が成り立つことがわかります。

これがわかると、次の図のような到達可能性を調べればよいことがわかります。
f:id:tokoharu-sakura:20170411005130p:plain