1.  1. Project Selection Problemとは  2. 基本  3. 制約条件を入れる  4. 選択肢をうまく並べる  ーーーー  5. 二部グラフの性質を生かす  6. 複雑な制約条件を入れる  7. 最小カットの復元をする.

Presentation on theme: "1.  1. Project Selection Problemとは  2. 基本  3. 制約条件を入れる  4. 選択肢をうまく並べる  ーーーー  5. 二部グラフの性質を生かす  6. 複雑な制約条件を入れる  7. 最小カットの復元をする."— Presentation transcript:

1 診断人(@nico_shindannin) 1

2  1. Project Selection Problemとは  2. 基本  3. 制約条件を入れる  4. 選択肢をうまく並べる  ーーーー  5. 二部グラフの性質を生かす  6. 複雑な制約条件を入れる  7. 最小カットの復元をする  8. 費用を工夫して割り当てる 2

3 3

4 燃やす埋める問題 引用: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の片方だけ「燃やす」と死ぬ。  死なずに最高で何円もらえるか？ 燃やす埋める問題 引用: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

5 Dual Core CPU 引用:POJ No.3469 （プログラミングコンテストチャレンジブック P212） http://poj.org/problem?id=3469  N個のモジュールを、コアAかコアBで実行する。 ◦ モジュールiをコアAで実行すると、コストがA i かかる ◦ モジュールiをコアBで実行すると、コストがB i かかる  M個のモジュールの組(a k,b k )はデータ交換を行う ◦ もし、a k とb k を異なるコアで実行した場合、w k のコスト がさらにかかる。  コストの和の最小値を求めなさい。  1≦N≦20000, 1≦ M ≦200000 Dual Core CPU 引用:POJ No.3469 （プログラミングコンテストチャレンジブック P212） http://poj.org/problem?id=3469  N個のモジュールを、コアAかコアBで実行する。 ◦ モジュールiをコアAで実行すると、コストがA i かかる ◦ モジュールiをコアBで実行すると、コストがB i かかる  M個のモジュールの組(a k,b k )はデータ交換を行う ◦ もし、a k とb k を異なるコアで実行した場合、w k のコスト がさらにかかる。  コストの和の最小値を求めなさい。  1≦N≦20000, 1≦ M ≦200000 5

6  複数の小問題（Project)がある ◦ それぞれの小問題に対し選択肢(Selection)がある ◦ 選択肢ごとに、費用・利益がある  選択肢同士に依存関係もありうる ◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。 ◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として 費用がかかる。  全体の費用を最小化（利益を最大化）する 6

7  複数の小問題(20問以下) がある。 ◦ それぞれの小問題に対し選択肢(Selection)がある ◦ 選択肢ごとに、費用・利益がある  選択肢同士に依存関係もありうる ◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。 ◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として 費用がかかる。  全体の費用を最小化（利益を最大化）する  これなら総当たりで解けます  計算量は20*2 20  しかし、問題が増えるとO(n*2 n )なので解けない。 7

8  複数の小問題(Project) がある。 ◦ それぞれの小問題に対し選択肢(Selection)がある ◦ 選択肢ごとに、費用・利益がある  選択肢同士に依存関係もありうる ◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。 ◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として 費用がかかる。  全体の費用を最小化（利益を最大化）する  これなら、小問題ごとに独立しているので それぞれの小問題の費用を最小化して足せばいい。  しかし、依存関係があると全体の費用を最小化 できない 8

9  複数の小問題(10000問とか)がある ◦ それぞれの小問題に対し選択肢(Selection)がある ◦ 選択肢ごとに、費用・利益がある  選択肢同士に依存関係もありうる ◦ 小問題1で選択肢Aを選んだら、小問題3でAは選べない。 ◦ 小問題1も小問題2でも選択肢Aを選んだ時は罰金として 費用がかかる。  全体の費用を最小化（利益を最大化）する これを最小カットで解きます。 9

10 10

