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

解き方メモ 信頼性低

SRM400代のHardで使ったものを見てみる。最初は全部記事書こうかと思ったがめんどくさくてやめた。

桁落ち誤差回避

ほとんど等しい2つの数を引き算すると、有効桁数が減少する。
式変形をして引き算をなくしたりする必要がある。
SRM 400 DIV1 Hard CollectingBonusesではさらにlog1p関数を使ったりする。

凸多角形は上部と下部に分割できる

左・右でも同じ。
それぞれの折れ線がy座標の関数と見た時に凸・凹となることが重要。
SRM 401 DIV1 Hard NCoolでは、それを利用して多角形内の点を列挙している。
"SRM 493 DIV1 Hard AmoebaDivOne"でも凸多角形を生成するDPでこの性質を大いに使っている。

集合を求める時に順番が関係ないことを利用して、フラグで持たずにそのフラグが立っている数で持ったりする

一般的なテクニック。あえて言及するほどでもないかもしれない。
数値の辞書順最小を求めたい時には必ず桁数が単調なことを利用して数値が終わったかどうかをΘ(数値の数)の状態で持てる。SRM 403 DIV1 Hard TheLuckySumで言っているが、実際にはこの問題では桁ごとにも数値の順番を入れ替えられるので、辞書順最小ということはあまり関係ない。

変数を1つ以外固定して近づけてくサーチ

"SRM 405 DIV1 Hard ReasonableOdds"で用いられる。
一般にベクトル引数の最適化の手法としてあるものだと思う。名前知らない。

��_{x=0}^[n-1} floor((a*x+b)/m) をO(log m)で

やばいアルゴリズム。
SRM 410 DIV1 Hard WifiPlanetの最重要部分。
応用は多そう。実際に全く別の問題SRM 406 DIV1 Hard ShortPathsでも使えて、漸近的な計算量を減らすことが出来る(と思う)。

凸とは限らない多角形内の何かを符号付き面積みたいに

SRM 410 DIV1 Hard WifiPlanetの1つ目のテクニック。
構造の差分上でのk番目クエリに対応しているデータ構造なら多角形内のk番目クエリにも使える気がする。

平面で領域が2色に分かれているとき、その両方のそれぞれを頂点として隣接を辺とすると木になる(？)

"SRM 411 DIV1 Hard MinimumTours"で使われる。
なんというか自明でないと思う。実際自分は解法を見た時驚いた。上の記述で合っているかどうかもわからない。
もし上の記述や理解が合っているなら応用性はかなりあると思う。

有理数上でもLCM,GCDが定義できる

"SRM 414 DIV1 Hard KPlanetaryAlignment"の肝。
"lcm(x/y,z/w) = lcm(x,z)/gcd(y,w)"。
整数上と同じく、周期を考える時に用いることが出来る。

重み付き数え上げのアルゴリズムで確率を求める(？)

"SRM 425 DIV1 Hard RoadsOfKingdom"の別解としてやばいアルゴリズムが存在する。
この問題は辺が存在する確率が与えられる時、全域木ができる確率を求める。
全域木はMatrix-tree theoremで数え上げられる。また、多重辺と考えれば重み付きバージョンもできる。
しかしそのアルゴリズムで確率が求められるというのだ。
辺がある確率をpとしたとき、重みをp/(1-p)に設定する。それで求めた後、(1-p)の総乗をかける。するとなんと確率が出るというのだ！
p=1の場合が0割りだが、特別扱いして連結成分を1つの頂点として適切にサイクルをチェックしたりしてもよいし、p=1-1e-10とするという方法もある。
なんでこれで求められるのかわかってないが、もしこれが一般的に適用できるのであれば応用は広がる。
determinantに限っても例えば有向木とかオイラー路とか平面グラフの完全マッチングなどがあるが…"もし"適用できたら面白いなあ。

Warshall-Floydで不等式を解く

うまくできる。あんまりわかってない。
"SRM 426 DIV1 Hard LongStraightRoad"や、最近では"SRM 586 DIV1 Medium History"で出されている。
SRM586ではみんな解いてるようなので、いまや常識らしい。

分割数の小ささ

分割数は指数オーダーだが、小さな方ではそれなりに小さい。だいたい(13^√n)/7n 程度。
「x個を順番関係なくいくつかに分割する」が分割数。
"SRM 427 DIV1 Hard PSequence"ではDPの状態として出た。一見制約が30で階乗オーダー・指数オーダーの解法は無理そうだが、実際の数は関係なく前の数と等しいかどうかだけを持てばいいことを利用すると分割数で抑えられて(Σ_{i=0}^30 p(i) = 28629)なので十分いける。

辞書順ペアをコストにする

"SRM 433 DIV1 Hard BarbarianInvasion"で最小カットとして出た。
最近では"Maximum-Cup 2013 - F 3人の騎士と1匹の犬"で重みつき二部マッチングの最小費用流として出た。

巡回する <-> 文字列としての2乗を考える

極めて典型的。

長くなったので分割。part2