GCJ 2014 Qualification Round

その他 参加ログ

4問中ABCが解けて60pt、2654位。

A. Magic Trick

4x4マスに1〜16の番号が書かれたカードを2回並べる。
番号を1つ選んでもらって、何列目にその数字があるか？を教えてもらえる。
その番号は何か？わからない場合、複数ある場合は、それぞれ文字列を返す。


やるだけ。

B. Cookie Clicker Alpha

クッキークリッカーっぽいゲームがある。
最初は2cpsでクッキーが作れるが、クッキーC枚を使って+Fだけcpsを上げることができる。
(ただし、時間は連続的で、2cpsの場合は0.5sで1枚のクッキーができあがるっぽい)
最終的にX枚のクッキーを得るために必要な時間を答える。


縦軸に枚数、横軸に時間のグラフで推移を書いてみると、cpsが傾きの直線が書ける。
C枚に達するたびに0になるがcpsが増えるので、傾きが急になる。
そのたびにそのままXまで増やすのにかかる時間＋累計時間の最小値を探せばよい。
X

C. Minesweeper Master

RxCマスに、地雷がM個埋まっているマインスイーパーを考える。
クリックした地点が0(=周囲8マスに地雷がない)ならば、その周囲8マスを自動でopenする。
openした場所に0があれば再帰的＆自動的にopenされていく。
1クリックで地雷が埋まっていない全てのマスが開いてwinするような状態を出力する(クリックする場所と地雷の場所と何もない場所)。できなければ、できないと出力。


クリックする場所を左上に固定して考える。
R==1&&C==1の場合は、M==0しかないので、「c」でよい。
M==R*C-1の場合は、その1つだけ空いている場所をクリックすればよいので、「c***」のような出力。
R==1かC==1の場合は、それぞれの方向に、「c.***」「c..***」「c...***」のように、クリック位置、何もなし、地雷の順番で並んでいれば、連続して0のマスがopenされるので、よい。
R==2かC==2の場合は、Mが奇数の場合だと、うまくopenされない場所ができてしまうので、Impossible。偶数の場合は、クリック位置、何もなし、地雷の順番で並んでいればよい。

c...***
....***

R>=3、C>=3の場合は、領域を4つに分割して考える。

c.aAAAAA
..aAAAAA
bbCCCCCC
BBCCCCCC
BBCCCCCC

A(とa)とB(とb)の領域には2個ずつ入れないと、openされないマスができてしまうことに注意。
空白セルの方で考え、A,B,Cの領域で埋めないといけない空白セルをできるだけ左上側によせて配置してあげればよい。
なので、ABCで埋めるべき空白セルの数が、2個、4個、5個以上で場合分けした。
2個、4個ならaaとbbに埋める。5個以上であれば、aaとbbに一回埋めてから、AAかBBの領域に2個ずつ埋めて、埋められなかった残り分をCの領域に左上からうめていけばよい。

D. Deceitful War

KenとNaomiがゲームをする。しかし、それぞれ以下のような持っている情報が違う場合の勝ち数を考える。
2*N個の0〜1kgのブロック(同じ重さはない)があり、KenとNaomiがN個ずつ得る。1回戦ごとに、お互いのブロックをはかりに乗せて重いほうに1ptはいる。1度使ったブロックは破棄する。
N回戦後のポイントを考える。両方がそれぞれ最適戦略で動くことが保障される場合に、Naomiのポイント数をそれぞれ答える。
【ゲーム1】
・KenもNaomiも自分のブロックの重さしか知らない
・Naomiが先に正しい重さを言い、それを受けてKenが自分のブロックの正しい重さを言って、両方はかりにのせる
【ゲーム2】
・Kenは自分のブロックの重さしか知らないが、Naomiは自分のKenのブロック(ようするにすべて)のブロックの重さを知っている
・Naomiが先に嘘かもしれない重さを言い、それを受けてKenが自分のブロックの正しい重さを言って、両方はかりにのせる
・重さについて嘘をつく場合は、はかりに乗せた場合に矛盾になるようなことにはなってはいけない


ゲーム1のKen側の最適戦略は、
・KenがNaomiの言った重さより重いブロックを持っていれば、重いブロックのうち一番軽いブロックを使う
・KenがNaomiの言った重さより重いブロックを持っていなければ、持っているブロックで一番軽いブロックを使う
にせざるを得ないので、Naomiはどんな出し方をしてもどうしようもない。
なので、全ブロックを重さで昇順ソートしたもの(NKNNKNKNNKKKのような感じ)を作って、重さが小さいほうから'N'の場合にそれより右側にある一番小さな'K'を対応させていけば、Kenの勝ち数が得られる。
N-Kenの勝ち数がNaomiの勝ち数になるので、それを返す。


ゲーム2の最適戦略は、Kenはゲーム1の最適戦略をとってくると保障されるが、Naomiに嘘の重さをいうことができることで、使わせるブロックをコントロールできるようになっている。
Naomiは、Kenの一番重いブロックよりも重い重さを言うと、Kenは持っている一番軽いブロックを使ってくるので、'K'の一番軽いブロックよりも重い一番軽い'N'のブロックを使って勝つために、Kenの一番重いブロックよりも重い重さを答える感じになる。

全ブロックを重さで昇順ソートしたものを作って考えると、重さが小さいほうから'K'の場合にそれより右側にある一番小さな'N'を対応させていけば、Naomiの勝ち数が得られるので、それを返す。
(これは別にKNの順番のペアがいくつできるか？なので、重さが大きいほうから'N'の場合に、それより左側にある一番大きな'K'を対応させても同じ)