11 11 燃やす埋める問題 Super Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円かかる。 ◦ A,B,Cは「土に埋める」と100円かかる。  最小で何円かかるか？ 燃やす埋める問題 Super Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円かかる。 ◦ A,B,Cは「土に埋める」と100円かかる。  最小で何円かかるか？

12 燃やす埋める問題 Super Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円かかる。 ◦ A,B,Cは「土に埋める」と100円かかる。  最小で何円かかるか？ 燃やす埋める問題 Super Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円かかる。 ◦ A,B,Cは「土に埋める」と100円かかる。  最小で何円かかるか？ 12  それぞれ、金額の安い選択肢を選べばよい。 ◦ Aを「燃やす」Bを「燃やす」Cを「土に埋める」 ◦ 50+60+100=210円が最小

13 13 s A B t C 50 60 130 100 燃やす 土に埋める  頂点sから頂点tへ辺をつなげる。 ◦ 小問題ごとに並列につなげる ◦ 選択肢は直列につなげる

14 14 s A B t C 50 60 130 100 燃やす 土に埋める  最小s-tカットは、このようになる。 ◦ 最小で50+60+100=210でs→tがつながらなくなる。 ◦ カット（赤い線）した部分が、小問題の選択肢になる。

15 15 s A B t C 50 60 130 100 燃やす 土に埋める  最小s-tカットは、このようになる。 ◦ 最小で50+60+100=210でs→tがつながらなくなる。 ◦ カットした部分が、小問題の選択肢になる。

16  s-tカットなので、t->sは無視してよい  有向グラフです  切るところは、平面図的につながってなくてよい  s側とt側の２つに切る。3つ切ってはいけない。  元のグラフはs->tへの経路が存在する必要がある 16

17  最小カットをプログラムで計算するのは困難  最小s-tカット＝最大s-tフロー ◦ 最小カットの各辺のコストが、最大フローの容量になる 最大フローを求めるのにはDinic法を使う  O(EV 2 )だが、実際はもっと速いので、おすすめ 17 s A B t C 50/50 60/60 100/130 50/100 60/100 100/100 流量/容量

18 18 燃やす埋める問題 Very Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。 ◦ A,B,Cは「土に埋める」と100円もらえる。  最大で何円もらえるか？ 燃やす埋める問題 Very Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。 ◦ A,B,Cは「土に埋める」と100円もらえる。  最大で何円もらえるか？

19 19 燃やす埋める問題 Very Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。 ◦ A,B,Cは「土に埋める」と100円もらえる。  最大で何円もらえるか？ 燃やす埋める問題 Very Easy  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。 ◦ A,B,Cは「土に埋める」と100円もらえる。  最大で何円もらえるか？  最小カットは、最小値を求める。最大値ではない。  そこで、最小値を求める問題に置き換える！

20 20 燃やす土に埋める A50円の利益100円の利益 B60円の利益100円の利益 C130円の利益100円の利益 無条件で得られる利益燃やす土に埋める A100円の利益50円の損失0円の損失 B100円の利益40円の損失0円の損失 C130円の利益0円の損失30円の損失  利益が大きい選択肢の利益を、無条件で得られるこ とにする→その分選択肢からひくと全て損失に

21 21 燃やす土に埋める A50円の利益100円の利益 B60円の利益100円の利益 C130円の利益100円の利益  これはダメ！ ◦ 負辺があるときの最小カット問題はNP困難 燃やす土に埋める A-50円の損失-100円の損失 B-60円の損失-100円の損失 C-130円の損失-100円の損失

22 s A B t C 50 40 0 0 0 3030 燃やす 土に埋める  最小s-tカットは0+0+0=0  あらかじめ貰える利益は100+100+130=330  求める最大値は330-0=330

23 s A B t C 50 40 0 0 0 3030 燃やす 土に埋める  コスト0の辺もグラフに書きましょう！ ◦ 最小カット問題のグラフでは、 辺が元からないのと、損失0の辺とでは、別物です。 ◦ 最大フローを求めるときに、容量0になるのでいらない辺に なりますが、それでも書きましょう ◦ 複雑な問題だと、辺が元からないのか、コスト辺が0なのか で、混乱しやすくなる。

