問題一覧 > スコア問題

No.5016 Worst Mayor

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 46
作問者 : e869120e869120 / テスター : butsurizukibutsurizuki trineutrontrineutron
2 ProblemId : 9554 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-29 13:50:15

問題文

KYOPRO 市は縦 $14$ 行，横 $14$ 列の正方形状の都市である。
北から $i$ 行目，西から $j$ 列目の区画には $(i, j)$ という番号が付いており，東西南北に隣接する区画の間は道路で繋がっている。
つまり，KYOPRO 市の構造は下図のようになっている。

また，KYOPRO 市には $N$ 人の市民が住んでおり，それぞれ $1$ から $N$ までの番号が付けられている。
市民 $k$ の家は区画 $(A_k, B_k)$，会社は区画 $(C_k, D_k)$ にある。

最初，KYOPRO 市に建設されている道路はすべて一般道であり，一本の道路を通るのに $1$ 分かかってしまう。
そこで市長である太郎君は，いくつかの道路を高速道路 ($0.223$ 分で通れる) にアップグレードすることで，移動時間を短縮しようと考えた。

具体的には，彼は残りの任期 $T$ 日間にわたって，毎日以下の行動を順に行う。
ただし，彼が最初に持っている資金は $10^6$ 円であり，協力者数は $1$ 人である。

  1. 以下のいずれかの行動を選ぶ
    • 高速道路の建設：区画 $(x, y)$ と $(z, w)$ を結ぶ道路を高速道路にする。$\lfloor 10^7 \div \sqrt{[協力者数]} \rfloor$ 円かかる
    • 協力者を集める：協力者が $1$ 人増える
    • 資金集めをする：所持金が $50000$ 円増える
  2. 高速道路の収益を受け取る
    • 高速道路を一本通るのに $30$ 円かかり，各市民は必ず最短の時間で通勤を行う
    • そのため，市民 $k$ ($1 \leqq k \leqq N$) の家から会社までの最短ルートにおける高速道路の本数を $s_k$ とすると，$60(s_1 + \cdots + s_N)$ 円受け取る

太郎君の真のゴールは，市を便利にすることでも市の財政を健全化させることでもなく金儲けをすることであるため，最終的な所持金をできるだけ多くしたい。
最終的な所持金をできるだけ多くするような太郎君の行動を出力せよ。

諸注意

各市民がステップ 2. で通るルートとしては様々なものが考えられるが，
最短時間のルートで移動したときに通る高速道路の本数は，本問題の制約下では一意であることに注意せよ。

たとえば以下の画像の黄色が高速道路であるとき，S から T に最短時間 ($4.338$ 分) で移動する方法は $2$ 通りあるが，
どちらも高速道路を $6$ 本通っているという点では変わらない。


入出力

本問題はインタラクティブ問題である。通常の問題とは入出力形式が異なることに注意せよ。

まず，最初に以下の形式で $N+1$ 行にわたって入力が受け取らなければならない。 

$N$ $T$
$A_1$ $B_1$ $C_1$ $D_1$
$A_2$ $B_2$ $C_2$ $D_2$
 $:$
$A_N$ $B_N$ $C_N$ $D_N$

次に，$T$ 回にわたって (あ) と (い) をその順に繰り返す。

(あ) 現在の所持金を $u$，現在の協力者数を $v$ とするとき，以下の形式で入力を受け取らなければならない。 

$u$ $v$

(い) 太郎君の行動を出力する。
もし区画 $(x, y)$ と区画 $(z, w)$ を結ぶ高速道路を建設する場合，以下の形式で出力を行う。
$|x - z| + |y - w| = 1$ を満たす必要があることに注意すること。 

$1$ $x$ $y$ $z$ $w$

もし協力者集めを行う場合，以下の形式で出力を行う。 

$2$

もし資金集めを行う場合，以下の形式で出力を行う。 

$3$

制約

  • $N=3000$
  • $T=400$
  • $1 \leqq A_k, B_k, C_k, D_k \leqq 14$ ($1 \leqq k \leqq N$)
  • $(A_k, B_k) = (C_k, D_k)$ になる場合もあることに注意せよ

