2010年度 ＩＣＰＣ ＯＢＯＧ会夏合宿 _セット（２日目） 解答と解説

（※）この解答と解説は、ＯＢＯＧ会公式のものではありません。


（※）チーム_の公式見解ですらありません。

セット作成担当メンバー

・iwi
・omeometo
・jellies（←この記事の執筆者）

とりあえず問題文のみ公開（１０問分）

こちらからどうぞ。

問題１　雅先生の地球侵略日誌

（問題文は要約です）


N（2≦N≦20億）枚のコインがある。1枚だけ偽物で、他より重い。
天秤ばかりを使って偽物を見つけるとき、最悪でも何回使えれば十分か。最小値を求めよ。

問題１　解答例

天秤ばかりの両方の皿に、未知のコインを同じ数だけ乗せる以外の戦術をとっても得しないことが、すぐに示せます（すでに本物だと判明したコインは捨ててよい）。


なので、1回の操作ごとに、「左の皿に乗せる枚数」「右の皿に乗せる枚数」「どちらにも乗せない枚数」のうち最大のものだけが残ると考え、再帰的に計算していけばよいです。
O(logN)。

問題１　参考文献

雅先生の地球侵略日誌 (ファミ通文庫)

既刊1巻。


簡単な1問目ということで、この問題だけは、タイトル・問題文の設定ともに、何のヒネリもなく出典そのままです。固有名詞すらそのまま。


このあいだ、とある会津コンテストでベン・トー宣伝問題を見たので、それへのリスペクトも込めて。
とはいえ、自分の好きなラノベ・クオリティの高いラノベで固めることはせず、できるだけ色々なラノベを幅広く引用する感じです。（ただし、入手のしやすさを考えて、ある程度最近のラノベを選択）
ライトノベル販売促進委員会、競技プログラミング業界支部。


あらすじ紹介は、ほぼ問題文に書いた通り。これにビビッときた人はぜひ購入を。
スーパーヒーロータイムを毎週欠かさず観ており、なおかつパロディー小説が大好きな人には、特にオススメの1冊です。まいじゃー風に言うなら、赤枠オススメ。


ちなみに、ICPC本番とは異なり、8段落目から読み始めても十分に問題を理解できる仕様。

問題２　友だちの誘い方

N（1≦N≦100,000）人の友達がいる。部分集合をとって、そこに所属する人数を最大化せよ。
ただし、それぞれの友達には、「自分が部分集合に所属しているとき、所属人数がa人以上b人以下でないと不満を抱く」という制約がある。誰からも不満が出ないようにしなければならない。

問題２　解答例

「a人以上b人以下」を区間とみなし、N個の区間の集合を考えます。


部分集合の人数を「k人」と決めたとき、その部分集合を作ることができるかどうかは、「k人」を含む区間がk個以上あるかどうかで分かります。


あとは、区間の始点と終点のみに注目しつつ、k=1,2,……,nと順に調べていけばＯＫです。
O(N)。

問題２　参考文献

友だちの作り方 (HJ文庫)

既刊1巻。


とにかく、いい意味でひたすら地味な1作。
あえて一言で言うなら、はがないから「残念」を引いた話です。


嫌な人間すら一人も出てこない、青い青い人間ドラマ。
小学校の図書室とかに置いてあっても、違和感のないレベル。
内省的な学園ドラマが好きな人に若干オススメ、かも。

問題３　時空のスゴロク・ロード

N（3≦N≦100,000）マスから成る1次元スゴロクがある。6面ダイスを振って、出た目の数だけ進むことを繰り返す。
マスには「○マス進む（戻る）」と書かれていることがあり、止まったらその指示に従う。指示で動いた結果、また効果マスに止まったら続けて従う。これを繰り返して無限ループになってしまったらスゴロク失敗。
ゴールするまでにサイコロを振る回数の最小値はいくつか。

問題３　解答例

前半：あるマスに止まったとき、指示に繰り返し従った結果、最終的にどこに止まるか（もしくは無限ループに陥るか）を求めます。
実際にシミュレーションします。安直に毎回やるとO(N^2)でアウトですが、一度通ったマスの結果を覚えておけば、O(N)で済みます。


後半：幅優先探索で最短路問題を解きます。O(N)。ダイクストラでも十分間に合います。

問題３　参考文献

時空のクロス・ロード最終譚―一番列車は朝焼けに (電撃文庫)

既刊7巻。


タイトルで駄洒落シリーズ第1弾。
自分はこの作品あんまり好きじゃないのですが、鷹見一幸ファンの方は、まあ、買えばいいんじゃないでしょうか。