24 24 燃やす埋める問題 Easy  A,Bは「燃やす」か「土に埋める」必要がある。 ◦ A,Bは「燃やす」とそれぞれ20,100円かかる。 ◦ A,Bは「土に埋める」とそれぞれ50,20円かかる。 ◦ Aを燃やしたときに、Bを土に埋めると罰金300円かかる。  最小で何円かかるか？ 燃やす埋める問題 Easy  A,Bは「燃やす」か「土に埋める」必要がある。 ◦ A,Bは「燃やす」とそれぞれ20,100円かかる。 ◦ A,Bは「土に埋める」とそれぞれ50,20円かかる。 ◦ Aを燃やしたときに、Bを土に埋めると罰金300円かかる。  最小で何円かかるか？

25 25 s A B t 20 100 50 20 燃やす 土に埋める  Aを燃やしたときにBを土に埋めると 罰金300円かかる

26 26 s A B t 20 100 50 20 燃やす 土に埋める  Aを燃やしたときにBを土に埋めると 罰金300円かかる  Aを燃やしたときにBを土に埋めたら まだs-tカットが成立しないようにする

27 27 s A B t 20 100 50 20 燃やす 土に埋める  Aを燃やしたときにBを土に埋めると 罰金300円かかる  Aを燃やしたときにBを土に埋めたら まだs-tカットが成立しないようにする 300 罰金

28 28 s A B t 20 100 50 20 燃やす 土に埋める  こうすると、s-tカットするにはB→Aの辺をカッ トせざるをえない。つまり300円かかる。  もちろん、これは最小カットではない。  この制約条件の追加方法を理解できないと その後すべて理解できなくなるので注意！ 300 罰金

29  Wikipediaのほうで。 29

30 30

31 31 s A B t C 50 60 130 100 燃やす 土に埋める  選択肢はどういう順番に置いてもよい。 ◦ ただ、順番が悪いと、制約条件を追加できないことが ある。  考えて選択肢の順番を決めないといけない。

32 32 FoxAndGo3 引用:TopCoder SRM594 Div1 Medium http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=1 5706  囲碁っぽい問題。自分が黒番で好きなだけ黒石を 置ける。（死ぬ場所にも置けるので注意）  黒石で白石のまわりを隙間なく囲めば白石を除い て領地（＝空きマス）にすることができる。  領地の最大値を求めよ。  盤面の数は最大で50*50。また、白石同士は隣接 していない。 FoxAndGo3 引用:TopCoder SRM594 Div1 Medium http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=1 5706  囲碁っぽい問題。自分が黒番で好きなだけ黒石を 置ける。（死ぬ場所にも置けるので注意）  黒石で白石のまわりを隙間なく囲めば白石を除い て領地（＝空きマス）にすることができる。  領地の最大値を求めよ。  盤面の数は最大で50*50。また、白石同士は隣接 していない。

33 33  そのまま置かなければ、領地は24 ◦ 本物の囲碁と違います

34 34  黒石を置けば、白石がとれるけど、置いた分だけ 領地が21に減る。何もおかないほうが領地が24 で最大。

35 35  このままでは領地は１

36 36  黒石を真ん中に置くと、すべての白石が死に、自 分の領地になる。領地は4、これが最大値。

37 37  初期の領地は10ですが、黒をうまく置くと、 最大領地は12になるようです。

38 38  最大値を求める問題なので、このままでは 最小カットが使えない。 ◦ 黒石が最初からおいてあるところは絶対領地にできない ◦ つまり、仮の最大領地数=盤面の全マスー黒石数 ◦ そこから逆に以下のように考える  白石がとれなかったら、領地1の損失  領地（空きマス）で黒石をおいたら、領地１の損失 ◦ 仮の最大領地数ー最小の領地損失＝最大の領地数で求め ることができる。

