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%程度の上昇は見込めたので影響が皆無なわけではなかったが、この辺の知識がなさすぎて後回しにした結果、結局やらなかった。 ↩︎

AHC 002 A - Walking on Tiles

• 問題
• AC

とりあえず愚直ビームサーチを書いてみると盤面全体を移動できないうちに行き詰まってしまうことがわかる。

こういうのをどうするかという時に手札があまりなくて困るが、安直な対処として、全体を10x10マスの25個のブロックに区切ってブロックを頂点とするグラフでハミルトンパスをひとつ与えて（偶奇によってはハミルトンパスがなくて24ブロックしか渡れないが）それに沿うような経路を探索するというのはありそう。ベスト方針とは思えないので少しためらっていろいろ考えたが、他に大した案を思いつかないので実装した。

現在のブロックを$B_1$、次のブロックを$B_2$とするとき、$B_1$内では幅6000のビームサーチをする。移動先は$B_1$内のいずれかのマスか、$B_2$のマスで$B_1$に隣接しているもの（高々10個）に限る。後者は最高点の経路だけ保持する。$B_1$のビームサーチが終わったら$B_2$のマスで$B_1$に隣接しているものを始点に$B_2$のビームサーチを始める。これで$5.2 \times 10^6$点程度だった。もう少し考えると、$B_1$と$B_2$にまたがるタイルを取る/取らないで$B_2$における探索に影響があるので、それらの違いも考慮して経路を保持する（高々$10 \times 2^{10}$状態だが、平均的にはそれよりだいぶ小さい。) これで$5.3 \times 10^6$台に上がった。ビームサーチの幅を増やすと点はある程度上がるようだったので、最後の数十分は高速化をして幅8000のビームサーチが間に合うようにしたが、更新できなかった。

---

• 結果を見ると、2個程度のテストケースで25個のブロックを渡りきる前に行き詰まって終了しているようだ。そうなる可能性は認識していたけれど、seed=0から99まででは大丈夫だったので軽視していた。応急処置としては、時間があまりすぎていたらもう一回別のハミルトンパスで探索する等は思いつくが……
  • コンテストが終わったあとで調べていたが、そもそもどう動いても隣接ブロックに移れないか、移れる経路が極端に限られるような配置がたまにあるようだ。
• 最初の考察で、タイル毎に取るほうを決め打つと普通の最長経路問題になるなと思ってしばらく考えていたが、それを利用する方針は思いつかず。
• 経路を一部破壊してからつなぎなおす方針で上位に入っている人がけっこういるようだ。これも考えたけれど、4時間で詰められると思えなかったので捨ててしまった。

ABC 199 E - Permutation

• 問題

$\operatorname{dp}[S] :=$集合$S$に含まれる整数を数列の先頭$|S|$箇所に（制約を満たすように）配置する場合の数、としてDPできる。$S$に整数$t$を追加して$S \cup \{t\}$に遷移する時、制約は$X_i=|S|+1$であるようなものだけ調べればよい。

また、状態を入れ換えて$\operatorname{dp}[S] :=$集合$S$に含まれる位置に整数$1, 2, ..., |S|$を配置する場合の数、としてもDPできる。この場合は$|S|$に位置$t$を追加して$S \cup \{t\}$に遷移する時、制約は$Y_i = |S|+1$であるようなものだけ調べればよい。

前者と後者は同じ形の遷移になっていて、一方を書いて入力の$X$と$Y$の順番を「間違える」ともう一方になって同じ答えがでる。これらの数えているものは、数列を置換とみなしたときに逆置換で一対一対応している。

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

• 提出

リアルタイム受験した。O以外を通して94点だった。今回は前半の複数の問題にはまってしまって、辛うじてエキスパートという結果だった。

G - 一日一歩

素直に考えると最短経路問題を解けばよくて、通りたい道の直近で通れる日はRMQ上の二分探索で突き止められるが、Gでそんなことする必要がある？ と悩んで時間を消費した。結局、最初に考えた通りに実装した。

H - カンカンマート

$T$の値によって2列にわけてどちらも昇順ソートして、$T=0$をできるだけ取るような構成にしてから$T=1$をひとつひとつ増やしていけばよい……のだが、それが見えずに三分探索などをして時間をかなり消費した。

L - 都市計画

道路の端点がタワーか環状交差点上になければならないという条件を見落としていて、解ける問題に見えなくて困っていた。

M - 等しい数

似た問題をCodeChefで解いたことがあったにも関わらず、長時間はまった。CodeChefの問題は平方分割で解いたのだが、実装が大変だった記憶があるし、この問題のほうがハッシュテーブルへのアクセスが多くなりそうだし、制約も厳しいし、ということで平衡二分木で解くことにした……のだが、複数箇所でバグらせてしまった。

