A - ぐるぐる庭園

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

妖精研究家のXは、とある庭園に出現する虹色に光り輝く妖精の研究に長年打ち込んでいます。
妖精は毎夜、庭園のある場所に出現し、別のある場所へと最短経路で飛んでいき、そこで消えるという習性を持っていることがわかっています。
長年の研究の結果、妖精の出現パターンを完璧に予想できるようになったXは、今度はできるだけ長い時間妖精を観察したいと考えています。
具体的には庭園に壁を作ったり壊したりして妖精の移動経路を操作し、後述の満足度をできるだけ大きくしようとしています。
ただし、1日に1つの壁しか作ったり壊したりできないため、Xはすぐれた作業計画を考えようとしています。

Xが行おうとしている妖精の観察は以下のような条件になっています。

  • 妖精の出現する庭園は N × N のグリッドからなっており、グリッドの各セルは空か壁のどちらかである。
    • 上から r 行目、左から c 列目のセルを (r,\ c) と表す。( 0 ≤ r,\ c < N )
  • 初期状態ではすべてのセルは空である。また、満足度は 0 である。
  • 妖精の観察は K 日間行い、各日に作業と満足度の計算を以下の順番で行う。
    1. 任意のセルを1つ選んでそのセルが空だったら壁に、壁だったら空に変化させる。もしくはなにもしない。セルの状態は次の日以降も引き継がれる。
    2. 妖精の出現するセル (a_{i},\ b_{i}) から消えるセル (c_{i},\ d_{i}) まで、妖精が空のセルだけを上下左右に1セルずつ辿って到達する経路があれば、その最短経路の (出現するセルと消えるセルを含めて通過したセルの数\ -\ 1)^2 を満足度として加える。
      • 到達できない場合は妖精は出現せず、満足度は変化しない。
      • (a_{i},\ b_{i}) と (c_{i},\ d_{i}) の少なくとも一方が壁の場合は妖精は出現せず、満足度は変化しない。
      • 妖精はグリッドの外を通過できない。

ところがXは妖精の研究は得意でも計算は得意でないため、どんな作業計画を立てればよいかわからず途方にくれています。
そこでXの頼れる友人であるあなたが、Xの代わりに満足度を最大化するための作業計画を立ててあげてください。

各テストケースの得点およびこの問題の得点は、次のように計算されます。

  • 1つのテストケースでは、(最終日の満足度/10000) の小数点以下を切り上げた整数が得点になります。
  • テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力

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

N K
a_{0} b_{0} c_{0} d_{0}
:
a_{K-1} b_{K-1} c_{K-1} d_{K-1}
  • N はグリッドの1辺の長さを表す整数で、N = 40 を満たします。
  • K は妖精の観察日数を表す整数で、K = 1000 を満たします。
  • (a_{i},\ b_{i}),\ (c_{i},\ d_{i}) はそれぞれ妖精が i 日目に出現するセルと消えるセルを表します。
    • 0 ≤ a_{i},\ b_{i},\ c_{i},\ d_{i} < N
    • (a_{i},\ b_{i}) ≠ (c_{i},\ d_{i})

出力

各日に作業するセルの座標 (y,\ x) をスペース区切りで順番に1行ずつ、合計 K 行出力してください。
どのセルでも作業しない場合は -1 -1 と出力してください。 

y_{0} x_{0}
:
y_{K-1} x_{K-1}
  • 出力が K 行でない場合やグリッドの範囲外の座標があった場合は WA (Wrong Answer) になります。

テストケースの生成について

各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータは一様乱数にしたがってケースを生成しています。
テストケースジェネレータはページ下部のリンクより提供しています。

入力例1

5 4
0 1 4 4
2 2 2 3
0 4 4 0
0 0 4 0

注意: この入力はテストケースとしての制約を満たしていません。

出力例1

3 0
-1 -1
4 1
4 1

出力された操作に基づいた各日の庭園の状態と妖精の飛行経路は以下のようになります。

　　

2日目は妖精の出現するセルから消えるセルまで到達できないので、妖精は出現せず、満足度は変化しません。
このテストケースの得点は最終日の満足度 86 を 10000 で割って切り上げした値なので 1 になります。
（画像中のSとGはそれぞれ妖精の出現するセルと消えるセルを表しています）

ジェネレータとテスター

テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。

ジェネレータ・テスター

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

  • このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
  • このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
  • このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ

fps
距離
距離2
描画内容を画像として保存
B - くるくる寿司