39 39 s t 1 0 1 0 1 0 黒置く 白死領地 黒置く 領地 白のまま  黒石は無視してよい。選択肢がないから。  領地を1の損失と考えたこのグラフは正しい。  「白死領地にするには、まわりに黒を置かない といけない」の制約をどうするか？ 領地

40 s t 1 0 1 0 1 0 黒置く 白死領地 黒置く 領地 白のまま 領地 この２つを強制的に切らせたい

41 s t 1 0 1 0 1 0 黒置く 白死領地 黒置く 領地 白のまま 領地 +∞+∞ +∞+∞

42 s t 1 0 1 0 1 0 黒置く 白死領地 黒置く 領地 白のまま 領地 +∞+∞ +∞+∞  +∞の制約条件を入れても、最小カットが成立 してしまう。「黒置く」のところを強制的に カットさせたいのにできない。  +∞のリンクを逆にしても、同じ。

43 43 s t 0 0 0 1 1 1 領地 白死領地 領地 黒置く 白のまま  「黒置く」と「領地」の選択肢の順番を変える 黒置く

44 44 s t 0 0 0 1 1 1 領地 白死領地 領地 黒置く 白のまま  +∞の辺を白から領地の方向へ足す 黒置く +∞+∞ +∞+∞

45 45 s t 0 0 0 1 1 1 領地 白死領地 領地 黒置く 白のまま 黒置く +∞+∞ +∞+∞  こうすると、領地のところをカットしても、 まだs-tは繋がっている

46 46 s t 0 0 0 1 1 1 領地 白死領地 領地 黒置く 白のまま 黒置く +∞+∞ +∞+∞  仮に隣接する１カ所をカットしても まだs-tは繋がっている

47 47 s t 0 0 0 1 1 1 領地 白死領地 領地 黒置く 白のまま 黒置く +∞+∞ +∞+∞  つまり、白の隣接する領地は、すべて「黒置 く」を選ばないと、s-tカットできない。  「白死領地にするには、まわりに黒を置かない といけない」の制約通りになってる。

48 48 s t 0 0 0 1 1 1 領地 白死領地 領地 黒置く 白のまま 黒置く +∞+∞ +∞+∞  うっかり+∞の辺を領地から隣接する白方向に 足すと、うまくいかない。  上の例で、「黒置く」をカットしなくても、s-t カットができている。

49 49 FoxAndGo3 引用:TopCoder SRM594 Div1 Medium http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=1 5706  囲碁っぽい問題。自分が黒番で好きなだけ黒石を 置ける。（死ぬ場所にも置けるので注意）  黒石で白石のまわりを隙間なく囲めば白石を除い て領地（＝空きマス）にすることができる。  領地の最大値を求めよ。  盤面の数は最大で50*50。また、白石同士は隣接 していない。←この条件は意味ある？ FoxAndGo3 引用:TopCoder SRM594 Div1 Medium http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=1 5706  囲碁っぽい問題。自分が黒番で好きなだけ黒石を 置ける。（死ぬ場所にも置けるので注意）  黒石で白石のまわりを隙間なく囲めば白石を除い て領地（＝空きマス）にすることができる。  領地の最大値を求めよ。  盤面の数は最大で50*50。また、白石同士は隣接 していない。←この条件は意味ある？

50 50  もう気づいている方もいるかもしれませんが、 次の章にいけばわかります。

51 51

