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で調べられる。

CODE FESTIVAL 2016 Grand Final D - Dice Game

• 問題
• AC

Petrの純粋戦略は$2$通り:

• 赤を選ぶ
• 青を選ぶ

touristの純粋戦略は$2^6=64$通り:

• どの目が出ても赤と答える。
• 2, 3, ..., 6が出たら赤と答え、1が出たら青と答える。
  ...
• どの目が出ても青と答える。

これらの混合戦略の中からお互いに最適戦略を取った時にtouristが勝つ確率を知りたい。

$a_{ij} =$ Petrが戦略$i$を取ってtouristが戦略$j$を取った時にtouristが勝つ確率、とすると行列$(a_{ij})$の見た目は

$$ \begin{bmatrix} 1 & 1-p_1 & 1-p_2 & 1-(p_1+p_2) & ... & 0 \\ 0 & q_1 & q_2 & q_1+q_2 & ... &1 \end{bmatrix}$$

となっている。touristの混合戦略を$(x_1, ..., x_{64})$で表すとき、touristは$a_{1, 1}x_1 + ... + a_{1, 64}x_{64}$と$a_{2, 1}x_1 + ... + a_{2, 64}x_{64}$の小さいほうを最大化したい。この問題は以下のLPになっている:

• $\textrm{maximize} \ z$
• $a_{1, 1}x_1 + ... + a_{1, 64}x_{64} \ge z$
• $a_{2, 1}x_1 + ... + a_{2, 64}x_{64} \ge z$
• $x_1+ ... + x_{64} = 1$
• $x_1, ... x_{64} \ge 0$

これは単体法などで解けるが、もう少し簡略化する。touristの戦略は「目$i$が出たら$y_i$の確率で赤を選ぶ」という形で表せる。Petrが赤、青を選んだ時にtouristが勝つ確率はそれぞれ$p_1y_1+...+p_6y_6$、$q_1(1-y_1)+...+q_6(1-y_6)$であり、touristはこれらの小さいほうを最大化したい。この問題は以下のように書ける。

• $\textrm{maximize} \ z$
• $p_1y_1+...+p_6y_6 \ge z$
• $q_1(1-y_1)+...+q_6(1-y_6) \ge z$
• $y_1, ..., y_6 \in [0, 1]$

これもLPだけれど、変数が少ないので非基底変数の組み合わせを総当たりするだけでもよさそう。

AHC 004 A - Alien's Genome Assembly

• 問題
• AC

$s_i$を盤面のどこかに上書きする遷移だけの焼きなましをした。

• 遷移の際のスコア更新について。変更に関わるそれぞれの行・列を（折り返しを考慮して）31文字の文字列とみなして、Aho-Corasickで$(s_i)$全体とマッチングした。マッチング結果は行・列ごとに長さ$M$のビット列に保持して、最後にすべてのビット列のORを取って立っているビットを数えた。
  • 最初は$(s_i)$中の同一文字列をまとめて1つ1つに重みを与えていたが、重み付きになると最後の「立っているビットを数える」部分でワードサイズ高速化ができなくなって逆に遅くなった。
• 縦に書く文字列と横に書く文字列を混在させようとするより、どちらかに絞ったほうがだいぶ得点効率がいいことに気づいたので、横に書くだけにした。
• 行にだけ文字列を書くとした上で、変更に関わるすべての列を遷移ごとにマッチすると、特に$(s_i)$の平均長が大きい場合に調べるべき列が多くなって重くなる。結果を見ていると、平均長が大きい入力は縦にマッチするパターンがほとんどないようなので、列に関するマッチを完全に無視することにした。具体的には6以上なら列は無視して、5以下は列のマッチも調べた。
  • 焼きなましの遷移回数は、前者が$2 \times 10^6$、後者が$4 \times 10^5$くらいだった。
• 盤面に存在しない$s_i$から乱択する遷移と$(s_i)$全体から乱択する遷移を入れていたが、前者がうまく高速化できずにボトルネックになっていたので、全体から乱択するだけにした。
  • 追記: もっと単純に、盤面に存在する$s_i$を引いたら何回かサンプルしなおす、でよかった。改善は+0.2%程度。
• 平均長が大きい入力は3秒使いきる前にどこかの山に収束してしまうようだったので、平均長が8以上の入力については多点スタートした。

振り返り

• prefixとsuffixが重なる2つの文字列を1つにすることで点を伸ばしている人が多数いるようだ。これは最初に考えたのだけど、具体的にどの文字とどの文字を連結するべきかを考える必要があるし、焼きなましと相反しないだろうと思って後回しにした結果、最後まで放置してしまった。雑な貪欲でもいいから試してみるべきだったな。

AHC 003 A - Shortest Path Queries

• 問題
• AC

最小二乗法による$H, V$の推定をベースにいろいろやった。辛うじて97%に達した。

M=1