というかこの問題設定、クロス・ロードとはまったくもって関係なく、『狂乱すごろく階段日記』の設定ほぼそのままです。
読んでる人が有利……と言えば有利ですが、まあ、簡単な問題なので別にいいや、ということで。


最初は優歌の一人称で問題文を書いていましたが、せっかくの日本語問題文なので、英語ではできない駄洒落タイトルの方を優先することにしました。

問題４　僕の友達は小さい

N（1≦N≦200）個の荷物と、容量制限W（1≦W≦10,000）のナップサックがある。容量制限を超えないように、荷物をランダムに1つずつ詰めていく。荷物を全部詰め終わるか、もうどの荷物を詰めても制限をオーバーしてしまう状態になったら終了。
最終的にナップサックに入っている荷物の集合は何通り考えられるか。10億7（素数）で割った余りを答えよ。

問題４　解答例

荷物を重い順にソート。通常のナップサック問題を解くときと同じようなDPを行います。


「最終的にナップサックに入っていない荷物のうち、最も軽い荷物x」で場合分けすれば、先ほどのDP結果を利用して、それぞれの場合の数が求められます（xより軽い荷物は全て入っていることに注意）。
O(NW)。必要メモリ量は、O(W)で済みますが、O(NW)かけてもよいです。

問題４　参考文献

僕は友達が少ない (MF文庫J)

既刊4巻。


言わずと知れたはがない。


つい最近東大ブランドも味方につけて大人気のライトノベル。
今さら自分が紹介するまでもないでしょう。なので省略。

問題５　街を駆ける道

平面上に、赤い点がN個と青い点がM個ある（2≦N,M≦1,000）。どの3点も一直線上にない。
赤い2点A,Bと、青い2点C,Dが指定される。
赤い点のみを経由してA,Bを結ぶ折れ線と、青い点のみを経由してC,Dを結ぶ折れ線を書く。違う色の折れ線同士が交差してはならないとき、2つの折れ線の長さの和の最小値を求めよ（存在しないときは-1）。

問題５　解答例

ちょっと考察すると、「片方の色の点は、直接、指定された2点を結び」「もう片方の色の点は、高々他の2点を経由して指定された2点を結ぶ」と仮定してよいことがわかります。


これさえ分かれば、ダイクストラすら使う必要がなく、答えが求まります。


必要な幾何アルゴリズムは、線分と線分の交点くらい。
しかも、どの3点も一直線上にないことが保証されているので、楽に組めます。
O(N^2+M^2)。

問題５　参考文献

地を駆ける虹 (MF文庫J)

既刊3巻。


タイトルで駄洒落シリーズ第2弾。ちをかけるにじ。まちをかけるみち。


最初は、痛主人公中二病鬱ＭＦファンタジーだったはずが、巻が進むにつれて肝心の主人公が成長しちゃうせいで……なんか普通の話に。
そして“魔改造”に至る。（問題８参照）

問題６　１０歳の動的計画

(0,0)から(N,M)まで（1≦N,M≦100,000）、(+1,0),(0,+1),(-1,0),(0,-1)の4種類の動きを組み合わせて移動するとき、移動の仕方は何通りあるか。10億7（素数）で割った余りを答えよ。
ただし、(-1,0),(0,-1)を合計ちょうどK回（1≦K≦10,000）使うこと。K回使い切る前に(N,M)に辿り着いても、ゴールしたと見なさず動き続ける。
また、X座標またはY座標が負になる点に入るような移動はできない。

問題６　解答例

(-1,0)を使う回数で場合分け。全部足しましょう。


X方向の移動とY方向の移動は、それぞれ独立に考えたうえで、後で統合すればよい。
X方向だけの移動に関しては（Y方向も同様）、例の↓のような図を書いて考えれば、高校数学レベルの場合の数で解けます。



（右か上にのみ動けるとする。
「Ｓ→Ｇの、赤丸を通らないルートの総数」
＝「Ｓ→Ｇのルートの総数」−「Ｓ→Ｇの、赤丸を通るルートの総数」
＝「Ｓ→Ｇのルートの総数」−「Ｓ→Ｇ’のルートの総数」）


実装よりも、計算機を使いだす前の手計算が面倒な問題です。
3人チームに計算機が1つなので、余った人が計算を担当するのが理想かもしれません。
コンビネーションの値は直前の結果が利用でき、O(N+M+K)。

問題６　参考文献

10歳の保健体育 (一迅社文庫 た 1-2)

既刊1巻。