52 52 The Year of Code Jam 引用:Google Code Jam World Finals 2008 E （プログラミングコンテストチャレンジブック P357） https://code.google.com/codejam/contest/32011/dashboard#s=p4 https://code.google.com/codejam/contest/32011/dashboard#s=p4  カレンダーN月で、各月はM日。 ◦ 白：コンテストが開かれない日 ◦ 青：コンテストに参加する日 ◦ ？：コンテストが開かれるが、参加しようか迷っている日  １つのコンテストに参加すると ◦ 幸福度の初期値は4 ◦ カレンダー上で隣接する日に参加するコンテスト1つにつき幸 福度は1下がる  幸福度の最大値を求めなさい。  1≦N≦50, 1≦M≦50 The Year of Code Jam 引用:Google Code Jam World Finals 2008 E （プログラミングコンテストチャレンジブック P357） https://code.google.com/codejam/contest/32011/dashboard#s=p4 https://code.google.com/codejam/contest/32011/dashboard#s=p4  カレンダーN月で、各月はM日。 ◦ 白：コンテストが開かれない日 ◦ 青：コンテストに参加する日 ◦ ？：コンテストが開かれるが、参加しようか迷っている日  １つのコンテストに参加すると ◦ 幸福度の初期値は4 ◦ カレンダー上で隣接する日に参加するコンテスト1つにつき幸 福度は1下がる  幸福度の最大値を求めなさい。  1≦N≦50, 1≦M≦50

53 53

54 54 Surrounding Game 引用:TopCoder - SRM558 Div1 Hard https://code.google.com/codejam/contest/32011/dashboard#s=p4 https://code.google.com/codejam/contest/32011/dashboard#s=p4  長方形の盤面（最大20マス*20マス）があり、す べてのマスに利益と費用が割り当てられている。 ◦ マスに石を置くか、全ての隣接するマスに石を置くと、 利益が得られる。 ◦ マスに石を置くと、費用がかかる  スコア＝全利益-全費用とする。スコアを最大化 せよ。 Surrounding Game 引用:TopCoder - SRM558 Div1 Hard https://code.google.com/codejam/contest/32011/dashboard#s=p4 https://code.google.com/codejam/contest/32011/dashboard#s=p4  長方形の盤面（最大20マス*20マス）があり、す べてのマスに利益と費用が割り当てられている。 ◦ マスに石を置くか、全ての隣接するマスに石を置くと、 利益が得られる。 ◦ マスに石を置くと、費用がかかる  スコア＝全利益-全費用とする。スコアを最大化 せよ。

55 55

56 56 1 引用: 立命館合宿2013 Day2 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2496 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2496 http://www.slideshare.net/oupc/h1-17155052  長さnのビット列がある． ◦ 左からi番目のビットが1のとき，スコアをa i 点得られる． ◦ 左からi番目のビットを中心に距離w以内にある1の個数 (=|{j∈{1,…,n}∩{i-w,…,i+w}|左からj番目のビットが1}|) が奇数のとき，スコアをbi点得られる．  スコアを最も多く得られるようなビット列を求め よ． 1 引用: 立命館合宿2013 Day2 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2496 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2496 http://www.slideshare.net/oupc/h1-17155052  長さnのビット列がある． ◦ 左からi番目のビットが1のとき，スコアをa i 点得られる． ◦ 左からi番目のビットを中心に距離w以内にある1の個数 (=|{j∈{1,…,n}∩{i-w,…,i+w}|左からj番目のビットが1}|) が奇数のとき，スコアをbi点得られる．  スコアを最も多く得られるようなビット列を求め よ．

57 57

58 58 RabbitWorking 引用: SRM 542 Div1 Hard http://community.topcoder.com/stat?c=problem_statement&pm=11054&rd=1 4734  N匹（N≦50）のうさぎの集団がいる。  うさぎの集団から何匹かを選ぶ ◦ 利益の合計Pは、選んだウサギの集団、すべてのペア利 益p ik の総和で求められる(0≦p ik ≦9) ◦ 費用Cは、C=K(200-K)で求められる。Kは選んだうさぎ の数  効率P/Cを最大化せよ（効率は実数） RabbitWorking 引用: SRM 542 Div1 Hard http://community.topcoder.com/stat?c=problem_statement&pm=11054&rd=1 4734  N匹（N≦50）のうさぎの集団がいる。  うさぎの集団から何匹かを選ぶ ◦ 利益の合計Pは、選んだウサギの集団、すべてのペア利 益p ik の総和で求められる(0≦p ik ≦9) ◦ 費用Cは、C=K(200-K)で求められる。Kは選んだうさぎ の数  効率P/Cを最大化せよ（効率は実数）