Time Limit: 15 sec / Memory Limit: 1024 MB

背景

Xはある回転寿司屋で一人で寿司を握っています。

今日はXの知人Q人が、回転寿司屋に訪れて食事をします。Xは知人の顔を知らず、さらに客が見えない場所にいますが、知人はSNSに自分の食べる寿司の写真を逐一アップロードするので、Xはそれを見ることで、知人の座っている席をだいたい特定したいと考えました。知人はM回写真をアップロードします。

Xは、特定したい知人に関係無く、決まった長さNの寿司の列を流し続けます。i番目の知人が着席した瞬間、その目の前には寿司列のstart_i番目の寿司が来るとします(この寿司を知人が取るとは限りません)。

また、Xはすでにいる他の客を何人か追い出すことで、それぞれの寿司が知人によって取られる確率を操作することができます。

もちろん客を追い出すと店の評判が落ちるので、寿司列をうまく決め、できるだけ評判が落ちないように知人の位置を特定してください。

問題文

この問題はインタラクティブです。Nが与えられるので、長さNの文字列Sと、実数Dを決めてください。ジャッジはS,\ DからQ個のクエリq_iを生成します。 i番目のクエリに対し、ジャッジがstart_iを、0以上N未満の整数から一様乱数にしたがって選びます。このとき文字列q_iは以下の擬似コードにより決定されます。 

q_i = ""
for (pos = start_i; q_i.length < M; pos++)
    確率 1.0 / D で、q_i の末尾に S[pos \% N] を付け足す
return q_i

各iについてstart_iを推定してください。

各テストケースの得点および、この問題の得点は、次のように計算されます。

  • 各iについて、start_iの推定値をguess_iとしたとき、スコアscore_iは以下の数式により計算されます。 \begin{aligned} distance_i &= \min\left(\left| guess_i-start_i\right|, N-\left| guess_i-start_i\right|\right),\\ score_i &= \sqrt{D} * \exp(-distance_i^2/25.0)\end{aligned}
    • y=exp(-x^2/25)は以下のようなグラフになります。
      y=exp(-x^2/25)
  • 1個のテストケースの得点は、各iのスコアの合計を小数点以下切り上げした値になります。
  • テストケースは全部で10個あります。各テストケースの得点の合計が、この問題の得点になります。
  • なお、スコアの計算に用いられる変数は64ビットの浮動小数点数表現なので、微小な誤差が発生することをご理解ください。

入出力

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

初めに、以下のような入力が与えられます。

N M Q
  • N はSの文字数を表す整数で、N = 3000 を満たします。
  • M はq_iの文字数を表す整数で、M = 7 を満たします。
  • Q はクエリの個数を表す整数で、Q = 30000 を満たします。

この入力に対し、SとDを以下の形式で出力してください。

S
D
  • Sは長さNの文字列で、半角英小文字からなります。
  • Dは1.0以上10.0以下の実数です。

その後、以下のような入力が与えられます。

q_0
q_1
：
q_{Q-1}
  • q_i は、M文字の文字列です。

各q_iに対し、guess_iを以下の形式で出力してください。

guess_0
guess_1
：
guess_{Q-1}
  • guess_i は、0≤ guess_i< N を満たす整数です。
  • 出力を終えたら、プログラムを終了してください。
  • 出力の後には必ず改行し、flush してください。
  • ジャッジプログラムの都合上、Q個のq_iをすべて読み取った後にguess_iの出力を始めてください。

入出力例

プログラムへの入力 プログラムの出力 説明 
13 7 2
N=13,\ M=7,\ Q=2が与えられます。この値はテストケースの制約を満たさないことに注意してください。 
nosushinolife
1.8
S=nosushinolife,\ D=1.8を出力します。Sの文字数はN=13です。 
osushin
nolifos
q_0,\ q_1が生成され、与えられます。長さはそれぞれM=7です。 
1
7

guess_0,\ guess_1 を出力します。これらは0以上N未満でなければなりません。

start_0=1,\ start_1=0であった場合、スコアは、

distance_0 = min(abs(1-1),\ N - abs(1-1)) = 0,

score_0 = sqrt(D) * exp(-0^2/25.0)≒1.341641,

distance_1 = min(abs(7-0),\ N - abs(7-0)) = 6,

score_1 = sqrt(D) * exp(-6^2/25.0)≒0.317872

のように計算され、このケースの得点は、

score_0 + score_1≒1.659513を小数点以下切り上げして2点となります。

テスター

テスターを次のリンクから提供しています。

テスター