ちょっとしない解き方メモ色々 part2

解き方メモ 信頼性低

part1

フィボナッチ数の小ささ

fib(n)は指数オーダーで結構大きいが、2^nよりは全然小さい。
"SRM 451 DIV1 Hard BrickPuzzle"は列DPを特定の形のブロックでするもの。ブロックの形が、下側が絶対2つ単位で隣接しているため、そのような形の状態しか覚えなくてよい。このような状態の数はfib(n+1)になる(漸化式を見ればわかる)。2^nでは大きすぎるが、fib(n+1)はギリギリ小さいため解ける。実際にはMLEにならないために状態にインデックスを付ける必要がある。

コストで直接辞書順最小を求める

part1で紹介した"辞書順ペアをコストにする"のさらなる一般化。大事なのは、計算量は漸近的には変わらない(たぶん)が、ビット並列化のようなことで高速化できるということ。
"SRM 457 DIV1 Hard TheSquareDivOne"では普通にやってはギリギリ時間に間に合わない(実際には定数倍高速化を頑張れば通る)が、これを利用することで余裕を持って通すことができる。自分は実装に固定長の多倍長整数のようなものを使ったが、「先頭から整数に収まる範囲だけやり、それを固定して次の範囲へ」というように普通の辞書順greedyとのハイブリッドにやることでもできる。
また、自作の問題"最初のコンテスト - E 辞書順最大の経路履歴"(問題文)でも同じようなテクニックが適用出来る。この場合はダイクストラ法の重みとして多倍長整数を採用する。なお、その問題はunion-find-deleteのようなもので解けるように思えるが(当時知らなかったし、今でもわかってない)…どうだろうか。

整数計画を分岐限定法で？

ヒューリスティックとかあまり実装しなくても、問題がうまくLPとフィットすれば解けるかも。
LPのboundが効率的に効くような問題では十分解けうる。変数の数が多かったりすると、ナイーブな実装ではMLEとなってしまうことが多いかもしれないので、変数の範囲はまあまああるが変数の数が少ないような問題がいいかもしれない。
"SRM 488 DIV1 Hard TheBoringGameDivOne"では何のヒューリスティクスも無しのプレーンの分岐限定法でも1ケース以外は通る。さらに、変数を割り当てる前にその範囲をLPで制限するようにしたら(これは何と呼ばれているのかわからない)全ケース通った。この問題は変数の数が9と少ない。また範囲も0〜1000と比較的少ない。しかし当然1000^9はできないわけだが、実際に解けた。
もっと実装すれば、もっと色々な問題が解けるかもしれない。解ける率を考えるとライブラリとしてそれなりのものを実装するのはありかもしれない。

浮動小数点数重みの最短路は誤差に注意

Dijkstra'sやFSPAなどは特に注意。誤差によって負サイクルができることがあり、負サイクルがあると無限ループしてしまうからだ。
最短路はそのままの形だけでなく、様々なアルゴリズムのサブルーチンとしても用いられることに注意する。特に多いのが最小費用流、特に重み付き2部マッチングである。
最小費用流のPrimal-Dualではポテンシャルを加減算する関係上誤差が大きくなりやすいように思える。
例として、"SRM 491 DIV1 Hard FoxCardGame"は浮動小数点数重み付き2部マッチングを使う。実際自分はこの無限ループのせいで1回Failしてしまった。
最小費用流のPrimal-Dualの場合、

Weight d = dist[i] + edgeCost + potential[i] - potential[j];
if(d < dist[j]) ...

のようになると思うが、これに1行足す。

Weight d = dist[i] + edgeCost + potential[i] - potential[j];
if(d < dist[i]) d = dist[i];	//*
if(d < dist[j]) ...

こうすることで解決できる。
Dijkstra'sでなく負辺も存在する場合はEPSを適切に使って比較すればよい。

サイズごとの総和で包除原理

包除原理の±はサイズによって決まる。つまり同じサイズの集合は全て同じ符号。
そのため、あるサイズの集合の総和を求めることができるなら包除原理ができる。
"SRM 498 DIV1 Hard FoxJumping"で使っている。この問題の場合はサイズごとの総和はsubset-sum数え上げのDPと二項係数などで求める。
包除原理といえば2^nかかると思ってnが大きい時できなそうだが、このようなやり方もあるということ。

Dijkstra's風で、単純な足し算以外の重み

