AtCoder Regular Contest 021

A - DEAD END

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたは友人の高橋君からとあるゲームを熱烈にオススメされている。

このゲームは 4 \times 4 のグリッド状に区切られた 16 個のセルと、その上に置かれた数が書かれたタイルを使ってプレーする。1 回の操作では上下左右の 4 方向のうちいずれかを指定することができ、指定した方向に向かってセル上のタイルが滑っていく。このとき、同じ数の書かれたタイル 2 枚がぶつかるとその 2 枚はグリッド上から取り除かれ、代わりに数を 2 倍した別のタイルが 1 枚新たに置かれる。

次の図は盤面の状態と、そこから右に向かって 1 回操作を行った後の盤面の例である。

上下左右のどの方向を指定してもタイルがまったく滑ることができず、同じ数のタイルをぶつけることもできなくなったらゲームオーバーで、それまでに出来るだけ大きい数の書かれたタイルを作るのが目的だ。

このゲームは確かに非常に面白そうだと思ったが、まだ慣れていないからか、グリッド上がタイルでいっぱいになったときにゲームオーバーなのかをなかなか判別できない。そこで、グリッド上のタイルの情報が与えられたときにゲームオーバーの状態なのかどうかを判定するようなプログラムを書くことにした。

入力

入力は以下の形式で標準入力から与えられる。

A_{1,1} A_{1,2} A_{1,3} A_{1,4}
A_{2,1} A_{2,2} A_{2,3} A_{2,4}
A_{3,1} A_{3,2} A_{3,3} A_{3,4}
A_{4,1} A_{4,2} A_{4,3} A_{4,4}

4 行にわたってタイルの情報が書かれている。A_{r,c} (2 ≦ A_{r,c} ≦ 2048) は、グリッド上で上から数えて r 番目、左から数えて c 番目のセルに置かれているタイルに書かれている数を表す。
- A_{r,c} はすべて 2 の累乗である。すなわち、A_{r,c} は 2,\,4,\,8,\,16,\,32,\,64,\,128,\,256,\,512,\,1024,\,2048 のいずれかである。

出力

与えられたグリッドの状態がゲームオーバーなら GAMEOVER、まだ操作ができるなら CONTINUE と 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

出力例1

CONTINUE

上下にはタイルを動かすことができませんが、左右に動かせば 2 が書かれたタイルどうしや 8 が書かれたタイルどうしをぶつけることが可能です。

入力例2

出力例2

GAMEOVER

どの方向に動かそうとしても同じ数の書かれたタイルをぶつけることができません。

入力例3

出力例3

GAMEOVER

B - Your Numbers are XORed...

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

小学 N 年生になったばかりの妹は、授業で 排他的論理和 というものについて学びました。

排他的論理和とは、例えば非負整数 P と Q の排他的論理和を R としたとき、以下のように定義されます。

R を 2 進数表記したときの 2^k (0 ≦ k，k は整数) の位の値は、P を 2 進数表記したときの 2^k の位の値を p、Q を 2 進数表記したときの 2^k の位の値を q としたとき、p=q なら 0、p≠q なら 1 となります。

具体的には、3 と 5 の排他的論理和の値は、3 の 2 進数表記が 011、5 の 2 進数表記が 101 のため、2 進数表記が 110 となる 6 が排他的論理和の値となります。

排他的論理和の素晴らしさを知った妹は、嬉しさの余り、周囲にあった非負整数の値を手当たり次第に排他的論理和された値に書き換えました。

ところが、その中には兄が提出する予定の書類が入っていたのです！

兄は外出中なので、今のうちに元の数列に復元することにしました。手がかりとして、以下のことが分かっています。

書類には L 個の非負整数 A_1，A_2，…，A_L が書いてありました。これらの数は今や書類には書き残されていません。妹の目的は、これらの数を知ることです。
書類には L 個の非負整数 B_1，B_2，…，B_L が書いてあります。これらの数は書類に書き残されているので知ることができます。

B_1，B_2，…，B_L は、以下の定義で表される数です。

1 ≦ i ≦ L-1 を満たす整数 i に関して、B_i の値は A_i と A_{i+1} を排他的論理和した値に等しい。
B_L の値は A_L と A_1 を排他的論理和した値に等しい。