採点方法

最終的な太郎君の所持金がそのまま得点となる。たとえば最終的な所持金が $5$ 億円である場合，$5$ 億点が得られる。
ただし，出力が不正である場合は WA と判定される。不正な出力とは以下を指す。

  • 出力形式に従わなかった
  • 資金が足りないのに高速道路を建設してしまった
  • 区画 $(x, y)$ と区画 $(z, w)$ を結ぶ高速道路を建設しようとしたが，$|x-z| + |y-w| = 1$ を満たさなかった
  • 区画 $(x, y)$ と区画 $(z, w)$ を結ぶ高速道路を建設しようとしたが，$1 \leqq x, y, z, w \leqq 14$ を満たさなかった

もし途中で不正な出力をしてしまった場合，次のターンでは入出力の項の (あ) で -1 -1 という入力を受け取ることになるので，直ちにプログラムを終了せよ。
もしプログラムを終了しなかった場合，採点結果は TLE や RE などの他のエラーになる可能性もある。
なお，既に高速道路を建設した場所に高速道路を建設しようとしても不正解にはならないが，無駄であることに注意せよ。

テストケースは全部で $50$ 個あり，全テストケースの得点の合計が提出の得点となる。
コンテスト時間中に得た最高得点で最終順位が決定され，コンテスト終了後のシステムテストは行われない。

サンプルコード / ヒント

ヒューリスティック初心者は，この項目を読むことをお勧めする。

まず，インタラクティブ問題に慣れていない方のために，C++ と Python のサンプルコードを以下に示す。
このプログラムは，すべての日について資金集めを行うものとなっている。

また，この問題では入力として「現在の資金」および「現在の協力者数」を受け取ることができるため，
必ずしも「高速道路の収益が何円なのか」を手元で計算する必要はないことに注意せよ。

テストケース生成方法

この項目は問題の理解に必須ではないことに注意せよ。

テストケースは以下のような方法で生成される。

  1. 各 $(p, q)$ ($1 \leqq p \leqq 14, 1 \leqq q \leqq 14$) に対して，平均 $0$，標準偏差 $1$ に従う乱数 $e_{p, q}$ を生成する
  2. 各 $k$ ($1 \leqq k \leqq N$) に対して，$(A_k, B_k)$ を生成する。$(A_k, B_k) = (p, q)$ になる確率は $3^{e_{p,q}}$ に比例する
  3. 各 $k$ ($1 \leqq k \leqq N$) に対して，$(C_k, D_k)$ を生成する。$(C_k, D_k) = (p, q)$ になる確率は $3^{e_{p,q}}$ に比例する

サンプル

このサンプルは制約と違って $N=5, T=4$ であり，最初の所持金も $2000$ 万円になっていることに注意せよ。

サンプル1
プログラムからの入力 プログラムの出力
5 4
1 1 14 14
2 2 13 13
3 3 12 12
4 4 11 11
5 5 10 10
20000000 1
2
20000000 2
3
20050000 2
1 4 4 5 4
12979173 2
3

最終的なスコアは $13,029,413$ 点となる。
なお，市民 $1, 2, 3, 4$ は通勤の際に $3$ ターン目で建設した高速道路を通るので，
4 ターン目開始時の所持金は $20,050,000 - \lfloor 10,000,000 \div \sqrt{2} \rfloor + (60 \times 4) = 12,979,173$ 円になっている。

サンプル2
プログラムからの入力 プログラムの出力
5 4
1 1 14 14
2 2 13 13
3 3 12 12
4 4 11 11
5 5 10 10
20000000 1
4
-1 -1

ユーザーが不正な出力をした場合，-1 -1という入力が受け取られることに注意せよ。
なお，テストケース自体はサンプル 1 と同様である。

その他のサンプル

制約を満たすテストケースの例を以下に示す。入力が $N, T, A_k, B_k, C_k, D_k$ のみであることに注意すること。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。