区間を平衡二分木で管理するやつを改造して使うことにして、手持ちのものはmapではない（区間に対応する値がない）ので、区間$[l, r)$に入っている値は別に用意した配列の位置$l$に保持することにしたのだが、それが間違いだったかもしれない。区間の分割・消去・挿入などの操作間で、区間に入っている値を正しく保つための処理が複雑になってしまって、手におえなくなるところだった。

N - 活動

順番を固定できればラッキーと思って調べると、$a_i/b_i$の降順でソートしてよいことがわかるのでソートしてDPする。（しかし、最後の活動の取り方を素朴なDPで正しく扱えているのか自信がなかった。）

O - 最短距離クエリ

先に開いて少し考えたがわからなかった。似た設定の問題としてUTPC 2011 - 巡回セールスマン問題があったのを思い出したが、そもそもこれも解けていなかった。

ABC 198 F - Cube

• 問題
• AC

サイコロが手元にあったので、回しながら考えた。まずはバーンサイドの補題を思い出す:

• 群$G$が集合$X$に作用するとする。この時、作用に関する同値類の総数は次の数に等しい:

$$\frac{1}{|G|}\sum _{g\in G}|F_g|$$

• ただし、$F_g$は$g$のfix、つまり$F_g=\{x\in X|g(x)=x\}$。

したがって、正六面体に対する回転操作で回転前と回転後が重なるものを列挙して、各回転に関するfixの大きさを求めればよい。正六面体に対する回転を分類すると以下の通り:

• $\mathrm{id}$: 恒等変換、つまり何もしない。1通り。
• $\alpha$: ある面の中心$A$と向かいにある面の中心$B$を結ぶ直線を軸に$90\mathrm{°}$回転する。どちら向きに回転するか述べていないが、ベクトルとみなして反時計回りに回転するとすると、$AB$と$BA$で別の回転になって$3\times 2=6$通りある。
• ${\alpha }^2$: ある面の中心$A$と向かいにある面の中心$B$を結ぶ直線を軸に$180\mathrm{°}$回転する。3通り。
• $\beta$: ある辺の中心$A$と向かいにある辺の中心$B$を結ぶ直線を軸に$180\mathrm{°}$回転する。辺対が6ペアあるので6通り。
• $\gamma$: ある頂点$A$と向かいにある頂点$B$を結ぶ直線を軸に$120\mathrm{°}$回転する。頂点対が$4$ペアあって、やはり回転する方向が2通りあるので$4\times 2=8$通り。

合わせて24通りあるので、fixの大きさを求めて全部足して24で割ればよいことになる。上の回転によってどの面とどの面が重なるかを調べると、以下の数え上げをすればよいことがわかる:

• $\mathrm{id}$: $x_1+x_2+x_3+x_4+x_5+x_6=S$の正整数解の総数を求めることに等しい。
• $\alpha$: $x_1+x_2+4x_3=S$の正整数解の総数を求めることに等しい。
• ${\alpha }^2$: $x_1+x_2+2x_3+2x_4=S$の正整数解の総数を求めることに等しい。
• $\beta$: $2x_1+2x_2+2x_3=S$の正整数解の総数を求めることに等しい。
• $\gamma$: $3x_1+3x_2=S$の正整数解の総数を求めることに等しい。

$\mathrm{id},\beta ,\gamma$は単純な重複組み合わせに帰着するが、$\alpha ,{\alpha }^2$がやや面倒に見える。

たとえば$\alpha$に関しては$1/(1-z{)}^2(1-z^4)$の$z^{S-6}$の係数を求めることに等しく、$1/(1-z{)}^2=\sum (\genfrac{}{}{0ex}{}{i+1}{i})z^i$（負の二項定理）を利用して$1+z^4+z^8+...$と掛けたときにどうなるか考えればよい。（自分は計算をバグらせてWolframAlphaに頼った） → $x_3$を決め打つと$x_1+x_2=S-4x_3$の正整数解が$S-4x_3-1$個だから、$\sum _{x=1}(S-4x-1)$を非負の範囲で計算すればいいのか。難しく考えてしまった。

---

見て何をすればよいかはわかったが、WolframAlphaがなければコンテスト中にはACできていなかった。結局は計算力なんだよな。

$mod6$で多項式になりそうなのでラグランジュ補間、というのを見てなるほどと思った。とはいえ小さいケースをちゃんと求めるのにもある程度の考察は必要か。

https://q.c.titech.ac.jp/docs/progs/polynomial_division.html
そもそも母関数が書けた時点で貼るだけになるらしい。というか、これを知らなくても漸化式に直して行列累乗はできるのでそれは考えるべきだった。