AHC058 one-shot prompt (green perf)

prompt.txt

あなたは競技プログラミング（ヒューリスティック）の専門家です。

atcoder heuristic contestを一緒に解き、高いスコアを達成しましょう。私が大まかな方針を示し、あなたが実装担当です。あなたからの改善提案はウェルカムです。

＝＝＝

# 知見1

レベルの高い機械を強化すると（同じIDの）下位の機械を生成してくれて、それらのPの積でリンゴが増える。よって、最終的にはどこかのIDに注力するのが良い戦術

＝＝＝

# 方針

## フェーズ0（LV0で金策土台作成）

・原則として、行動候補は「レベル0の機械の強化」のみとする。
・ただし例外として、以下の条件が成立した瞬間に、他の評価を全て無視して
  強制的に次の行動を行う。

【強制遷移条件】
- 現在の所持リンゴで、機械 0^1（i=1, j=0）を強化可能になった場合

【強制行動】
- そのターンの行動は必ず「1 0」とする
- この行動を出力した直後に Phase1 に遷移する

【通常行動（強制条件が成立していない場合のみ）】
- レベル0の機械 j^0 の中から
  評価値 = A[j] / (C[0][j] * (P[0][j] + 1))
  が最大のものを強化する

## フェーズ1（ID＝0で金策土台作成）

機械セットID=0に集中して投資する。
現在所持しているリンゴで強化可能な機械の中から、レベルが最も高いものを優先して強化する。
機械0^3が強化可能になった時、そのターンでは機械0^3を強化し、次のフェーズに移行する

## フェーズ2（ID=Xで本命金策作成）

ここからは機械セットID=Xのみを強化する（機械X^0, 機械X^1, 機械X^2, 機械X^3のみ）。
ID選択方法は後述する。
ID選択は、このフェーズに入った時の一度だけでよい。
現在所持しているリンゴで強化可能な機械の中から、レベルが最も高いものを優先して強化する。
（コスト最小のものを選ぶのではなく、レベルの大きいもの（レベル3が最大）を優先して強化）。

### ID = X の選択方法について

