ARC 032 - 仕事計画

• 問題
• AC

辞書式順序の条件を無視すればただの区間スケジューリングなので、始点$a_i$でソートして逆から貪欲に選んでいけば仕事の数の最大数$k$が求まる。この際に得られた仕事の列が開始から

$$ (a'_1, b'_1), (a'_2 b'_2), ..., (a'_k, b'_k) $$

となっているとする。このとき、次の性質があることに注目する:

• $k-1$個の仕事をこなすためには、少なくとも$a'_2$までには始めなければならないし、$a'_2$までに始めれば$k-1$個の仕事が可能である
• $k-2$個の仕事をこなすためには、少なくとも$a'_3$までには始めなければならないし、$a'_3$までに始めれば$k-2$個の仕事が可能である
• ...
• $1$個の仕事をこなすためには、少なくとも$a'_k$までには始めなければならないし、$a'_k$までに始めれば$1$個の仕事が可能である

これらの性質から、$k$個の仕事からなる辞書順最小のスケジュールを構成する方法が従う:

• $1$個目の仕事は$a'_2$までに終わるものならなんでも可能である。このうちインデックスが最小のものを$(l_1, r_1)$とする。
• $2$個目の仕事は$r_1$以降に始まって$a'_3$までに終わるものならなんでも可能である。このうちインデックスが最小のものを$(l_2, r_2)$とする。
• ...
• $k$個めの仕事は$r_{k-1}$以降に始まるものならなんでも可能である。このうちインデックスが最小のものを$(l_k, r_k)$とする。

こうして辞書順最小のスケジュール$(l_1, r_1), ..., (l_k, r_k)$が得られた……わけだが、実際にこのスケジュールを求める手順がまだ明らかでない。

時間$x$に始まって$y$に終わる仕事のインデックスを$f(x, y)$とするとき（複数ある場合、インデックスが最小のもの以外は捨ててよい）、仕事は二次元空間上の点とみなせるので、上の性質をさらに言い換えられる:

• $[0, a'_2] \times [0, a'_2]$上にある仕事について$f(x, y)$の最小値を求める。$(l_1, r_1)$で最小になるとする。
• $[r_1, a'_3] \times [r_1, a'_3]$上にある仕事について$f(x, y)$の最小値を求める。$(l_2, r_2)$で最小になるとする。
• ...
• $[r_{k-1}, +\infty] \times [r_{k-1}, +\infty]$上にある仕事について$f(x, y)$の最小値を求める。$(l_k, r_k)$で最小になるとする。

ここまで整理すると、$\min$を乗せたrange treeで実行できる手順になっている。計算量は${O}(N \log^2 N)$。

---

線形で求まるのは、手順を示されれば確かにとなるけどまったくわからなかった。

今出題されたら、もう少し制約が大きくなって$\log^2$は落ちる気がする。この方針のままでも、2D range tree + fractional cascading + 構築${O}(N)$クエリ${O}(1)$のRMQで$\log$を1つにできそう？ でも、そもそも平面走査的になんとかできないのかな。

CODE FESTIVAL 2015 E - ショートコーディング

• 問題
• AC

次の3つの変形を適用していく:

• $!!! = \ !$
• $-- = \ \operatorname{id}$
• $!- = \ !$

このとき、可能な解は$!!, !, \operatorname{id}, -!!, -!, -$の6つしかないことがわかる。

WUPC 2019 C - Choose Your Characters

• 問題
• AC

勝てない相手キャラがいないような最短の区間を尺取り法で求める。つまり、$\operatorname{dp}[i] :=$キャラ$i$が勝てるキャラの数、として各区間について正しい$\operatorname{dp}$を求めて、$\min_i \operatorname{dp}[i] >0$になるような最短の区間を探せばよい。

具体的には、最初に

$S(i) :=$ キャラ$i$が勝てないキャラの集合（同キャラ含む）

と言うデータを作っておく。区間を伸ばすときは$\operatorname{dp}$全体に1を足してから各$k \in S(i)$について$\operatorname{dp}[k] \mathrel{{-}{=}} 1$とし、区間を縮めるときには$\operatorname{dp}$全体から1を引いてから各$k \in S(i)$について$\operatorname{dp}[k] \mathrel{{+}{=}} 1$とする。$\operatorname{dp}$にセグメント木等を使えば簡単。

---

ようやく尺取り法の間違えにくい書き方にたどり着いたのでメモ。

• ok関数とng関数で相互再帰する。
• 常に半開区間$[l, r)$を扱う。(ok l r)は$[l, r)$が条件を満たすときに呼び出され、(ng l r)は$[l, r)$が条件を満たさないときに呼ばれる。rはこれから追加される位置であり、lはこれから除去される位置である。
• (ok l r value)のように区間に関する値を受け渡す場合、valueは常に区間$[l ,r)$に対応する値になるようにする。
• 最適値を求める場合はok関数の冒頭で更新する。

JOI2018 本戦 B - 美術展

• 問題
• AC

最初から$A_1 \le A_2 \le ... \le A_N$であると仮定してよい。この場合、大きさの最大と最小が決まっていればその範囲にある美術品はすべて展示したほうが得なので、美術品の連続部分列だけ考えればすむ。

美術品$i$を展示しているとき、さらに$i+1$を展示すると得点は$B_{i+1}-(A_{i+1}-A_i)$だけ増えることに注目してDPする。$\operatorname{dp}[i] := i$まで展示するとした時の最大得点、として以下のように更新していけばよい:

$$ \operatorname{dp}[i] \leftarrow \max(\operatorname{dp}[i-1] + B_{i}-(A_i-A_{i-1}), B_{i}) $$

答えは$\max_{i \in [N]} \operatorname{dp}[i]$。

---

いわゆるKadane's algorithmっぽい感じなんだけど、なぜかそれをそのまま書いてしまってWAした。

JOI2010 春合宿 - Stairs

• 問題
• AC

$x$段目の地面からの高さを$H_x$とし、$x$段目までの上り方の総数を$f(x)$とする。$H_l \ge H_x - P$となるような最小の段を$l$段目とするとき、$f$の漸化式は

$$ f(x) = \sum_{t \in [l, x)}f(t) $$

と書ける。このままDPすると間に合わないので累積和$S(x) := \sum_{t=0}^xf(t)$を考える。

$$ f(x) = S(x-1) - S(l-1) $$ $$ S(x) = f(x) + S(x-1) $$

が成り立つから、$S$の漸化式は

$$ S(x) = 2S(x-1) - S(l-1) $$

とまとまる。$S$に関してDPすればよい。答えは$f(N) = S(N)-S(N-1)$である。

毎回$l$を二分探索で求めると計算量は${O}(N\log N)$。尺取り法で${O}(N)$。

JOI2010 本戦 C - つらら

• 問題
• AC

つらら$v$より$v+1$のほうが長いとき、$v$は$v+1$が$L$に達して$0$に戻るまでは伸びない。この時$v+1$から$v$に辺を張ることにすると、DAGが得られる。そこで、トポロジカルソートした上で辺$(u, v)$に対して

$$ \operatorname{dp}[v] \leftarrow \max(\operatorname{dp}[v], \operatorname{dp}[u] + L - a_v) $$

と更新していけば、最終的には$\operatorname{dp}[v] = v$が$0$に戻るまでの時間、となる。$\operatorname{dp}$の初期値は$\operatorname{dp}[v] := L - a_v$としておくのがわかりやすそう。${O}(N)$。