燃やす埋める問題 Very Easy

診断人(@nico_shindannin)
1









1. Project Selection Problemとは
2. 基本
3. 制約条件を入れる
4. 選択肢をうまく並べる
ーーーー
5. 二部グラフの性質を生かす
6. 複雑な制約条件を入れる
7. 最小カットの復元をする
8. 費用を工夫して割り当てる
2
3
燃やす埋める問題
引用:Komakiさんのページ
http://topcoder.g.hatena.ne.jp/CKomaki/20121019/1350663591

A,B,Cは「燃やす」か「土に埋める」必要がある。
◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。
◦ A,B,Cは「土に埋める」と100円もらえる。
◦ BとCの片方だけ「燃やす」と死ぬ。

死なずに最高で何円もらえるか？
4
Dual Core CPU
引用:POJ No.3469 （プログラミングコンテストチャレンジブック P212）
http://poj.org/problem?id=3469

N個のモジュールを、コアAかコアBで実行する。
◦ モジュールiをコアAで実行すると、コストがAiかかる
◦ モジュールiをコアBで実行すると、コストがBiかかる

M個のモジュールの組(ak,bk)はデータ交換を行う
◦ もし、akとbkを異なるコアで実行した場合、wkのコスト
がさらにかかる。


コストの和の最小値を求めなさい。
1≦N≦20000, 1≦ M ≦200000
5

複数の小問題（Project)がある
◦ それぞれの小問題に対し選択肢(Selection)がある
◦ 選択肢ごとに、費用・利益がある

選択肢同士に依存関係もありうる
◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。
◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として
費用がかかる。

全体の費用を最小化（利益を最大化）する
6

複数の小問題(20問以下) がある。
◦ それぞれの小問題に対し選択肢(Selection)がある
◦ 選択肢ごとに、費用・利益がある

選択肢同士に依存関係もありうる
◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。
◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として
費用がかかる。

全体の費用を最小化（利益を最大化）する

これなら総当たりで解けます


計算量は20*220
しかし、問題が増えるとO(n*2 n)なので解けない。
7

複数の小問題(Project) がある。
◦ それぞれの小問題に対し選択肢(Selection)がある
◦ 選択肢ごとに、費用・利益がある

選択肢同士に依存関係もありうる
◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。
◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として
費用がかかる。



全体の費用を最小化（利益を最大化）する
これなら、小問題ごとに独立しているので
それぞれの小問題の費用を最小化して足せばいい。
しかし、依存関係があると全体の費用を最小化
できない
8

複数の小問題(10000問とか)がある
◦ それぞれの小問題に対し選択肢(Selection)がある
◦ 選択肢ごとに、費用・利益がある

選択肢同士に依存関係もありうる
◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。
◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として
費用がかかる。

全体の費用を最小化（利益を最大化）する
これを最小カットで解きます。
9
10
燃やす埋める問題 Super Easy

A,B,Cは「燃やす」か「土に埋める」必要がある。
◦ A,B,Cは「燃やす」とそれぞれ50,60,130円かかる。
◦ A,B,Cは「土に埋める」と100円かかる。

最小で何円かかるか？
11
燃やす埋める問題 Super Easy

A,B,Cは「燃やす」か「土に埋める」必要がある。
◦ A,B,Cは「燃やす」とそれぞれ50,60,130円かかる。
◦ A,B,Cは「土に埋める」と100円かかる。

最小で何円かかるか？

それぞれ、金額の安い選択肢を選べばよい。
◦ Aを「燃やす」Bを「燃やす」Cを「土に埋める」
◦ 50+60+100=210円が最小
12
燃やす
A
50
s
燃やす
60
B
燃やす
130
土に埋める
100
土に埋める
100
t
土に埋める
100
C

頂点sから頂点tへ辺をつなげる。
◦ 小問題ごとに並列につなげる
◦ 選択肢は直列につなげる
13
燃やす
A
50
s
燃やす
60
B
燃やす
130
土に埋める
100
土に埋める
100
t
土に埋める
100
C

最小s-tカットは、このようになる。
◦ 最小で50+60+100=210でs→tがつながらなくなる。
◦ カット（赤い線）した部分が、小問題の選択肢になる。
14
燃やす
A
50
s
燃やす
60
B
燃やす
130
土に埋める
100
土に埋める
100
t
土に埋める
100
C

最小s-tカットは、このようになる。
◦ 最小で50+60+100=210でs→tがつながらなくなる。
◦ カットした部分が、小問題の選択肢になる。
15





s-tカットなので、t->sは無視してよい
有向グラフです
切るところは、平面図的につながってなくてよい
s側とt側の２つに切る。3つ切ってはいけない。
元のグラフはs->tへの経路が存在する必要がある
16
A
50/50
s
60/60
B
100/130
流量/容量
50/100
60/100
t
100/100
C


最小カットをプログラムで計算するのは困難
最小s-tカット＝最大s-tフロー
◦ 最小カットの各辺のコストが、最大フローの容量になる
最大フローを求めるのにはDinic法を使う
 O(EV2)だが、実際はもっと速いので、おすすめ