タイトルで駄洒落シリーズ第3弾。“保健体育と動的計画って似てね？”って言いだしたの誰だよ！　俺だよ！


内容に関しては、“竹井10日”好きは即買え、嫌いなら絶対買うな、以上。

問題７　スプリング・タイル

W×Hのダンジョンがある（3≦W,H≦500）。ダンジョンのマスは、壁、床、バネ、階段からなり、あなたは初期位置から1ターンに1歩、上下左右のいずれかに移動できる。
バネを踏むと、いずれかの床の上にランダムに飛ばされる。
最善の戦術をとったとき、階段に辿り着くまでのターン数の期待値を求めよ。
もう決してゴールできない“詰み”の状態に陥ることのないマップだけが与えられるとしてよい。

問題７　解答例

どのバネも同じ役割を果たすことに気づくのが第一です。


まずは、「歩いて階段まで辿り着くのに必要な最小ターン数a」と「歩いてバネまで辿り着くのに必要な最小ターン数b」を、それぞれの床に対して求めましょう。
これは、「階段」もしくは「バネ」をスタートとみなした幅優先探索で求められます。O(WH)。


自分があるマスにいるとき、「そのマスにおけるa-bの値が一定値より大きければバネに向かい、そうでなければ階段に向かう」のが最善の戦術であることがわかります。この“閾値”は、全通り試してしまって問題ないでしょう。
a-bの値で全床をソートし、全通り試せばＯＫです。O(WH×log(WH))。

問題７　参考文献

スプリング・タイム (ガガガ文庫)

既刊1巻。


タイトルで駄洒落シリーズ第4弾。、『スプリング☆メイズ』とどっちにしようか迷いましたが、ラノベタイトルで問題セットに統一感を出すために、こちらにしました。


肝心の内容は、タイムスリップを題材にした、直球のノスタルジー小説。
台詞回しは多少好き嫌いが分かれるような気がします。


買おうかどうか迷ったら、とりあえず買って損はしないレベル、だと思います。

問題８　ねこ鍋改造計画（仮）

オスの猫がN匹、メスの猫がM匹いる（1≦N,M≦500）。各猫には、それぞれm_i（1≦m_i≦10,000）とc_i（1≦c_i≦10億）というパラメータが定まっている。また、整数W（1≦W≦10,000）が与えられる。
オス猫の部分集合Aとメス猫の部分集合Bを定め（ただし空集合ではダメ）、次の値dを最小化せよ。
d=max{Mmax-Mmin , Cmax-Cmin}。
ただし、Mmaxは、Aに属する猫のm_iの和とBに属する猫のm_iの和のうち大きい方、Mminは小さい方をあらわし、Cmaxは、AまたはBに属する猫のc_iの最大値、Cminは最小値をあらわす。
また、Mmaxの値はW以下でなくてはならない。

問題８　解答例

dの値で二分探索します。
まずは、全猫をcの小さい順にソート。その順に従って、猫を組み合わせてm_iの和で特定の値を作るナップサック問題をDPで解きます（ただし、オスとメスは区別しておく）。
ただし、その際、「作れるかどうか」だけではなく「その値を作るのに必要な猫のcの最小値の最大値」も求めていきます。
こうやってO((N+M)W)でDPすれば、二分探索中のdの値で部分集合を作れるかどうかが分かります。全部まとめてO(（N+M）W×log（c）)。


……ただし、これだと微妙に間に合わないので、二分探索をやめて、しゃくとりメソッドで解きます。
ソートに関しては同様。DPのやり方も、ほぼ同様。
ただし、d=max{Mmax-Mmin , Cmax-Cmin}なので、MとCのうち、大きい方の値を小さくするように、しゃくとり範囲を動かしていきます。O((N+M)W)。

問題８　参考文献

丸鍋ねこ改造計画(仮) (MF文庫J)

既刊3巻。


タイトルで駄洒落シリーズ第5弾……と見せかけて、そもそも「丸鍋ねこ」というネーミングが「ねこ鍋」由来だと思われるため、駄洒落になっていないというオチ。
例えるならば、「木津千里」とか「日塔奈美」に混ざって「久藤准」がいる違和感に近いかもです。


『地を駆ける虹』から続けて読めば、俗に言うMF文庫Jの“魔改造”の典型例を体験できます。
ちなみに、自分はあまりこの本が好きではありません。

問題９　よくわかる二重魔法

N個の点（2≦N≦100）からなる連結単純無向グラフが与えられる。
このグラフのすべての無向辺に向きをつけることで得られる、以下の条件を満たす（点i,点j）のペアの数の最大値を求めよ。


