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)$。

JOI2008 春合宿 - ナイルドットコム

• 問題
• AC

$f(x) := x$日目を終えた時点での最小金額 とするとき、

$$f(x) = \min \begin{cases} f(x-1) + 1日間同じ店で購入する場合の最小金額 \\ f(x-2) + 2日間同じ店で購入する場合の最小金額 \\ ... \\ f(0) + x日間同じ店で購入する場合の最小金額 \end{cases}$$

となっている。上から順に、つまり$k=1, 2, ..., x$という順に$k$日間同じ店で購入する場合の最小金額を求めていくのは、ひとつ前の情報を利用すれば${O}(N)$で可能なので、全体の計算量は${O}(ND^2)$になる。

この方針だと割り算を排除しないと通らなかった。実際のループ回数は$2 \times 10^8$くらい？

---

もっとましな方法があるらしいのであとで確認する。というか、2008年当時なら通ってなさそう。

KUPC 2014 I - Rain

• 問題
• AC

合計雨量の差にしか興味がないので、費用$d_i$を使って呪文$i$を唱えると地域$b_i$の雨量が$1$減り地域$a_i$の雨量が$1$増える、つまり雨量が$1$移動するとだけ考えればよい。雨量の移動を自由に繰り返して最小コストで雨量を平準化するのは、最小費用流問題そのものである。

最初の雨量はどの地域も$0$とし、呪文$c_1, ..., c_M$を唱えて雨量が$p_1, ..., p_K$になったとする。グラフは次のように作ればよい:

• $p_v>0$なら、始点$S$から$v$に容量$p_v$、コスト$0$の辺を張る。
• $p_v<0$なら、$v$から終点$T$に容量$-p_v$、コスト$0$の辺を張る。
• 各$b_i$から$a_i$に容量$\infty$、コスト$d_i$の辺を張る。

$S$の出容量のぶんだけ$T$に流したときの最小コストが答えであり、必要な量を流せない場合は$-1$である。計算量（の一例）は${O}(KE \log V)$。

JOI2011 本戦 D - 歩くサンタクロース

• 問題
• AC

ひとまず一次元の問題として考える。つまり、数直線上のある地点$t$に降り立って、各点$x_1, x_2, ..., x_n$に行って帰る問題である。さらに$x_1 \le x_2 \le ...\le x_n$と仮定する。最後に訪れる点を$x_k$とする時、総距離は

$$\ 2|t-x_1| + .... + 2|t-x_{k-1}| + |t-x_{k}| + 2|t-x_{k+1}| + ... +2|t-x_n|$$

となる。絶対値関数の和は下に凸になり、区分する点の中央値で最小値を取ることを使えそうな気がする。しかし、係数が邪魔なので開いて並べる:

$$|t-x_1|, |t-x_1|, ... , |t-x_{k-1}|, |t-x_{k}|, |t-x_{k+1}|, ... , |t-x_n|, |t-x_n|$$

これら$2n-1$個の点の真ん中にある点$x_l$は（奇数個だから）一点に定まるので、上の式に$t=x_l$を代入すると最小値が求まる。具体的には、右側にある$n-1$個の$x_i$を足して左側にある$n-1$個の$x_i$を引けばよい。最後に訪れる点を$n$通り試せば答えがわかる。二次元の場合もまったく同じで、$x$方向と$y$方向について独立に求めてから和を取ればよい。

実装について。いろいろやり方はありそうだけど、ソートされた列に順序を保って挿入・削除する操作があって、さらに区間の和が高速に求まれば直接的にシミュレーションできるのでそれがもっとも簡単に見える。平衡二分木ならどちらも${O}(\log N)$でできる。

---

けっきょく真ん中になりえる点は1個か2個しかないので、それを試すだけでよいらしい。途中で気づきたかった。

JAG Summer Camp 2013 Day 2 G - Perm Query

• 問題
• AC

与えられた置換$p$を巡回置換の合成$\sigma_1\sigma_2 ... \sigma_k$に分解して、ある巡回置換$\sigma$に注目する。$\sigma$の長さが$d$とすると、