Dijkstra'sは辺の重みを距離→距離の関数と考えたとき、その関数が広義単調増加なら正当(たぶん)。証明はしてないけどなんとなくそうっぽい？
普通の重みつき辺は重みが非負なら足し算関数はそれを満たすので正当であるといえる。
よくあるのは「ある時刻まで待つ」という重み。できるだけ早く行ったほうがいいのがわかる。
"SRM 479 DIV1 Medium TheAirTripDivOne"は周期的な区間を待つような形。これも明らかに広義単調増加なのでいけるといえる。
"SRM 462 DIV1 Hard WarTransportation"はmaxを取る。これも同様に正当性がいえる。

常識とか発想とか雑多な
  • 多項係数は二項係数のかけあわせになる。(n!/x_1!/x_2!/... = C(n,{x_1,x_2,...}) = C(n-��_{j=1..i-1}x_j,x_i))
  • 隣同士に限定してもswapが自由な回数できるなら任意の順列を作れる(たぶんどんなswapなら任意の順列ができるか、とか考えられるのかな？知らないけど)
  • longest common prefix → 辞書順ソートする。"SRM 496 DIV1 Hard YetAnotherHamiltonianPath"とか"SRM 330 DIV1 Medium PrefixFreeSubsets"とか。
  • (rank(s)+k)番目を辞書順で求めたくて、rank(s)がlong longに入りきらないほど大きい時はsandwich(s≦x≦tとなるxの数)で数を数えるルーチンを作れればいける。"SRM 467 DIV1 Hard NextHomogeneousStrings"。ただ多倍長でもいけそうだが。
  • 連結成分の集合をsubsetとして数えるときには(ab)(cd)と(abcd)を重複して数えないように、連結成分が区切られる時に最低でも1つスペースを開けないといけないようにすればいい。"SRM 421 DIV1 Hard "TeamManagement"は木上。
  • greedyは分岐がある時に「片方の選択肢だったら絶対良い解になる」という優先順位をいかにつけられるかがポイント。辞書順greedyはその点自明。"SRM 429 DIV1 Hard SpecificPolyominoCovering"。
  • 平面上の矩形とかのunionの面積を求めるのはline-sweep的にやればΘ(n log n)とかでできる。"SRM 441 DIV1 Hard PaperAndPaint"。
  • 行列の足し算とか。それでバイナリ法とか。"SRM 444 DIV1 Hard AvoidFour"。この問題の解法頭良くて好き。
  • modが小さいとき、modをとった後の値ごとに考える(それが同じなら同じなので)。"SRM DIV1 Hard IncreasingNumber"。
  • できるだけ対角線上いようとするようなメモ化再帰でO(n)。"SRM 454 DIV1 Hard MegaSum"。
  • 2部マッチングで絶対使わないといけない頂点があるときは、それ以外の頂点を(k-そのような頂点数)の容量の辺に通すようにして制限する(それが負になったら絶対無理)。2部マッチング以外にも一般に同じような考え「重要なものを絶対使う <-> 重要でない物の数を制限する」が使えるだろう。"SRM 459 DIV1 Hard TheContest"。
  • 常に前の状態に戻れて、その「前の状態」という状態遷移にサイクルが無いとわかるとき、森である。"SRM 463 DIV1 Hard RabbitPuzzle"。この問題のこの状態が森で、さらに無限で一様であるから区別する状態数が少ないという議論はとても面白かった。
  • (��_{i=1}^n x_i / n)以下の値x_jが必ず存在する。"SRM 468 DIV1 Hard MallSecurity"。
  • FPTの自明でないアルゴリズムであっても、DPなら柔軟性がある。"SRM 470 DIV1 Hard BuildingRoads"の解法は、steiner treeのDreyfus-Wagner algorithmの変形であるとみなせる。
  • "SRM 477 DIV1 Hard KingdomTour"のgreedyな、minimum cost flowのPrimal Dualにも似た謎アルゴリズム。practice roomの自分の解答(自分はzhuojie氏のものを参考にしたが、誰が最初に書いたかは知らない)参考。
  • Hyperplane separation theorem。2つの凸多角形が交差しないとき、それらを分割する直線が存在する(さらに多次元でも)。この直線はn^2試せば良いので、分割のし方もO(n^2)となる。"SRM 486 DIV1 Hard BatmanAndRobin"の肝。
  • グリッド上で各列で区間を決めるとき、それを領域として連結にするために区間の左と右を伸縮する順番を適切に決める。"SRM DIV1 Hard AmoebaDivOne"で綺麗に書けた。伸縮をインクリメンタルにやるDPで、縮める方を最初に縮めきってからもう片方をやれば、縮める方はもう片方より左右には縮まないので必ず連結にできるというテク。自分で思いついて、とても面白いと思った。