大変残念なことに場合によっては該当する元の数列が存在しないことや、複数通り存在する場合があります。どうしましょう！

困った妹は、今日の占いのラッキーアイテムが辞書であったことを思い出しました。辞書、じしょ、辞書順…

最終的に、以下のルールを追加することにしました。

該当する元の数列が存在しない場合は、仕方がないので存在しないむねを示す -1 を答えとします。
該当する元の数列が複数存在する場合は、辞書順最小な数列を出力します。

ここで、2 つの数列 S_1，S_2，…，S_L と T_1，T_2，…，T_L に関して、 S_1，S_2，…，S_L が T_1，T_2，…，T_L より辞書順で小さいというのは、以下の条件を満たす場合とします。

ある整数 i (1 ≦ i ≦ L) に関して、1 ≦ j ≦ i-1 を満たすどの整数 j に関しても S_j=T_j が成立し、かつ S_i＜T_i が成立する。

あなたは妹の代わりに上記の条件を満たす数列を出力するプログラムを作成してください。

入力

入力は以下の形式で標準入力から与えられる。

L
B_1
B_2
:
B_L

1 行目には、書類に書かれている数字の個数を表す整数 L (2 ≦ L ≦ 10^5) が与えられる。
2 行目から L 行では、書類に残されている非負整数について書かれている。このうち i 行目では整数 B_i (0 ≦ B_i ＜ 2^{31}) が与えられる。

出力

元の非負整数列 A_1，A_2，…，A_L として考えられるものが存在する場合は、それらのうち辞書順最小なものを L 行にわたって出力せよ。このうち i 行目には整数 A_i を出力せよ。存在しない場合は -1 を出力せよ。出力の末尾にも改行を入れること。

入力例1

2
1
1

出力例1

0
1

A_1 と A_2 を排他的論理和した値が 1 となるものが正解になります。このような 2 つの数は複数通りありますが，A_1=0，A_2=1 を満たす場合が辞書順最小になります。

入力例2

出力例2

-1

条件を満たす元の数列は存在しません。きっとどこかで誤った操作をしたのでしょう。

入力例3

出力例3

0
1
3

C - 増築王高橋君

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は友人達ととあるゲームをしている。

このゲームでは、プレイヤーは建物を購入し、増改築し、できるだけ多くお金を稼ぐことが目的となる。

高橋君は現在 2 位であり、どうにかして首位の青木君より多くのお金を稼がなければならない。

高橋君は、最も多くの回数増築したものに与えられる称号「増築王」を手に入れることで、政府から受ける援助金を利用して勝利しようと計画した。長年の経験から、あと K 回増築することで増築王になれることが分かっている。

高橋君は現在 N 軒の建物を所有している。建物には 1 から N まで番号がついている。最初、どの建物も増築されていない。

建物 i (1 ≦ i ≦ N) について、以下のことが分かっている。

建物 i の増築前の価格は A_i である。
建物 i を 1 回増築するには、建物 i の現在の価格に等しい費用が必要となる。
建物 i の価格は、1 回増築する度に D_i だけ上昇する。

高橋君は他の戦略も同時並行で実施するので、増築にかけるお金の合計値ができるだけ少なくなるようにしたい。

あなたは高橋君の代わりに K 回増築するのに必要な価格の合計値として考えられる最小値を求めてほしい。

入力

入力は以下の形式で標準入力から与えられる。

K
N
A_1 D_1
A_2 D_2
:
A_N D_N

1 行目には、増築王になるために必要な増築の回数 K (1 ≦ K ≦ 10^8) が与えられる。
2 行目には、高橋君が所有している建物の軒数 N (1 ≦ N ≦ 10^5) が与えられる。
3 行目から N 行では、建物の情報が与えられる。このうち i 行目では整数 A_i (1 ≦ A_i ≦10^3) と整数 D_i (1 ≦ D_i ≦10^3) が空白を区切りとして与えられる。

部分点

この問題には部分点が設定されている。

K ≦ 300 かつ N ≦ 300 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
K ≦ 5,000 かつ N ≦ 5,000 を満たすデータセット 2 に正解した場合は、上記とは別に 10 点が与えられる。
K ≦ 10^5 を満たすデータセット 3 に正解した場合は、上記とは別に 15 点が与えられる。
追加制約のないデータセット 4 に正解した場合は、上記とは別に 45 点が与えられる。