• 列$\sigma x$の区間$[l, r]$の総和
• 列$\sigma^2 x$の区間$[l, r]$の総和
• ...
• 列$\sigma^d x = x$の区間$[l, r]$の総和

をすべて足せばこの巡回置換を一周した場合の総和が求まることになる。この際、巡回置換に現れるすべての数は同じ回数だけ$[l ,r]$に現れるので、上の総和は巡回置換に登場する数の総和の倍数になっている。

また、問題のようにすべての巡回置換を同時に適用した場合、次にもとに戻るのは（区間$[l, r]$に登場する）すべての巡回置換の長さの最小公倍数である。これを$\operatorname{LCM}(l, r)$とすると、$\operatorname{LCM}(l, r)$回の操作を行う場合、長さ$d$の巡回置換については$\operatorname{LCM}(l, r)/d$周することになる。この際、巡回置換に登場する数で最初に区間$[l, r]$に含まれていたものが$q$個であるとすると、巡回置換に登場する数はそれぞれ$q\operatorname{LCM}(l, r)/d$回足されることになる。

---

実装で迷った末に、Moのアルゴリズムを使った。

区間$[l, r]$についての値がわかっているとき、$[l, r+1]$の値を考える。まず、区間が伸びたことによって操作回数が$\operatorname{LCM}(l, r)$から$\operatorname{LCM}(l, r+1)$に伸びるので、既存の値が$\operatorname{LCM}(l, r+1)/\operatorname{LCM}(l, r)$倍になる。また、位置$r+1$が追加されるので、この位置を含む巡回置換$\sigma$の長さ$d$について、$(巡回置換 \sigma に登場する数の総和) \times \operatorname{LCM}(l, r+1)/d$が加算されることになり、新しい値が求まる。区間が縮む場合も同様に書ける。

$\operatorname{LCM}(l, r)$の値を得るのにsparse tableが使えるから計算量の問題はないと思って書き出したのだが、伸縮の際にmodの割り算が必要になるので結局$\log$がついて${O}(N \sqrt{Q} \log N)$だった。^[1]

---

lcmと同時に、それぞれの巡回置換の総和もセグメント木で持てばよいらしい。それはそうか……

---

1. lcmの範囲が大きいので逆数のテーブルは用意できない。でも、うまい方法がありそうな気もする。 ↩︎

ARC 014 - 魂の還る場所

• 問題
• AC

隣り合う同じ色の2つのボールは即消せるので、その部分は最初から存在しないものとしてよい。また、GBGのように1つ挟んで同じ色のボールも消すことができて、間のBは左右の好きなほうに置くことができるので、やはり2つのGは最初から存在しないものとしてよい。これらのパターンを連鎖的に消していけば、残るのは距離2以内に同じ色のボールがない並びのみで、これはRGBRGBRGB...のように周期3の列になっている。そしてやはりこのパターンも各色の偶数個分は全部消せる。つまり、各色の偶奇を判定して$0$から$3$までのいずれかを答えにすればよい。

ARC 049 B - 高橋ノルム君

• 問題
• AC

時間$t$が与えられたとき、$i$人目のノルム君の行ける範囲は$[x_i-t/c_i, x_i + t/c_i] \times [y_i -t/c_i, y_i + t/c_i]$となる。これらの$N$個の区間の共通部分が空でないことと、時間$t$内にすべてのノルム君が一点に到達できることは同値である。したがって、$t$について二分探索すればよい。

---

判定の部分を深く考えずに平衡二分木上のいもす法でやってしまったのだが、よく考えると区間の両端を保持するだけでよかった。

ARC 044 B - 最短路問題

• 問題
• AC

とりあえずソートしてランレングス圧縮して、同じ距離の頂点グループ毎にグラフを作っていくことを考える。距離$0$は頂点$1$だけとか、距離が飛んでいる部分があってはいけないとか、そういうケースは最初に考慮しておく。