17
燃やす埋める問題 Very Easy

A,B,Cは「燃やす」か「土に埋める」必要がある。
◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。
◦ A,B,Cは「土に埋める」と100円もらえる。

最大で何円もらえるか？
18
燃やす埋める問題 Very Easy

A,B,Cは「燃やす」か「土に埋める」必要がある。
◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。
◦ A,B,Cは「土に埋める」と100円もらえる。



最大で何円もらえるか？
最小カットは、最小値を求める。最大値ではない。
そこで、最小値を求める問題に置き換える！
19
燃やす
土に埋める
A
50円の利益
100円の利益
B
60円の利益
100円の利益
C
130円の利益
100円の利益
無条件で得られる利益
燃やす
土に埋める
A
100円の利益
50円の損失
0円の損失
B
100円の利益
40円の損失
0円の損失
C
130円の利益
0円の損失
30円の損失

利益が大きい選択肢の利益を、無条件で得られるこ
とにする→その分選択肢からひくと全て損失に
20

燃やす
土に埋める
A
50円の利益
100円の利益
B
60円の利益
100円の利益
C
130円の利益
100円の利益
燃やす
土に埋める
A
-50円の損失
-100円の損失
B
-60円の損失
-100円の損失
C
-130円の損失
-100円の損失
これはダメ！
◦ 負辺があるときの最小カット問題はNP困難
21
燃やす
A
50
s
燃やす
40
B
燃やす
0
土に埋める
0
土に埋める
0
t
土に埋める
30
C



最小s-tカットは0+0+0=0
あらかじめ貰える利益は100+100+130=330
求める最大値は330-0=330
燃やす
A
50
s
燃やす
40
B
燃やす
0
土に埋める
0
土に埋める
0
t
土に埋める
30
C

コスト0の辺もグラフに書きましょう！
◦ 最小カット問題のグラフでは、
辺が元からないのと、損失0の辺とでは、別物です。
◦ 最大フローを求めるときに、容量0になるのでいらない辺に
なりますが、それでも書きましょう
◦ 複雑な問題だと、辺が元からないのか、コスト辺が0なのか
で、混乱しやすくなる。
燃やす埋める問題 Easy

A,Bは「燃やす」か「土に埋める」必要がある。
◦ A,Bは「燃やす」とそれぞれ20,100円かかる。
◦ A,Bは「土に埋める」とそれぞれ50,20円かかる。
◦ Aを燃やしたときに、Bを土に埋めると罰金300円かかる。

最小で何円かかるか？
24
燃やす
20
s
A
燃やす
100
土に埋める
50
土に埋める
20
t
B

Aを燃やしたときにBを土に埋めると
罰金300円かかる
25
燃やす
20
s
A
燃やす
100
土に埋める
50
土に埋める
20
t
B


Aを燃やしたときにBを土に埋めると
罰金300円かかる
Aを燃やしたときにBを土に埋めたら
まだs-tカットが成立しないようにする
26
燃やす
20
s
土に埋める
50
A
罰金
300
燃やす
100
土に埋める
20
t
B


Aを燃やしたときにBを土に埋めると
罰金300円かかる
Aを燃やしたときにBを土に埋めたら
まだs-tカットが成立しないようにする
27
燃やす
20
s
土に埋める
50
A
罰金
300
燃やす
100
土に埋める
20
t
B



こうすると、s-tカットするにはB→Aの辺をカッ
トせざるをえない。つまり300円かかる。
もちろん、これは最小カットではない。
この制約条件の追加方法を理解できないと
その後すべて理解できなくなるので注意！
28

Wikipediaのほうで。
29
30
燃やす
A
50
s
土に埋める
100
B
燃やす
130
土に埋める
100
燃やす
60
t
土に埋める
100
C

選択肢はどういう順番に置いてもよい。
◦ ただ、順番が悪いと、制約条件を追加できないことが
ある。

考えて選択肢の順番を決めないといけない。
31
FoxAndGo3
引用:TopCoder SRM594 Div1 Medium
http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=1
5706




囲碁っぽい問題。自分が黒番で好きなだけ黒石を
置ける。（死ぬ場所にも置けるので注意）
黒石で白石のまわりを隙間なく囲めば白石を除い
て領地（＝空きマス）にすることができる。
領地の最大値を求めよ。
盤面の数は最大で50*50。また、白石同士は隣接
していない。
32

そのまま置かなければ、領地は24
◦ 本物の囲碁と違います
33

黒石を置けば、白石がとれるけど、置いた分だけ
領地が21に減る。何もおかないほうが領地が24
で最大。
34

このままでは領地は１
35

黒石を真ん中に置くと、すべての白石が死に、自
分の領地になる。領地は4、これが最大値。
36

初期の領地は10ですが、黒をうまく置くと、
最大領地は12になるようです。
37

最大値を求める問題なので、このままでは
最小カットが使えない。
◦ 黒石が最初からおいてあるところは絶対領地にできない
◦ つまり、仮の最大領地数=盤面の全マスー黒石数
◦ そこから逆に以下のように考える
 白石がとれなかったら、領地1の損失
 領地（空きマス）で黒石をおいたら、領地１の損失