出力

K 回増築するのに必要な金額の合計として考えられるものの最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

出力例1

例えば、以下のように増築します。

建物 1 を増築します。現在の建物 1 の価格は 10 なので、増築にかかった金額の合計は 10 となります。また、増築後の建物 1 の価格は 13 になります。
建物 1 を増築します。現在の建物 1 の価格は 13 なので、増築にかかった金額の合計は 23 となります。また、増築後の建物 1 の価格は 16 になります。
建物 2 を増築します。現在の建物 2 の価格は 12 なので、増築にかかった金額の合計は 35 となります。また、増築後の建物 2 の価格は 16 になります。
建物 3 を増築します。現在の建物 3 の価格は 15 なので、増築にかかった金額の合計は 50 となります。また、増築後の建物 3 の価格は 20 になります。

このようにすることで、4 回増築するのにかかる金額を 50 にすることができます。

入力例2

出力例2

建物 1 を 8 回増築します。

D - だいたい最小全域木

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

この世界は 3 次元、すなわち位置を座標で示すためには (x, y, z) と 3 つの数が必要です。今回はそれよりも高次元の 200 次元の世界について考えてみましょう。つまり、ある点の座標は (x_1, x_2, ..., x_{200}) と 200 個の数で表現されるということです。

いま、200 次元空間上に 1 から 5,000 までの異なる番号がつけられた点が 5,000 個あります。これら 5,000 個の点に対して、次の条件を満たすように点どうしを結ぶことを考えます。

どの点からどの別の点に対しても、結ばれた点への移動を繰り返すことで到達することができる。
その移動の際に同じ点を 2 回以上通らないことにすると、移動方法が 1 通りに定まる。

別の言葉でいえば、点たちが木になるように結びたいということです。

そして、コンテストの問題としてお約束っぽいですが、できるだけコストが小さくなるように結ぶことを考えましょう。ここで、2 つの点 (a_1, a_2, ..., a_{200}) と (b_1, b_2, ..., b_{200}) を結ぶコストは次のようにして定まります。

2 つの点の 類似度 を次の式で定めます。（これは「コサイン類似度」と呼ばれているものです）
このとき、2 つの点を結ぶコストは 1 - 類似度 となります。つまり、類似度が高いほどコストが低く、類似度が低いほどコストが高くなります。

全体のコストは、点を結ぶのに要したコストの和で決まります。このとき、できるだけコストが小さくなるように結ぶ方法を求めるプログラムを作成してください。ただし、コストを最小にする必要はなく、出力した結び方のコストが 最小なものの 1.01 倍以内のコストに収まっていれば Accept とします。

入力

入力は以下の形式で標準入力から与えられる。

seed

1 行目には整数 seed (1 ≦ seed ≦ 10^6) が与えられる。

実際の点の座標は、初期化に seed を用いた擬似乱数によって生成する。すべての点の座標の値は -50,000 以上 50,000 以下でかつ 0 ではない整数の中から一様に選ばれる。具体的には次のような擬似コードで座標の値を決める。

x = 123456789
y = 362436069
z = 521288629
w = seed

for i = 1 to 5000
  for j = 1 to 200
    t = x ^ (x << 11)
    x = y
    y = z
    z = w
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))

    v = w % 100000 - 50000
    if v >= 0 then
      v = v + 1

    (i 番目の点の座標の j 番目の値) = v

ここで seed は入力の seed の値である。

また変数 x, y, z, w, t は 32 ビットの符号なし整数型とし、= で代入、^ でビットごとの排他的論理和(XOR)、<< でビット左シフト、>> でビット右シフトを表すとする。

出力

ちょうど 4,999 行出力せよ。各行には 2 つの整数 p, q が書かれていなければならず、これは点 p と点 q を結ぶことを表す。

出力の末尾にも改行をいれること。

入力例1

出力例1

出力は膨大な量になるため記載しませんが、このケースに対する最小のコストは約 3739.378294998 です。

入力例2

出力例2

このケースに対する最小のコストは約 3741.147062644 です。