AT_newjudge_2308_heuristic_a AtCoder Contest Scheduling (Online Version)

AtCoderでは現在ABC、ARC、AGC、AHCの4種類のコンテストを開催している。 ユーザー数が増えてきたので、より多くのニーズに応えるために、コンテストの種類をAACからAZCまでの26種類に増やすことにした。 便宜上、26種類のコンテストをタイプ1からタイプ26と番号付ける。 毎日ちょうど一つのコンテストを開催し、各コンテストはその日のうちに終了する。 ユーザーの満足度が出来るだけ高くなるように、コンテストの日程を決めたい。 **コンテストを開催することで得られる満足度は、AtCoder以外のコンテストの開催状況等により変化するため、予め全ての日程を決めるのではなく、順次決定していく必要がある。** 満足度は以下のように算出される。 - 1日目の開始時点における満足度は0である。満足度は負の値も取り得る。 - コンテストを開催することで満足度は増加するが、AtCoder以外のコンテストの開催状況や、曜日など、様々な要因によりその増加量は変動する。 $ d $ 日目にタイプ $ i $ のコンテストを開催すると $ s_{d,i} $ だけ満足度が増加する。**この値 $ s_{d,i} $ は $ d $ 日目に開催するコンテストを決定するタイミングになって初めて明かされるため、 $ d $ 日目のコンテストを決定する際には、 $ d'\geq d+1 $ 日目について $ s_{d',i} $ の値は不明である。** - しばらく特定のタイプのコンテストが開催されないと、満足度が下がってしまう。コンテストのタイプ $ i $ ごとに満足度の下がりやすさ $ c_i $ が定まっており、各 $ d=1,2,...,D $ 日目の終わりに以下のように満足度が低下する。 $ d $ 日目以前( $ d $ 日目を含む)にタイプ $ i $ のコンテストを開催した最後の日を $ \mathrm{last}(d,i) $ とする。ただし、まだ一度もタイプ $ i $ のコンテストを開催していない場合は $ \mathrm{last}(d,i)=0 $ とする。 $ d $ 日目の終わりに、 $ \sum _{i=1}^{26}c_i \times (d-\mathrm{last}(d,i)) $ だけ満足度が低下する。 ### Input & Output Format まずはじめに、標準入力から以下の形式で日数 $ D $ とコンテストのタイプ $ i $ ごとの満足度の下がりやすさ $ c_i $ が与えられる。 > $ D $ $ c_1 $ $ c_2 $ $ \cdots $ $ c_{26} $ 全てのテストケースで $ D = 365 $ で固定であり、各 $ c_i $ は $ 0\leq c_i \leq 100 $ を満たす整数値である。 上記の情報を読み込んだら、以下の処理を $ D $ 回繰り返す。 $ d(1\leq d\leq D) $ 回目の処理ではまず、標準入力から $ d $ 日目にタイプ $ i $ のコンテストを開催することで得られる満足度 $ s_{d,i} $ が以下の形式で与えられる。 > $ s_{d,1} $ $ s_{d,2} $ $ \cdots $ $ s_{d,26} $ 各 $ s_{d,i} $ は $ 0\leq s_{d,i} \leq 100000 $ を満たす整数値である。 $ s_{d,i} $ の情報を読み込んだら、 $ d $ 日目に開催するコンテストタイプ $ t_d $ ( $ 1\leq t_d\leq 26 $ ) を一行で標準出力に出力せよ。 **出力の後には改行をし、更に標準出力を flush しなければならない。** そうしない場合、TLEとなる可能性がある。 **$ d $ 日目の出力するまで、 $ d+1 $ 日目の入力は与えられないので注意せよ。** 解答プログラムは、# から始まるコメント行を出力に含めても良い。 Web版ビジュアライザを使用すると、コメント行を対応するタイミングで表示出来るため、デバッグや考察等に役立てることが出来る。 ジャッジプログラムはコメント行を全て無視するため、コメント行を出力するプログラムをそのまま提出可能である。 #### 例 $ d $ Input Output 事前情報 > 365 2 99 18 $ \cdots $ 24 1 > 20704 21183 16332 $ \cdots $ 9433 ``` 1 ``` 2 > 9611 17267 13088 $ \cdots $ 11234 ``` 2 ``` $ \vdots $ 365 > 14903 15204 7889 $ \cdots $ 10388 ``` 1 ``` [例を見る](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91.html?lang=ja&seed=0)

N/A

N/A

### 得点 提出プログラムが決定したコンテスト日程における、 $ D $ 日目終了時点での満足度を $ S $ とする。 $ d (1\leq d\leq D) $ 日目にコンテストタイプ $ ((d-1)\% 26) + 1 $ のコンテストを開催するとした日程における、 $ D $ 日目終了時点での満足度をベースライン $ B $ とする。 ここで、 $ (d-1)\% 26 $ は $ (d-1) $ を 26 で割った余りを表す。 このとき、 $ \max(S-B+1, 0) $ の得点が得られる。 各テストケース毎に、 $ \mathrm{round}(10^9\times \frac{自身の得点}{全参加者中の最高点}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。 最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、不正な出力や制限時間超過をした場合、そのテストケースのみ0点となる。 システムテストは **CE 以外の結果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50個 - システムテスト: 1000個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/newjudge-2308-heuristic/seeds.txt) (sha256=83dc490c0904b4cbb1d541143bd1a6f478180b94df4f834d5d873330ffa62ad6) を公開 #### 相対評価システムについて 暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最高点の算出においても、順位表に反映されている最終提出のみが用いられる。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の得点をそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。 #### 実行時間について 実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数を $ \mathrm{rand}(L,U) $ 、 平均 $ \mu $ 標準偏差 $ \sigma $ の正規分布から実数値をランダムに生成する関数を $ \mathrm{normal}(\mu,\sigma) $ と表す。 各 $ c_i $ は $ \mathrm{rand}(0,100) $ により生成する。 各 $ i $ について、平均 $ \mu_i $ と標準偏差 $ \sigma_i $ を $ \mu_i=\mathrm{rand}(10000,20000) $ 、 $ \sigma_i=\mathrm{rand}(2000,8000) $ により生成する。 これらを用いて、各 $ s_{d,i} $ は $ \min(\max(\mathrm{round}(\mathrm{normal}(\mu_i,\sigma_i)), 0), 100000) $ と生成する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91.html?lang=ja) - [ローカル版](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。