SRM637

久しぶりにwriterやってました。登場人物もやってました。
Cat SnukeWolf Sothe がゲームをする」というテーマで統一されています。
Cat Snukeといえば、いまのtopcoderの画像カンガルーだから早く猫の着ぐるみ買わないと。

Div2 Easy

猫のSnukeと狼のSotheで1~2Nが書かれた2N枚のカードでゲームをする。
まず、カードをN枚ずつ配る。
各ターンで2人のプレイヤーは同時に1枚ずつカードを出していき、大きい方のカードを出した方に1点が入る。
各ターンでプレイヤーが出したカードの情報が与えられるので、Snukeの点数を答えよ。

解法

やるだけ

Div2 Medium

2*Wのグリッドがあり、いくつかセルが黒く塗られている。
左端から右端まで白いセルだけを通っていくパスが存在するようにいくつかのセルを黒く塗る時、最大何カ所塗れるか。

解法

左から貪欲に埋めていく感じで考える。
両方空の列があったら基本ans++で、
#.~~~~..
..~~~~~.#
みたいに上下が切り替わってる場所の個数だけans--
オーバーキルっぽいけど、最短路問題を解いてもよい。
この問題だけ1人用ゲームです。

Div2 Hard

グリッドがいくつかのregionに分かれている。
まずSnukeがいくつかのregionを赤く塗る。
残りのregionをSotheが青く塗る。
青いセルのみを辿って上端から下端まで行けたらSotheの勝ち。
Snukeが勝つためには最小で何カ所の"セル"を塗らなければならないか。

縦,横 <= 50
regionの個数<=62

解法

各regionを頂点と見なして、8近傍で接しているregionに辺を張る。
そのグラフで左端から右端への最短路を求めれば良い。(重みはregionのサイズ)
平面グラフの最小カット=最短路的なあれ。

ちなみにこのゲームの元ネタはHexとか。

Div1 Easy

猫のSnukeと狼のSotheで1~2Nが書かれた2N枚のカードでゲームをする。
まず、カードをN枚ずつ配る。
各ターンで2人のプレイヤーは同時に1枚ずつカードを出していき、大きい方のカードを出した方に1点が入る。
Snukeの手札と、Sotheがi番目に出すカードの情報(-1なら分からない、1~2Nならそのカードを出す)が与えられる。
Snukeの手札を順番を適切に決めて、得点の期待値を最大化し、その期待値を返せ。

解法

見えてる所は出来るだけ多く勝った方が良い。なぜなら、見えている所でわざわざ負けてそのカードを見えていない所に回して一勝するよりは、見えている所をちゃんと勝つ方が良い(または同じ)。勝つときはぎりぎりで勝つのが最善。絶対に負けるカードに対しては持っている中で最小のカードを割り当てる。
残った完全なる運ゲー部分は、カードごとに独立して期待値を計算し、足し合わせれば良い。期待値線形性ってやつだっけ。

Div1 Medium

2*Wのグリッドがあり、いくつかセルが黒く塗られている。
交互にセルを1つずつ塗っていく。左端から右端まで白いセルだけを通っていくパスが無くなるように塗った人の負け。

解法

まず、右端の4セルのうちのどこかと左端の4セルのうちのどこかが埋まったらあとは何の戦略も無く、終局までの手数の偶奇が一定となり、それによって勝敗が決まることに気付く。
両端2列ずつを抜き出してみる。
f:id:snuke:20141024163109p:plain
となっていた場合はもう勝敗は決している。
f:id:snuke:20141024163137p:plain
となっていた場合は右の4セルのうち上に置くか下におくかで終局までの手数の偶奇を好きに選べるため、先手の勝ち。
f:id:snuke:20141024163145p:plain
となっていた場合は見合いとなっており、この8セルのうちどこかを塗ってしまうと1つ上のパターンとなり、負けてしまう。
つまり、中略の区間での勝敗がこのゲームの勝敗となるため、再帰的に判定して行けば良い。

ちなみに、空の区間で分割してグランディー数とかで解けてしまうのが少し残念。グランディー数強過ぎるんじゃいー。
追記:制約でかくすればgrundyやるだけ問題じゃなくなって良かったなぁとすごく後悔しています・・・

Div1 Hard

グリッドがいくつかのregionに分かれている。
何らかの手順でゲームが行われ、ゲームの最終状態では、いくつかのregionを赤く塗られ、残りのregionをSotheが青く塗られている状態になる。
赤いセルのみを辿って左端から右端まで行けたらSnukeの勝ち。
青いセルのみを辿って上端から下端まで行けたらSotheの勝ち。
両方勝てないことはあり得るかどうかを判定せよ。

縦,横 <= 30

解法

結論から言うと、
格子点を頂点、異なるregion同士の境界を辺としてグラフを作る。
このグラフから1つ頂点を選んでsourceとし、四隅の頂点をsinkとしてフローを流した時、4流れればinvalidとなる。
フローに使われた辺をまたぐregionに異なる色を塗れば復元できる。

まず、上端と下端・左端と右端をcutしたい。
平面グラフのcut→最短路的なあれを考えると左端→右端のフローと上端→下端のフローを同時にながせれば良さそうですが、それだとあんまりうまくいかない。
混ぜちゃうと多分、
AAB
CAA
を誤ってinvalidと言ってしまったりする。
そこで少し考える。
左端→右端のフローと上端→下端のフローは少なくとも1点で交わるはずなのでその点をsourceにして、
中央→右端・中央→左端・中央→上端・中央→下端の4つのフローにすると良さそう。
少し悩みそうなのはsinkをどうするかですが、盤外の上下は青で、左右は赤で塗られていると考えれば、フローの脱出口が四隅だけになってhappy。
ざっくりですが以上です。

解法2
8近傍のregion間に辺を張り、辺の交差点からフローが4流れるかを判定。
解法1とわりと違う気がするのに正しく解けるの面白い。
強いケース:
ABC
DED
DDD
フローを流した時に次数が4になる頂点が2つ。
解法2を8近傍でなくて4近傍にするとこれが落ちるらしい。