狠狠撸

～シチュエーション別～
Perlでちょいモテアルゴリズム

2012/01/27 Livedoor DeNA 合同勉強会
萬野有生 @DeNA id: mandy_44

Case1:
「運命の人なら誕生日くらい当て
られるよね！？9回で当てられ
ないと???(*?ω｀*)」

Case1:
「運命の人なら誕生日くらい当て
られるよね！？9回で当てられ
ないと???(*?ω｀*)」

電波ですか？a(°Д°ill

彼女の誕生日を9回以内に当てよ！
ただしはずれると彼女は誕生日が
それより後か前か教えてくれる。

1/1 1/2 ??? 6/30 7/1 7/2 ??? 12/30 12/31

7/1 7/2 ??? 9/30 10/1 10/2 ??? 12/30 12/31

7/1 7/2 ??? 8/14 8/15 8/16 ??? 9/29 9/30

#!/usr/bin/perl

use strict;
use warnings;
中間値を取ってきてその
my $MAX_LOOP = 9;
前後どちらにあるか判定
my $doy = 250; # 9/7
my ($min $max) = (0, 365);

my $ans;
for (1..$MAX_LOOP) {
計算量はO(log2n)
????my $mid = int(($min+$max)/2);

????if ($mid == $doy) {
????????$ans = $mid; 並列N分探索は強力
????????last;
????}
????elsif($mid > $doy) {
????????$max = $mid;
????}
????else {
????????$min = $mid;
????}
}

print "ans: ", $ans, "n";

#!/usr/bin/perl

use strict;
use warnings;
中間値を取ってきてその
my $MAX_LOOP = 9;
前後どちらにあるか判定
my $doy = 250; # 9/7
my ($min $max) = (0, 365);

my $ans;
for (1..$MAX_LOOP) {
計算量はO(log2n)
????my $mid = int(($min+$max)/2);

????if ($mid == $doy) {
????????$ans = $mid; 並列N分探索は強力
????????last;
????}
????elsif($mid > $doy) {
????????$max = $mid;
????}
????else {
????????$min = $mid;
じわりじわりと攻めていく
????}
}


Case2:
「私、1日でなるべくいっぱい映画
を見たいの☆（ゝω?）v????」

Case2:
「私、1日でなるべくいっぱい映画
を見たいの☆（ゝω?）v????」

DVD借りようよ(；? ?)

n本の映画が上映されている。各映
画は時刻siに始まりeiに終了する。
できるだけ多くの映画を見たいと
き何本見ることができるか。
ただし途中入退場は出来ない。

2 4

1 3 5

時間

1.一番開始時間の早いものから見る
2.一番時間の短いものから見る
3.一番終了時間の早いものから見る

2 4

1 3 5

時間


今、その時点で一番○○なものを
選んでいく

2 4

1 3 5

時間


今、その時点で一番○○なものを
貪欲法
選んでいく

#!/usr/bin/perl

use strict;
use warnings;
終了時間でソート
# 映画のリスト
↓
my @movies = ([1,3], [2,5], [4,7], [6,9], [8,10]);
@movies = sort { $a->[1] <=> $b->[1] } @movies; 順番に今見ることが出来
my $ans = 0; るかを判定
my $end = 0; # 前回見た映画の終了時刻
↓
for my $movie (@movies) {
????if ($movie->[0] > $end) { 見れるものがあれば見る
????????$ans++;
????????$end = $movie->[1];
????}
} 計算量はO(n)

#!/usr/bin/perl

use strict;
use warnings;
終了時間でソート
# 映画のリスト
↓
my @movies = ([1,3], [2,5], [4,7], [6,9], [8,10]);
@movies = sort { $a->[1] <=> $b->[1] } @movies; 順番に今見ることが出来
my $ans = 0; るかを判定
my $end = 0; # 前回見た映画の終了時刻
↓
for my $movie (@movies) {
????if ($movie->[0] > $end) { 見れるものがあれば見る
????????$ans++;
????????$end = $movie->[1];
????}
} 計算量はO(n)

仕事も恋も貪欲さが大事

Case3:
「何でも食べていいんだよねっ？
何食べたら一番お腹いっぱいに
なるかなー?(? ?)」

Case3:
「何でも食べていいんだよねっ？
何食べたら一番お腹いっぱいに
なるかなー?(? ?)」

5万円まででお願いします
(ヽ ω`)

n種類の料理のリストがある。
各料理はpiの値段でviの量がある。
X万円以内で一番量が多くなる料理
の組み合わせを見つけよ。
※ただし料理は1種類につき1回し
か頼めない

颈番目の料理を食べるか食べないかで総当たり
→ 計算量はO(2^n)


i番目の料理を食べる、食べない、に分解

食べた時食べない時
X-pi円でi番目以外の料 X円でi番目以外の料理で
理で最も量を食べたい最も量を食べたい




動的計画法




動的計画法

一つ前や一つ後を考えたときに相似形が出てくる
ような問題はDPで解きやすい！

颈番目(颈=0～苍-1)までの料理を箩万円以内で食
べた時の量の最大値をdp[i+1][j]とおく

i→i+1とするときの遷移を考えると、以下の
漸化式が導ける

颈番目(颈=0～苍-1)までの料理を箩万円以内で食
べた時の量の最大値をdp[i+1][j]とおく

i→i+1とするときの遷移を考えると、以下の
漸化式が導ける

dp[i][j] (j < v[i])
dp[i+1][j] = max(dp[i][j], dp[i][j-p[i]]+v[i]) (それ以
外)

#!/usr/bin/perl

use strict;
use warnings;
use List::Util qw(max);

my $n = 4; 計算量はたかだかO(nX)
my @p = (2, 1, 3, 2);
my @v = (3, 2, 4, 2);
my $X = 5;

my @dp = ([0, 0, 0, 0, 0, 0]);
for my $i (0..$n-1) {
????for my $j (0..$X) {
????????if ($j < $p[$i]) {
????????????$dp[$i+1][$j] = $dp[$i][$j];
????????}
????????else {
????????????$dp[$i+1][$j]
????????????????= max($dp[$i][$j], $dp[$i][$j-$p[$i]] + $v[$i]);
????????}
????}
}

print "max_v: ", $dp[$n][$X], "n";

#!/usr/bin/perl

use strict;
use warnings;
use List::Util qw(max);

my $n = 4; 計算量はたかだかO(nX)
my @p = (2, 1, 3, 2);
my @v = (3, 2, 4, 2);
my $X = 5;

my @dp = ([0, 0, 0, 0, 0, 0]);
for my $i (0..$n-1) {
????for my $j (0..$X) {
????????if ($j < $p[$i]) {
????????????$dp[$i+1][$j] = $dp[$i][$j];
????????}
????????else {
????????????$dp[$i+1][$j]
????????????????= max($dp[$i][$j], $dp[$i][$j-$p[$i]] + $v[$i]);
????????}
????}
}

print "max_v: ", $dp[$n][$X], "n";

過去の思い出は大切に

Case4:
「今度の旅行楽しみだねー?でも
私最短距離で移動しないと怒っ
ちゃうぞっ(o≧▽?)o」

Case4:
「今度の旅行楽しみだねー?でも
私最短距離で移動しないと怒っ
ちゃうぞっ(o≧▽?)o」

新幹線で(ry (；? ｀)

n個の地点がある。
各地点間の道路の距離が与えられ
た時、地点iから地点jまでの最短経
路を求めよ。

３
2

9
8 10 4
1

11
12 この問題は左図のようなグラフで表される
7
5
（この場合は重み付き無向グラフ）
6

1.n以下の整数kを取る
2.(1～k) (i,j)のグラフを考える
3.この時のi,j間の最短経路をpi,jとする
4.このグラフに地点k+1を加える
5.この時のi,j間の最短経路は以下のどちらか

３
2

9
8 10 4
1

11
7
5
6


pi,jまたはpi,k+1+pk+1,j

３
2

9 ワーシャルフロイド
8 10 4
1

11
7
5
6


pi,jまたはpi,k+1+pk+1,j

#!/usr/bin/perl
$p[$i][$j]は、
use strict;
use warnings;
直通の道あり → ２点間の距離d
my $n = 12; 直通の道なし → （十分大きな数）
my ($s, $g) = (2, 5);
my @p = init_p(); $i == $j →0
for my $k (1..$n) { で初期化する
????for my $i (1..$n) {
????????for my $j (1..$n) {
????????????if ($p[$i][$k] + $p[$k][$j] < $p[$i][$j]) {
????????????????$p[$i][$j] = $p[$i][$k] + $p[$k][$j];
????????????}
????????}
????}
}

print "ans: ", $p[$s][$g], "n";
計算量はO(n^3)

#!/usr/bin/perl
$p[$i][$j]は、
use strict;
use warnings;
直通の道あり → ２点間の距離d
my $n = 12; 直通の道なし → （十分大きな数）
my ($s, $g) = (2, 5);
my @p = init_p(); $i == $j →0
for my $k (1..$n) { で初期化する
????for my $i (1..$n) {
????????for my $j (1..$n) {
????????????if ($p[$i][$k] + $p[$k][$j] < $p[$i][$j]) {
????????????????$p[$i][$j] = $p[$i][$k] + $p[$k][$j];
????????????}
????????}
????}
}

print "ans: ", $p[$s][$g], "n";
計算量はO(n^3)

ときには遠回りも必要(?)

Thank you very much for your attention.

狠狠撸

20120127 nhn

Recommended

More Related Content

What's hot (11)

Viewers also liked (6)

Similar to 20120127 nhn (11)

Recently uploaded (11)

20120127 nhn

Editor's Notes