とりあえず、$M=1$のケースしか来ないとして$H, V$を推定することを考える。報告されたパスの長さを$W$として、パスが行$i$を$r_i$回、列$j$を$c_j$回通るとする。このとき、$\sum_{i: 行}r_iH_i + \sum_{j: 列}c_jV_j$と$W$が近くなるように$(H_i), (V_j)$を選びたくて、これは最小二乗法(OLS)が使えそう。得点は正規化されているので$W$で割って、

$$ \Bigl (\frac{1}{W} \bigl(\sum_{i: 行}r(i)H_i + \sum_{j: 列}c(j)V_j \bigr) - 1 \Bigr)^2 $$

の総和を最小化することを目指す。OLSはクエリ数を$Q$、変数の数を$d$として${O}(Qd^2)$でできる。

• パスの重みなし長さ$l$が大きいと、$\delta, \gamma$の平均の分散（≒誤差の分散）が小さくなっていくはずなので、パスごとの誤差の分散を揃えるために重み付き（式に$\sqrt l$を掛ける）にしてみた。直接のスコアにはほぼ影響しなかったけれど、後述の$M$の判定にかなりよい影響があったので残した。（ただ、そうなる理由がよくわからない。）
• 特にクエリが少ないうちは多重共線性の問題があるので、OLSの行列の対角成分に微小な定数を足して正則にするやつ（リッジ回帰と呼ばれているもの）をした。
• 毎回OLSすると遅すぎるし、クエリが一定数を超えるとだいたい収束しているようだったので、クエリを150個処理するまでは毎回OLSし、それ以降は25回に1回にした。
• OLSは素朴な掃き出し法でやった。疎行列なのでもっと速い方法はあるらしいけれど、後半のOLSの頻度を上げてもほとんど得点に結びつかなかったので、コンテスト中は無視していた。

M=2

$M=2$の場合、$H, V$の値が行、列ごとに2種類あり、境界がわからないのでその推定もする必要がある。境界を決めつければ上と同様のやり方で$H, V$が推定できるので、その際のRMSEをスコアとして境界を探索する焼きなましは考えられる。ただ、素朴にやると1回のOLSが重すぎるという問題がある。そこで、ある一行$i$の境界を移動させたときのRMSEを最小化する問題を局所化して、$H_{i, 0}, H_{i, 1}$だけを推定する二変数の回帰と考えることにする。このOLSは${O}(クエリ数)$でできるので、焼きなましの遷移としては十分に速い。

• 最初のうちは多項式回帰や3分割、4分割のOLSも試したが、普通にやると収束が遅すぎてうまく扱えなかった。

Mの分類

$M$は与えられていないので推定する必要がある。クエリを150回処理するまでは$M=1$を想定したOLSをして、その時点でのRMSEを見て一定より大きければ$M=2$、とするだけで96%程度の正解率があるようだった。ほかにも相関のある指標はいくつかあったけれど、正解率100%でも総スコアに大きな影響はなかったので追求しなかった。^[1]

• もう少し精密に、10回目、20回目、30回目、...で$M=2$である確率が（例えば）98%以上になったら$M=2$の処理に移行する、みたいな考え方もありそうだったが、そもそも移行を早めても得点が上がらない（$M=2$の入力に対しても、最初はむしろ$M=1$向けのモデルを適用したほうが効率がよい）ようだった。

OLS以降

クエリ数が増えると、個別の辺の重みもある程度は推定できそうと思った。推定した$(H_i), (V_j)$をベースに、RMSEをスコアとして各辺の重みを変更する山登りをすると、$M=1, 2$ともに点が伸びた。

• 焼きなましで点が伸びなかったので、速度を重視して山登りにした。
• 素朴にやるとオーバーフィットするので、正則化（各辺の重みの$H, V$との差についてのRMSEも山登りのスコアに足す）を加えたりしたが、十分にコントロールできている気がしない。
• 通った回数の多い辺上位200個くらいを選んでOLS、も試したが山登りを超えられなかった。

振り返り

• 統計の知識がなさすぎるので、問題を見たときにけっこう困った。ただ、最初の印象に反して、素朴な回帰と局所探索を調整しているだけでまあまあスコアが伸びていった。
• Woodburyの恒等式でOLSの差分更新ができるらしい。確かにこういうものを探していた。
• 通った回数の少ない辺や行・列を少しだけ楽観的に評価したり、（使う行・列は少ないほうが質の高い情報が得られるので）最初のうちは方向転換にペナルティをつけたりするという工夫で点を伸ばしている人がかなりいるようだった。どの情報を得るかという観点を後半になって忘れてしまったのは反省点。
  • 前半のことを思い出すと、通ったことのない行・列を優先して通るようにすると多重共線性の問題が大きくなってむしろスコアが下がってしまうので捨てて、それ以降ほとんど考えなかったんだよな。

---

1. 0.03%程度の上昇は見込めたので影響が皆無なわけではなかったが、この辺の知識がなさすぎて後回しにした結果、結局やらなかった。 ↩︎