頂点$1$からの距離が$i$の頂点が$B_i$個あるとする。距離$i$の頂点同士はどうつないでもほかの頂点と$1$との距離に影響しない。したがって、$\binom{B_i}{2}$通りのペアすべてに自由に辺を張れるので、距離$i$に対して$2^{\binom{B_i}{2}}$通りの辺の張り方があることになる。

次に、距離$i-1$の頂点グループと距離$i$の頂点グループをつなぐ辺の張り方を考える。これもだいたい自由に辺を張れるのだが、距離$i$の頂点は、距離$i-1$の$B_{i-1}$個の頂点のうち少なくとも1つにはつながれていなければならないという制約がある。「少なくとも1つ」は包除原理で書ける:

$\begin{aligned} & 2^{B_{i-1}B_i} - \binom{B_i}{1}2^{B_{i-1}(B_i-1)} + \binom{B_i}{2}2^{B_{i-1}(B_i-2)} - ... + (-1)^{B_i}\binom{B_i}{B_i}2^{B_{i-1} \cdot 0} \\ = & \sum_{k=0}^{B_i} \binom{B_i}{k}(-1)^k(2^{B_{i-1}})^{B_i-k} \\ = & (2^{B_{i-1}}-1)^{B_i} \end{aligned}$

あっ……

---

包除で求めてから自明な数え方に気づくパターン、これで3回目くらい。

JOI2018 予選 F - L番目のK番目の数

• 問題
• AC

0-based($A_0, A_1, ..., A_{N-1}$)で考える。

書き出した数の中に$x$以下の数が$f(x)$個あるとするとき、$f(x) \ge L$となるような最小の$x$を求めればよい。この言い換えを元の数列$(A_i)$の言葉でさらに言い換えると、次のようになる:

$x$以下の数を$K$個以上含むような部分列$A[l, r)$が$L$個以上存在するような$x$の中で最小のものを求めよ。

部分列$A[l, r)$が$x$以下の数を$g(l, r, x)$個含むとする。$x$を固定した時に$、g(l, r, x) \ge K$であるような$l, r \in [0, N]$が何組あるか数えられれば、二分探索で上の$x$も求まりそう。具体的には次のように数える:

$g(0, i, x)$は部分列$A[0, i)$の中の$x$以下の数の総数だから、累積和でテーブルを作っておけば任意の$i$について$O(1)$で求まる。そして、$g(l, r, x) = g(0, r, x) - g(0, l, x) \ge K \Leftrightarrow g(0, r, x) \ge K+g(0, l, x)$であり、$l$を固定した時にこの式を満たすような$r$の数は二分探索で求まる。したがって、すべての$l \in [0, N]$についてこの$r$の数を求めて足し合わせると、それが$f(x)$である。

あとは$f(x)$について二分探索して、$f(x) \ge L$であるような最小の$x$を求めればそれが答えになっている。計算量は${\mathcal O}(N \log^2 N)$。

ARC 024 C - だれじゃ

• 問題
• AC

「（部分列に）文字$c$がちょうど$x$個含まれること」の$26N$通りすべてに対して、あらかじめ乱数$R_{c, x}$を割り振っておく。 最初の$K$文字のヒストグラムを作って、各文字$c$について該当する$R_{c, x}$のXORを取って、最初のハッシュ値とする。

あとは、長さ$K$の部分列をスライドさせながら各部分列のハッシュ値を求めていく。直前の部分列のハッシュ値が$V$であったとし、文字$c$が加わって$c$の数が$x$から$x+1$に増え、文字$d$が除かれて$d$の数が$y$から$y-1$に減るとすると、新しい部分列のハッシュ値は$V \oplus R_{c, x} \oplus R_{c, x+1} \oplus R_{d, y} \oplus R_{d, y-1}$になる。このハッシュ値をキーとして、部分列の開始位置を保持しておく。同じハッシュ値が再び出現した時、開始位置が$K$以上離れていればアナグラムダジャレが見つかったことになる。

アルファベットのサイズを$\alpha$とするとき、計算量は${\mathcal O}(\alpha N)$。

---

こんなことしなくても、普通にヒストグラムをキーにするだけで通った……