日本橋ハーフマラソン 2021

• 提出

A - 魔法使いXの戦い

308662点。1つのモンスターにつき、だいたい3回くらいパワーアップできる計算で、3回ならひとつずつ最適な組み合わせを貪欲に取っていけそう。素朴にやると${O}(N^4)$だが、最後は二分探索でよいので${O}(N^3 \log N)$。

まだ回数に余裕があるので、末尾に近いモンスターは4回パワーアップしたいが、これは素朴に探索すると間に合わない。$q$に選ぶモンスターから近い数値で固まっているものを省いたりして間に合う程度のノード数に減らした。

探索する順番を工夫すれば少し伸びるかもと思っていろいろ試したが伸びず。

B - マッサージチェア2021

210901点。一点のパワーを変更して干渉する点のパワーを減らすだけの山登りをした。すぐに収束してしまうが、簡単に書けそうな他の遷移もないので多点スタートなどで時間を使い切ることにした。一点のパワーを下がるほうに変更するような完全に無駄な遷移も入れてしまっているなど、いろいろ詰めが甘かった。

AtCoder Adのように、1つのノードを大きくして周りのノードを小さくする操作と、1つのノードを小さくして周りを大きくするような操作を組み合わせて再帰的に頑張るともう少しよくなるかもと思ったが、この時間では書ける気がしなかった。

マス$(i, j)$のパワーを表す変数を$p_{i,j}$とし、マス$(i, j)$に正のパワーを与えることをバイナリ変数$x_{i, j}$で表すと、素朴なMIP定式化は

maximize $E_{i, j}p_{i, j}$
subject to

• $0 \le p_{i, j} \le Nx_{i, j}$
• $p_{i_1, j_1}-N(1-x_{i_2, j_2})\le |i_1-i_2|+|j_1-j_2|-1$

という感じか。

---

解説を見ると全然問題の性質をとらえられていないなと思う。短時間コンテストは自明な方針を手早く実装したあと細部の詰めで同方針の人にちょっと勝つだけでそれなりの順位がとれてしまうことがありそう。

Treapのunionの計算量に関するメモ

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf に$m, n \ (m \le n)$要素のTreapのunionで期待計算量が${O}(m \log (n/m))$であるものが紹介されている。これを使うと次のことができる:

1要素のTreapが$N$個与えられたとし、これらのTreapに任意の順番で$N-1$回unionを適用して$N$要素のTreapを作るとする。この時、全体の期待計算量は${O}(N \log N)$である。

これはマージテクと同じように理解できる:

まず、定数$B$が存在して$m, n\ (m \le n)$要素のTreapのunionの期待計算量は$B m \log (n/m)$以下である。

求める計算量を$T(N)$とする。$C>0$が存在して$N$未満の整数$x$については$T(x) \le C x \log x$が成り立っていると仮定する。このとき、$T(N) \le C N\log N$であることを示せばよい。この際、$C \ge B$としてよい。

$$ T(N) \le \max_{m+n = N} \bigl (Bm \log \frac{n}{m}+ T(m) + T(n) \bigr) $$

であるから、任意の分割$N = m+n \ (0 < m \le n)$について$Bm \log (n/m) + T(m) + T(n) \le C N \log N$が成り立つことを示せばよい。実際、次のように示せる:

$$ \begin{aligned}& Bm \log \frac{n}{m}+ T(m) + T(n) \\ \le \ & B m \log \frac{n}{m} + Cm\log m + C n \log n \\ \le \ & C \bigl (m\log\frac{n}{m} + m\log m + n \log n \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n \log \frac{n}{m}m \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n\log \frac{n}{m} + n \log m \bigr ) \\ = \ & C \bigl ((m+n) \log \frac{n}{m} + (m+n)\log m \bigr ) \\ = \ & C \bigl (N\log \frac{n}{m} + N \log m \bigr) \\ = \ & C(N\log n - N\log m+ N \log m) \\ = \ & CN\log n \\ \le \ & CN\log N \\ \end{aligned} $$

（$\log 1 = 0$ 問題があるのであまり正確でない。）

JAG Summer Camp 2017 Day 1 C - すごろく

• 問題
• AC

まずは$B_i$がすべて$0$であるような問題を考える。ループがない、つまり同じマスに二回止まることがないので、ゴール以前の各マスに止まる確率を足し合わせたものが求める期待値になっている。

$p(i) =$ サイコロを振って$i$が書かれた面が出る確率 $\operatorname{dp}[x] =$マス$x$に止まる確率

とするとき、0-basedで考えると遷移は

$\operatorname{dp}[x] = \sum_{0 \le k \le x}\operatorname{dp}[x-k]p(k)$

となって、これはオンラインFFTで解ける形になっている。

