1

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

3

燃やす埋める問題 引用:Komakiさんのページ  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。 ◦ A,B,Cは「土に埋める」と100円もらえる。 ◦ BとCの片方だけ「燃やす」と死ぬ。  死なずに最高で何円もらえるか？ 燃やす埋める問題 引用:Komakiさんのページ  A,B,Cは「燃やす」か「土に埋める」必要がある。 ◦ A,B,Cは「燃やす」とそれぞれ50,60,130円もらえる。 ◦ A,B,Cは「土に埋める」と100円もらえる。 ◦ BとCの片方だけ「燃やす」と死ぬ。  死なずに最高で何円もらえるか？ 4

Dual Core CPU 引用:POJ No.3469 （プログラミングコンテストチャレンジブック P212）  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 ≦ Dual Core CPU 引用:POJ No.3469 （プログラミングコンテストチャレンジブック P212）  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 ≦

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

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

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円かかる。  最小で何円かかるか？

燃やす埋める問題 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を「土に埋める」 ◦ =210円が最小

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

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

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

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

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

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

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

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

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

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 s A B t 燃やす 土に埋める  Aを燃やしたときにBを土に埋めると 罰金300円かかる

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

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

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

 Wikipediaのほうで。 29

30

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51

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

53

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

55

56 1 引用: 立命館合宿2013 Day  長さnのビット列がある． ◦ 左からi番目のビットが1のとき，スコアをa i 点得られる． ◦ 左からi番目のビットを中心に距離w以内にある1の個数 (=|{j∈{1,…,n}∩{i-w,…,i+w}|左からj番目のビットが1}|) が奇数のとき，スコアをbi点得られる．  スコアを最も多く得られるようなビット列を求め よ． 1 引用: 立命館合宿2013 Day  長さnのビット列がある． ◦ 左からi番目のビットが1のとき，スコアをa i 点得られる． ◦ 左からi番目のビットを中心に距離w以内にある1の個数 (=|{j∈{1,…,n}∩{i-w,…,i+w}|左からj番目のビットが1}|) が奇数のとき，スコアをbi点得られる．  スコアを最も多く得られるようなビット列を求め よ．

57

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