ゴミ箱

豊かな人生を歩みたい

Introduction to Contemporary Algorithms

www.youtube.com

岩間先生の講義が京都大学OCWで公開されていた.この先生の「アルゴリズム・サイエンス:出口からの超入門」が大好きなのでとても嬉しい.

以下は自分用の適当なメモ.

アルゴリズムの設計と解析に基本的な3つのテクニック

  1. 分割統治法

  2. 動的計画法

  3. バックトラック

分割統治法の例

  1. n個のコインからたった一つの偽物のコインを秤を使って見つける.

  2. 整数がn個並べられた数列(必ずしもソートされていない)からk番目に小さな整数を見つける.

    • O(n) で出来る.

    • T(n) = T(2/3 n) + T(1/5 n) という式の導き方がとても楽しい.

  3. 平面上のn点から最近接ペアを見つける.

    • 平面をある直線で半分に切るのは良い.その直線周りで近接している点を求める方法が賢い.

動的計画法の例

  1. n個の整数を,和の等しい二つの集合に分割する.ただしn個の整数はすべて0以上100以下とする.

    • 自明なO(2^n)のサーチから,適切にブランチをまとめることでO(n^2)になる.

    • 自明なサーチからdpのアイディアで何が変わるか?ということを強調する.

    • 整数に範囲の制限がない場合,O(2^(n/2)) で出来る.これをexponentail speedupsという.

  2. 行列の積の順序(順番)を最適化せよ

    • A, B, C の行列のサイズがまちまちな場合,行列の積:A*B*C(A*B)*Cと計算するかA*(B*C)と計算するかで計算量(ここでは必要な四則演算の数という意味)が異なる.

    • 適切にまとめると状態数はO(n^2)になるのでO(n^3)程度.

    • 全体の状態数はO(4^n)になる.カタラン数と関連.

バックトラックとローカルサーチ

  1. 3-SAT

    • バックトラックのアイディアで少し考えればT(n) = T(n-1) + T(n-2) + T(n-3)となる.

    • local search = random assignment + local improvement

    • 3-SATの有名な乱択アルゴリズムを実際に解析する.

黒魔術

Bit Twiddling Hacks

Bit Twiddling Hacks
色々ある基本的な操作を少ない命令数で実行できるような黒魔術を紹介しているページ. 面白そうなので少し読んでみる.

  • Compute the sign of an integer
    vはint(32bit)で,vが正なら0vが負なら-1の値を返すような計算をしたいとする.
    一つの方法は-(v < 0)のようにboolを得て,適当にintにキャストする.しかしこの方法には分岐(branching on CPUs with flag registers (IA32))が存在する.それを避けるには,(v >> 31)といっぱいいっぱい右にシフトして符号部分を取り出す.ただ,この方法はちょっと危険?らしく,unsigned intにキャストする方法も紹介してる.いずれにせよ補数表現を利用した賢いやり方だ.

  • Detect if two integers have opposite signs

bool f = ((x ^ y) < 0); // true iff x and y have opposite signs

愚直にやるとifだらけだし,x + yの符号を計算する方法だとオーバーフローが怖い.xorってなんだか速そうだし(知らない)オーバーフローの心配もないしとても賢い.

  • Compute the integer absolute value (abs) without branching
int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
// CHAR_BIT is the number of bits per byte (normally 8).
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;

分岐にコストのかかるCPUではこちらの方が早いんだろうな.maskvが正なら0,負なら-1をとるようになっている.仕組みは,>>-より優先度が低いのでvを31ビット右にシフトするんだけど,vが正なら符号部分が0なので0vが負なら符号部分が1なので-1(???).え,負の場合がよくわからん.
rの式はまあそのままなんだけど一応例は次の通り.32ビット書くのは面倒なので整数が4ビットで表現されているとした例になってる.-1する必要があるのは少しややこしいね.

v = -6 = 1010
mask = -1 = 1111
v+mask = -7 = 1001
(v+mask)^mask = (1001) ^ (1111) = 0110 = 6
  • Compute the minimum (min) or maximum (max) of two integers without branching
int x;  // we want to find the minimum of x and y
int y;   
int r;  // the result goes here 
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

x < yのときは-(x < y)-1なのですべてのビットが1になる,よって,r = y ^ ((x ^ y) & (-1)) = y ^ (x ^ y) = xとなる.
逆にx >= yのときは-(x ^ y)0なのでr = y ^ ((x ^ y) & 0) = y ^ 0 = yとなる.
maxを得る方法もほとんど同様だ.ここではquick and dirty versionというのも紹介していた.ideaはx - yの符号を利用するってやつなので結構ナイーブ.式中にx - yが2回出てくるけれどここはコンパイラアセンブラかが最適化して一度しか計算しなくて済むようにしてくれるのかな?

  • Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 
f = (v & (v - 1)) == 0;

2冪の数はある一つのビットだけが1なので,-1するとそのビットは0となり,そのビットより下位のビットがすべて1になる.よってその二つの&は0となる.また,2冪じゃなければ-1した時に変わらないビットが必ず存在するので&をとっても0にならない. ただし,上の式では0が2冪と判定されてしまう.それを修正したのが次の式.

f = v && !(v & (v - 1));

v = 0の場合はv &&によって0にしちゃえば良いのだった.

もっと読みたいしどんどん更新するつもりですが,今日はこの辺で.

AGC023B

メモ

ナイーブに考えると,どれだけ盤面をずらすかでO(N^2),ずらした盤面が対称的か判定するのにO(N^2)で,合計O(N^4)だけ計算する必要がある.
右にA,下にBだけずらした盤面をT(A,B)と書くことにする.
よく考えれば「T(A,B)が対称的⇔T(A+i,B+i)が対称的」が成立するので,盤面のずらし方はO(N)だけ探索すれば良い.
Submission #5312265 - AtCoder Grand Contest 023

感想

条件を満たす(この場合,条件は対称性)盤面の集合に備わる性質を見つければ一発だった.競プロに限らずこういうのは大事だよね.難しいけれど.

AGC031B

メモ

左からi番目の石の色をc[i],左からi番目までの石で色ぬりした場合の数をdp[i]とする.
iからi+1の遷移を考えると,dp[i+1]は「ji+1の間にある石を色c[i+1]で塗る(ただしc[j] = c[i+1], j < i+1)場合」と「何もしない場合」の和とわかる.前者の求め方を考えれば良い.
abの間にある石を色c[b]で塗る(ただしc[a] = c[b], a < b)」と何度も書くのは面倒なので,f(a,b)でこの文章を表すとする.
c[j] = c[k] = c[i+1], j < k < i+1という状況を考える.f(j,i+1) = f(j,k) + f(k,i+1)が成立する.この式よりf(j,i+1)をした状況は,左からk番目までの石で色塗りした場合にf(k,i+1)したという状態に包含される.よって,c[j] = c[i+1]なる最大のjとの間をf(j,i+1)した場合が求めたかったものとなる.そのようなjをaとすれば,次のような漸化式が得られる.
dp[i+1] = dp[i] + dp[a]
ただしc[i] == c[i+1]の場合はdp[i+1]=dp[i]である.あとは適当にdp[a]を記憶しておけば良い.
Submission #5301942 - AtCoder Grand Contest 031

感想

「色々な状況を想像できちゃうけど,結局直前のdp[a]に包含されてしまう」ってのは典型なんだろうけどほんと賢いねえ.