条件：「点iからスタートして、向き通りに辺をたどって点jまで辿り着ける」
（i=jのときは、常にこの条件が満たされているものとする）

問題９　解答例

ざっくり説明しづらいので、ある程度厳密に書きます。


まずは与えられた有向グラフを橋で分解します（二重辺連結成分に分解する）。
O(M+N)ですが、安直にO(M^2)のアルゴリズムでもたぶん間に合います（Mは辺の数）。


分解されたそれぞれの成分内では、任意の点から任意の点に移動できるように向きをつけられることが示せます。全体としてもそれが最良になります。


各成分をあらためて1つのノードとみなすと、これは木になっています。
なので、問題は「無向木が与えられる。ただし各頂点vには重みw(v)が定義されている。これに向きをつけ、スコアを最大化せよ。ただしスコアとは、点aから点bへと辺を向き通りにたどって移動できるときw(a)*w(b)点もらえるものである」に帰着されました。
以下、この問題を考えます。木は、適当な頂点を根として考えます。


まずは、どの辺にも向きをつけていない状態からスタートします。


各頂点に対して、次のようにして「入重み」と「出重み」を定義します。
頂点vの入重み：頂点vからスタートして、向きのついた辺のみを「向き通りに」辿って辿りつける全頂点をa1,a2,……とすると（v自身も含む）、頂点vの入重みはw(a1)+w(a2)+……である。
頂点vの出重み：頂点vからスタートして、向きのついた辺のみを「逆向きに」辿って辿りつける全頂点をa1,a2,……とすると（v自身も含む）、頂点vの出重みはw(a1)+w(a2)+……である。


以降、ある頂点の「入重み」がa、「出重み」がbであることを、[a,b]と書きます。
初期状態では、どの辺にも向きがついていないので、vは[w(v),w(v)]です。


ある葉ノードAが[a,b]で、Aの親ノードBが[c,d]で、辺A-Bに向きがついていないとき、A→Bと向きをつければ、Aを削除し、Bが[c,b+d]になり、スコアをbcだけ獲得したグラフと等価になります。
同様の条件で、A←Bと向きをつければ、Aを削除し、Bが[a+c,d]になり、スコアをadだけ獲得したグラフと等価になります。

これらの定理を使って、葉ノードから順に、ノードを1つ1つ消していきます。


dp[N][N][N]を定義して動的計画します（Nは元々の頂点の数）。
dp[v][i][j]には、頂点vが[i,j]となるように、vの子孫ノードを全部消したときに獲得できるスコアの最大値を入れておきます。
ノードの数がO(N)個、各ノードに対してdp変数がO(N^2)個、dp変数を1つ埋めるのにO(N^2)かかるので、あわせてO(N^5)です。


とはいえ、dp[x][i][?]の最大値と、dp[x][?][i]の最大値（?を動かしたときのmax）を保持しつつ計算すれば、1つ埋めるのにO(N)で済みます。
これでO(N^4)になったので、間に合います。


ちなみに、これでTLEする場合は、初期状態の対象性より、実はdp[v][i][j]＝dp[v][j][i]であることを使うと、2倍早くなります。

問題９　参考文献

よくわかる現代魔法 (集英社スーパーダッシュ文庫)

既刊6巻。


タイトルの、よくわかる“二重”魔法が、二重辺連結成分分解を暗示しているよ！　みたいなっ！
実際、USAGI codeはそこから「橋に分解すればいい」ことの確信を得たとか。


アニメ化した程の有名ラノベなので、わざわざ自分が語るまでもないでしょう。
プログラミングを題材としているように見せかけて、実際はそれっぽい用語がよく出てくる程度です。


ちなみに、この問題文、第一稿では長さがこの2倍くらいあり、固有名詞も今の3倍くらい登場、しかもその全てが聞いたこともないようなオリジナル用語で固められていました。
冒頭で無駄な設定を延々と垂れ流す3流ファンタジーっぽいものを目指す予定でしたが……自重しました。


あとはまあ、なぜか序盤にバレバレの言葉遊びラッシュがありますが、特に深い意味はありません。
（紀慧歴→きけえ歴→架空歴、2119年15の月→21,19,15→USO、Sengemon→mensonge（嘘）、Lugene→leugen（嘘）、In Magiray→imaginary（架空の））

問題１０　問題文担当者は働かない！

N個の点（1≦N≦1,000）とM個の辺（1≦M≦10,000）からなる有向グラフがある。このグラフに閉路はない。
それぞれの点には、いくつかの石が置かれている（1≦各点の石の数≦10,000）。