$B_i$が必ずしも0でない場合について考える。$B_x > 0$であるようなマス$x$については、オンラインFFT中に$\operatorname{dp}[x]$に加算する時に、代わりに$\operatorname{dp}[x+B_x]$に加算すればよい。また、$B_x < 0$、つまり休みのマスについては、そのようなマスに止まる確率$\times |B_x|$を結果に足せばよさそう……だが、他のマスから$B$の影響で進んできた場合は休まないので、$\operatorname{dp}$を構成し終えてから$\operatorname{dp}[x] \times |B_x|$を後で足すと正しく計算できない。やはりオンラインFFT中に$\operatorname{dp}[x]$に加算する瞬間に結果に足す必要がある。

KUPC 2016 H - 壁壁壁壁壁壁壁

• 問題
• AC (slope trick)
• 部分点 (単体法)

位置$i$から$i+1$に補強材を移動する量を$x_i$として制約を書き下す。$n=4$なら

• $A_1-x_1 \ge B_1$
• $A_2 + x_1-x_2 \ge B_2$
• $A_3 + x_2-x_3 \ge B_3$
• $A_4+x_3 \ge B_4$

という制約の下で$|x_1|+|x_2|+|x_3|+|x_4|$を最小化する問題になっている。

$f_i(x)$を$x_1, ..., x_{i-1}, x_i=x$までを決定した際の最小コストとする。slope trick向けに制約を変形すると、

• $x_1 \le A_1-B_1$
• $x_1 \ge x_2-(A_2-B_2)$
• $x_2 \ge x_3-(A_3-B_3)$
• $x_3 \ge B_4-A_4$

となって、一番上の$x_1$に関する制約を無視すると$f_i$の漸化式が得られる:

• $f_1(x) = |x|$
• $f_2(x) = \min_{t \ge x - (A_2-B_2)}f_1(t) + |x|$
• $f_3(x) = \min_{t \ge x - (A_3-B_3)}f_2(t) + |x|$

登場する操作はすべてslope trickで表現できて、答えは凸性により、$B_4-A_4$か$\argmin_xf_3(x)$の大きいほうの位置で$f_3$の値を求めると得られる。

制約$x_1 \le A_1-B_1$については、この範囲を超えると高いコストがかかることにして対処したい。$x_1$が$A_1-B_1$を$1$超過することによる利益が高々$C$であるとき、$f_1(x) = |x| + C\max(0, x-(A_1-B_1))$とすればよい。$C$の具体的な値としては、制約を$1$だけ破っている状態を解消するために1つの補強材を端から端へ移動すると$N-1$のコストがかかるので、$N-1$でよい。

CodeChef - CCDSAP Exam

• 問題
• AC

slope trickの練習問題として解いた。

人$i$の初期位置を$a_i$とし、人$i$を位置$x$に配置した場合の人$1, 2, ..., i$に関するコストの総和の最小値を$f_i(x)$とする。

左右の境界を無視すると$f_{i}(x) = \min_{t \le x-2}f_{i-1}(t) + |x-a_{i}| = \min_{t \le x}f_{i-1}(t-2)+|x-a_i|$と表せる。これだけなら普通のslope trickで解けるが実際には境界を越えられないところが難しい。

境界を越えたら大きなコストがかかるように、$|x-a_i|$の代わりに定数$C$を定めて$C\max(0, 1-x) + |x-a_i| + C\max(0, x-N)$を追加することを考えたが、これは優先度付きキューに一つずつ挿入していく方法では難しそう。平衡二分木で多重集合を管理すればいけそう？ → 平衡二分木slope trickを作ろうとしたが、最小値の更新が自明にはできない。おそらく任意の$x$について$f(x)$の値が取得できる必要があって、実現方法がわからなかった。ただ、$\min$がわからなくても$\argmin$は容易に取得・更新できる。これだけわかれば最適解を貪欲に復元できそう。最適解における人$i$の位置を$y_i$とする。$y_N=\argmin_x f_{N}(x)$は既知であり、$y_{i+1}$が既知であるとき$y_i$は

$$y_i = \min(\argmin_x f_{i}(x), y_{i+1}-2)$$

と決定できる。$\argmin$が複数ある時はどれを取ってもよい。

第七回 アルゴリズム実技検定

• 問題
• 提出

辛うじて全完したが、最後の問題の正しい解法がわからなかった。

K - 急ぎ旅

最短経路DAGを作ってからDPした。

ダイクストラと同時にできるらしい。確かに。

L - たくさんの最小値

最小値の列挙は遅延セグメント木上を二分探索すればできる。いつもこの方針でやっていて、想定解のようにノードに持たせる情報を増やすやり方でやったことがない。後者でないと難しい設問ってあるんだろうか。

M - 分割

明らかに最小費用流だと思ったが、グラフの作り方で長時間かけてしまった。