◦ 仮の最大領地数ー最小の領地損失＝最大の領地数で求め
ることができる。
38
黒置く
1
s
白のまま
1
黒置く
1



領地
0
白死領地
0
t
領地
0
黒石は無視してよい。選択肢がないから。
領地を1の損失と考えたこのグラフは正しい。
「白死領地にするには、まわりに黒を置かない
といけない」の制約をどうするか？
39
黒置く
1
s
白のまま
1
黒置く
1
この２つを強制的に切らせたい
領地
0
白死領地
0
領地
0
t
領地
0
黒置く
1
+∞
s
白のまま
1
黒置く
1
+∞
白死領地
0
領地
0
t
領地
0
黒置く
1
+∞
s
白のまま
1
黒置く
1


+∞
白死領地
0
t
領地
0
+∞の制約条件を入れても、最小カットが成立
してしまう。「黒置く」のところを強制的に
カットさせたいのにできない。
+∞のリンクを逆にしても、同じ。
領地
0
s
白のまま
1
領地
0

黒置く
1
白死領地
0
t
黒置く
1
「黒置く」と「領地」の選択肢の順番を変える
43
黒置く
1
領地
0
+∞
s
白のまま
1
領地
0

+∞
白死領地
0
t
黒置く
1
+∞の辺を白から領地の方向へ足す
44
黒置く
1
領地
0
+∞
s
白のまま
1
領地
0

+∞
白死領地
0
t
黒置く
1
こうすると、領地のところをカットしても、
まだs-tは繋がっている
45
黒置く
1
領地
0
+∞
s
白のまま
1
領地
0

+∞
白死領地
0
t
黒置く
1
仮に隣接する１カ所をカットしても
まだs-tは繋がっている
46
黒置く
1
領地
0
+∞
s
白のまま
1
領地
0


+∞
白死領地
0
t
黒置く
1
つまり、白の隣接する領地は、すべて「黒置
く」を選ばないと、s-tカットできない。
「白死領地にするには、まわりに黒を置かない
といけない」の制約通りになってる。
47
黒置く
1
領地
0
+∞
s
白のまま
1
領地
0


+∞
白死領地
0
t
黒置く
1
うっかり+∞の辺を領地から隣接する白方向に
足すと、うまくいかない。
上の例で、「黒置く」をカットしなくても、s-t
カットができている。
48
FoxAndGo3
引用:TopCoder SRM594 Div1 Medium
http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=1
5706




囲碁っぽい問題。自分が黒番で好きなだけ黒石を
置ける。（死ぬ場所にも置けるので注意）
黒石で白石のまわりを隙間なく囲めば白石を除い
て領地（＝空きマス）にすることができる。
領地の最大値を求めよ。
盤面の数は最大で50*50。また、白石同士は隣接
していない。←この条件は意味ある？
49

もう気づいている方もいるかもしれませんが、
次の章にいけばわかります。
50
51
The Year of Code Jam
引用:Google Code Jam World Finals 2008 E
（プログラミングコンテストチャレンジブック P357）
https://code.google.com/codejam/contest/32011/dashboard#s=p4

カレンダーN月で、各月はM日。
◦ 白：コンテストが開かれない日
◦ 青：コンテストに参加する日
◦ ？：コンテストが開かれるが、参加しようか迷っている日

１つのコンテストに参加すると
◦ 幸福度の初期値は4
◦ カレンダー上で隣接する日に参加するコンテスト1つにつき幸
福度は1下がる


幸福度の最大値を求めなさい。
1≦N≦50, 1≦M≦50
52
53
Surrounding Game
引用:TopCoder - SRM558 Div1 Hard
https://code.google.com/codejam/contest/32011/dashboard#s=p4

長方形の盤面（最大20マス*20マス）があり、す
べてのマスに利益と費用が割り当てられている。
◦ マスに石を置くか、全ての隣接するマスに石を置くと、
利益が得られる。
◦ マスに石を置くと、費用がかかる

スコア＝全利益-全費用とする。スコアを最大化
せよ。
54
55
1
引用: 立命館合宿2013 Day2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2496
http://www.slideshare.net/oupc /h1-17155052

長さnのビット列がある．
◦ 左からi番目のビットが1のとき，スコアをai点得られる．
◦ 左からi番目のビットを中心に距離w以内にある1の個数
(=|{j∈{1,…,n}∩{i-w,…,i+w}|左からj番目のビットが1}|)
が奇数のとき，スコアをbi点得られる．

スコアを最も多く得られるようなビット列を求め
よ．
56
57
RabbitWorking
引用: SRM 542 Div1 Hard
http://community.topcoder.com/stat?c=problem_statement&pm=11054&rd=1
4734


N匹（N≦50）のうさぎの集団がいる。
うさぎの集団から何匹かを選ぶ
◦ 利益の合計Pは、選んだウサギの集団、すべてのペア利
益pikの総和で求められる(0≦pik≦9)
◦ 費用Cは、C=K(200-K)で求められる。Kは選んだうさぎ
の数

効率P/Cを最大化せよ（効率は実数）
58

Download Report