このグラフを使って、２人のプレイヤーがゲームをする。
おのおのの手番は、交互に訪れる。
各プレイヤーは、自分の手番において、頂点vを選び、そこに置かれた石を１つ以上取り除く。
その後、vからwに辺が張られているすべての頂点wについて、wに置かれている石の個数を自由に変化させることができる（いくつ増やしても、いくつ減らしても、変化させなくてもよい）。
これを繰り返して、最初に取る石がなくなった方の負けである。
両者が最善をつくしたとき、先手と後手、どちらが勝つか。もしくは、いつまでもゲームが終わらないか。

問題１０　解答例

ゲームが必ず終了することは適当にやれば示せます（閉路がないことに注意）。


「有向グラフのどこかの頂点にコマが置かれている。先手と後手は、交互にコマを、張られている辺にそって1マスずつ動かす。動かせなくなったら負け」というゲームを考えます。
このゲームのグランディー数を、各状態（＝各頂点）について求めます。O(N+M)。


f(n)を、「グランディー数がnであるすべての頂点について、そこに置かれている石の数のxorをとった値」と定義します。
すると、任意のnに対してf(n)=0のとき、後手必勝。そうでないとき先手必勝であることが示せます。


＜証明＞
任意のnに対してf(n)=0である状態を「悪い状態」、そうでない状態を「良い状態」とする。
・悪い状態からどのように1手進めても、必ず良い状態になる
・良い状態からうまく1手進めると、必ず悪い状態にできる
ことを示せばよい。


（前者）
1手進める。
このとき、石を取った頂点をvとする。vのグランディー数をg(v)とする。
グランディー数がg(v)と一致する頂点の中で、石の数が変化した頂点はvだけである。
ゆえにf(g(v))は0ではなくなる。


（後者）
f(n)が0にならない最大のnをNとする。
普通のNimのときと同様に、グランディー数がNの適当な頂点vを選んで、f(N)=0になるように石を取ることができる。
また、グランディー数の定義より、vからグランディー数が0,1,2,……,N-1の頂点について辺が必ず張られている。これらは好きに石の数を操作できるので、悪い状態にすることは可能。

問題１０　参考文献

鳳凰堂みりあは働かない! (MF文庫J)

既刊3巻。


働かないやつに、ニートを名乗る資格があるか！
……な、ニート系ラブコメディ。


〜あらすじ〜
人並み外れた運動能力を秘めているが、ド貧乏なためアルバイト漬けの日々を送っていた主人公。
しかし、クリスマスイブの日、ちょっとした勘違いがもとで、超大金持ちの、ワガママお嬢様の下で働き続ける羽目になり――！
（※）ただし１箇所嘘です。


どうでもいい言葉のこじつけでお腹いっぱいになれる人には、オススメ。

難易度まとめ

各問題の難易度を、TopCoderSRMDiv1のスコアで例えると、


問題１：150
問題２：250
問題３：300
問題４：500
問題５：500
問題６：600
問題７：600
問題８：1000
問題９：1100
問題１０：1000


あたりに相当するでしょうか。

あとがき

自分が作る情報の問題は、基本的に、


（１）特定作品にある設定をそのまま問題にする。（※例）
（２）特定作品にある設定をおおよそ活かし、少しの味付けを加えて情報の問題らしい状況を作り上げる。（※例）
（３）特定作品を出したいがために、無理やりこじつけて問題にする。
（４）特定作品のタイトル・用語だけをもじる。


のいずれかに該当します。（競技プログラミング界隈でわりとよく見かけるのは（３））


普段、自分がイチから問題を作るときは、作るのが非常に楽な（１）（２）を選ぶことが多いです。
しかし、今回は、


・自分以外の人も問題原案を作っている　→　後からこじつけて（１）（２）にするのは一般に難しい
・日本語で問題文を書いていい　→　せっかくの機会なので、英文だと不可能な（４）を存分にやろう


という理由で、大半が（４）で埋め尽くされています。
（一部、地味に（１）や（２）が混ざっていますが）


ちなみに、没になった案として、


問題１　幸せの背景は不幸
問題２　善意の指針は悪意
問題３　死の礎は生
問題４　絆の支柱は欲望
問題５　欲望の主柱は絆
問題６　嘘の価値は真実
問題７　死後の影響は生前
問題８　記憶の形成は作為
問題９　日常の価値は非凡
問題１０　始まりの未来は終わり


というものがありましたが、問題文があまりにアレな文章で埋め尽くされそうだったので没になりました。