最終的なリンゴ増加は A_j と P_{i,j} の積構造になるため、
レベル0だけでなく全レベルのコストを
「積を作るための投資効率」として評価したいので、
A_iの3乗 / sqrt(Ci^1, Ci^2, Ci^3の積）でよかろう。
（機械0^0に特殊処理がされているので、レベル0はあえて積から除外している）

注力するID=Xは1度決定したら最後まで固定とする。

### レベルの選択方法

ID=Xの4つの機械のPの積が最大化するように投資する。つまり、Pが1番小さいものに投資すればよかろう

## 全フェーズ共通ルール：Pの強化限度の設定

各機械の最大強化のP=100とする。特定のPばかり投資するのは効率が悪いし、より上位レベルに投資するための「待ち」を作るためでもある

## その他

不明点があったら実装前に聞いてね

＝＝＝

言語：CPP

コメント：英語で簡潔に

using ll = long long; 

コードを出力する時は完全版（コンパイル可能なもの）を出力する

入力から与えられる値はすべて変数として宣言する

＝＝＝

# 問題文

（htmlベタ貼りじゃない方がいい場合はおしえて）

<section>
<h3>問題文</h3><p><var>N</var> 種類のIDと <var>L</var> 種類のLevelからなる <var>N \times L</var> 種類の機械が存在し、Levelが <var>i</var>、IDが <var>j</var> の機械を<strong>機械 <var>j^i</var></strong> と呼ぶ（<var>0 \leq i &lt; L,\ 0 \leq j &lt; N</var>）。</p>
<p>機械 <var>j^0</var> の生産能力は <var>A_j</var> である。また、機械 <var>j^i</var> の初期コストは <var>C_{i,j}</var> である。</p>
<p>以下の生産計画の手順に従い、全 <var>T</var> ターン終了時点でのりんごの総数を最大化することが目的である。</p>
<h4>生産計画の手順</h4>
<p>機械 <var>j^i</var> の個数を <var>B_{i,j}</var> とし、計画開始時点ではすべて <var>1</var> である。
また、機械 <var>j^i</var> のパワーを <var>P_{i,j}</var> とし、開始時点ではすべて <var>0</var> である。</p>
<p>計画開始時点でのりんごの数は <var>K</var> である。
各ターンは以下の手順で進行する。</p>
<ol>
<li>あなたは以下の2つの行動のうちいずれか1つを選択する。<ul>
<li>機械 <var>j^i</var> を強化する：りんごを <var>C_{i,j} \times (P_{i,j} + 1)</var> 消費し、<var>P_{i,j}</var> を1増やす。ただし、りんごの数が負になるような強化は行えない。</li>
<li>何もしない。</li>
</ul>
</li>
<li>Level 0, 1, 2, 3 の順に、すべての機械 <var>j^i</var> について以下の処理を行う。<ul>
<li>Level 0 の機械（<var>i = 0</var>）の場合：<ul>
<li>りんごを <var>A_j \times B_{i,j} \times P_{i,j}</var> 増加させる。</li>
</ul>
</li>
<li>Level 1 以上の機械（<var>i \geq 1</var>）の場合：<ul>
<li><var>B_{i-1,j}</var> を <var>B_{i,j} \times P_{i,j}</var> 増加させる。</li>
</ul>
</li>
</ul>
</li>
</ol>
<p>上手に行動を選択し、<var>T</var> ターン終了時点でのりんごの数をできるだけ多くしてほしい。</p>
</section>
</div>

<div class="part">
<section>
<h3>得点</h3><p><var>T</var> ターン後の時点におけるりんごの数を <var>S</var> としたとき、<var>\mathrm{round}(10^5 \times \log_2 S)</var> の得点が得られる。
得点は大きいほど良い。</p>
<p>以下の場合、<span class="label label-warning" data-toggle="tooltip" data-placement="top" title="" data-original-title="不正解">WA</span>となる。</p>
<ul>
<li>りんごの数が <var>0</var> 未満になるような強化を行った場合</li>
<li>存在しない機械のLevelまたはIDを指定した場合</li>
<li>行動回数が <var>T</var> 未満の場合</li>
</ul>
<p>合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。
一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が<span class='label label-warning' data-toggle='tooltip' data-placement='top' title="不正解">WA</span>や<span class='label label-warning' data-toggle='tooltip' data-placement='top' title="実行時間制限超過">TLE</span>となる。
コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。</p>
</section>
</div>

<hr />
<div class="io-style">
<div class="part">
<section>
<h3>入力</h3><p>入力は以下の形式で標準入力から与えられる。</p>
<pre><var>N</var> <var>L</var> <var>T</var> <var>K</var>
<var>A_0</var> <var>A_1</var> <var>\cdots</var> <var>A_{N-1}</var>
<var>C_{0,0}</var> <var>C_{0,1}</var> <var>\cdots</var> <var>C_{0,N-1}</var>
<var>C_{1,0}</var> <var>C_{1,1}</var> <var>\cdots</var> <var>C_{1,N-1}</var>
<var>\vdots</var>
<var>C_{L-1,0}</var> <var>C_{L-1,1}</var> <var>\cdots</var> <var>C_{L-1,N-1}</var>
</pre>
<ul>
<li>1行目には、4つの整数 <var>N, L, T, K</var> が与えられる。<ul>
<li><var>N</var> は機械のIDの種類数であり、<var>N = 10</var> を満たす。</li>
<li><var>L</var> は機械のLevelの種類数であり、<var>L = 4</var> を満たす。</li>
<li><var>T</var> は総ターン数であり、<var>T = 500</var> を満たす。</li>
<li><var>K</var> は計画開始時点のりんごの数であり、<var>K = 1</var> を満たす。</li>
</ul>
</li>
<li>2行目には、Level 0 の機械の生産能力を表す <var>N</var> 個の整数 <var>A_0, A_1, \dots, A_{N-1}</var> が空白区切りで与えられる。<ul>
<li><var>A_j</var> は機械 <var>j^0</var> の生産能力であり、<var>1 \leq A_j \leq 100</var> を満たす。</li>
<li><var>A</var> は昇順にソートされている（<var>A_0 \leq A_1 \leq \cdots \leq A_{N-1}</var>）。</li>
</ul>
</li>
<li>続く <var>L</var> 行には、それぞれ <var>N</var> 個の整数 <var>C_{i,j}</var> が空白区切りで与えられる。<ul>
<li><var>C_{i,j}</var> は機械 <var>j^i</var> の初期コストであり、<var>1 \leq C_{i,j} \leq 1.25 \times 10^{12}</var> を満たす。</li>
</ul>
</li>
</ul>
</section>
</div>

<div class="part">
<section>
<h3>出力</h3><p>ちょうど <var>T</var> 行出力せよ。
各行には、<var>t</var> ターン目（<var>0 \leq t &lt; T</var>）に行う行動を、<var>0</var> ターン目から順に以下の形式で出力すること。</p>
<ul>
<li>機械 <var>j^i</var> を強化する場合</li>
</ul>
<pre><var>i</var> <var>j</var>
</pre>
<ul>
<li>何もしない場合</li>
</ul>
<pre>-1
</pre>
<p>解答プログラムは、<code>#</code> から始まるコメント行を出力に含めても良い。</p>
<p><a href="https://img.atcoder.jp/ahc058/UpvAVdx6.html?lang=ja&seed=0&output=sample">例を見る</a></p>
</section>
</div>

<div class="part">
<section>
<h3>入力生成方法</h3><p><var>L</var> 以上 <var>U</var> 以下の実数値を一様ランダムに生成する関数を <var>\mathrm{rand\_double}(L,U)</var> で表す。</p>
<h4><var>A_j</var> の生成</h4>
<ul>
<li><var>j=0</var> のとき：<var>A_0=1</var></li>
<li><var>j \neq 0</var> のとき：<var>A_j=\mathrm{round}(10^{\mathrm{rand\_double}(0,2)})</var></li>
<li>生成後、<var>A</var> 配列を昇順にソートする</li>
</ul>
<h4><var>C_{i,j}</var> の生成</h4>
<ul>
<li><var>i=0</var> かつ <var>j=0</var> のとき：<var>C_{0,0}=1</var></li>
<li>それ以外のとき：<var>C_{i,j}=\mathrm{round}(A_j \times 500^i \times 10^{\mathrm{rand\_double}(0,2)})</var></li>
</ul>
</section>