辺の下限流量を決めて変形するイメージで作った。まず、整数$A_i$を表す各位置$i$を$i_{\mathrm{in}}, i_{\mathrm{out}}$に分割する。

• $S$から$i_{\mathrm{out}}$に容量1、コスト0の辺を張る
• $i_{\mathrm{in}}$から$T$に容量1、コスト0の辺を張る
• $i_{\mathrm{out}}$から$T$に容量1、コスト$C$の辺を張る
• $i < j$であるすべての$j$について、$i_{\mathrm{out}}$から$j_{\mathrm{in}}$に容量1、コスト$|A_i-A_j|$の辺を張る

想定解は「通ってほしい辺」のコストを$-\infty$にしてから変形する考え方のようだった。こちらは全然考えたことがなかった。

N - モノクロデザイン

JOI 2012 春合宿 - fortune_telling

O - コンピュータ

$(B_i)$が狭義単調増加の場合が解ければよい。また、世界には$B_1, ..., B_N$円のコンピュータしか存在しないとしてよい。

$\operatorname{dp}[x] = x$日目でちょうどコンピュータを買い替えなければならない場合の最大所持金額

とする。$x$日目に買えるコンピュータは、所持金以下であるような最大価格のコンピュータを$r$として$B_x, B_{x+1},..., B_r$のいずれかであり、$B_y$を買うとすると遷移は$\operatorname{dp}[y+1] := \max(\operatorname{dp}[y+1],\operatorname{dp}[x]+A_{x+1}+A_{x+2}+...+A_{y+1}-B_y)$。$A_{x+1}+A_{x+2}+...+A_{y+1}$の部分を累積和で計算すると、このDPは${O}(N^2)$である。

$o(N^2)$にする方法がわからなかった。試しに、買うコンピュータを$x$か$r$だけにしたものを投げると半分以上は通る。それならと思って両端から2000個程度（$x, x+1, ..., x+2000$と$k-2000, ..., k-1, k$）の遷移に限定してみたらACした。

解説を見た。

$\operatorname{dp}[x] =$ コンピュータ$x$を買った時点での支出の最小値

とする。コンピュータ$p$を買ってから次に買うコンピュータとして$x$を選べる必要十分条件は$A_1+...+A_{p+1}-\operatorname{dp}[p] \ge B_x$であること。これが成り立つような$p$について、$\operatorname{dp}[x] := \min_p\operatorname{dp}[p] + B_x$と更新すればよい。

実装としては、range minを載せた平衡二分木のキー$A_1+...+A_{p+1}-\operatorname{dp}[p]$に値$\operatorname{dp}[p]$を対応させておけば、キーが$B_x$以上のノードについての$\operatorname{dp}[p]$の最小値を高速に求められる。

---

Oは今までのPASTで一番難しく感じた。

CodeChef - Short in Average

• 問題
• AC

$A$から$B$へのウォークが与えられたとする。このウォークが閉路を含んでいて閉路の平均長がウォークの平均長より小さいなら、何回も回ればウォークの平均長を閉路の平均長まで下げられるし、そうでないなら閉路を除いて損しない。また、閉路を含まないウォークは高々$N-1$本の辺しか含まない。従って、以下のようなアルゴリズムが考えられる:

1. $B$に到達できる頂点の集合$W \subseteq V$を求めて、以降は$W$による誘導部分グラフ上で考える。
   • この時点で$A$と$B$がつながっていなければ終わり。
2. Bellman-Ford法のようなDPをして、高々$N-1$辺を通るという条件の下での$A$から$B$までの最短平均長ウォークの長さを求める。
3. $A$から到達できる最短平均長閉路の長さを求める。
4. 2と3の小さいほうを取る。

実装上は3のアルゴリズムが2のDPを含んでいる。2は$N-1$回、3は$N$回回す必要があるので、最初から$N$回回せばよい。

3については、$\operatorname{dp}[k][v] =$ちょうど$k$本の辺を使う場合の$S$から$v$への最短経路、として

$$ L = \min_{v \in N}\max_{k = 0, ..., N-1} \frac{\operatorname{dp}[N][v] - \operatorname{dp}[k][v]}{N-k} $$

が求める長さである。ただし、$S$から到達できない頂点がある時にそのまま扱うと$\infty - \infty$という計算が起きてしまうので、$\operatorname{dp}[N][v] = \infty$の場合は除いて計算する。全部そう（＝$N$回目で到達できる頂点がない）なら閉路がないグラフなので$L = \infty$になるべきで、つじつまがあっている。

解説は「平均長が$L$以下のウォークが存在するか？」という判定問題を解いて二分探索する方針だった。判定問題は、すべての辺の重みから$L$を引いた時に$S$から$T$への長さ$0$以下のウォークが存在するかどうかで判定できて、これはやはりBellman-Fordで調べられる。