/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
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)) だけ満足度が低下する。
得点
提出プログラムが決定したコンテスト日程における、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 (sha256=83dc490c0904b4cbb1d541143bd1a6f478180b94df4f834d5d873330ffa62ad6) を公開
相対評価システムについて
暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最高点の算出においても、順位表に反映されている最終提出のみが用いられる。
順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の得点をそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。
実行時間について
実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。
入出力
まずはじめに、標準入力から以下の形式で日数 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 |
入力生成方法
各 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版
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
Problem Statement
AtCoder currently hosts four types of contests, ABC, ARC, AGC, and AHC. As the number of users has grown, in order to meet the needs of more users, AtCoder has decided to increase the number of contests to 26 types, from AAC to AZC. For convenience, we number these 26 types as type 1 through type 26. For every day, AtCoder will hold exactly one contest, and each contest will end on that day. Please schedule contests so that user satisfaction is as high as possible. The amount of satisfaction increased by holding a contest will depend on various factors, such as the schedule of contests other than AtCoder, etc. Therefore, instead of deciding on the entire schedule in advance, it is necessary to determine it one day at a time.
The satisfaction is calculated as follows.
- The satisfaction at the beginning of day 1 is 0. Satisfaction can take negative values.
- Holding contests increases satisfaction. The amount of increase will vary depending on a variety of factors, such as the schedule of contests other than AtCoder, the day of the week, and so on. Holding a contest of type i on day d will increase the satisfaction by s_{d,i}. The value s_{d,i} is only revealed at the time of determining the contest to be held on day d, so when determining the contest on day d, the value of s_{d',i} is unknown for day d'\geq d+1.
- If a particular type of contest is not held for a while, the satisfaction decreases. Each contest type i has an integer c_i, and at the end of each day d=1,2,...,D, the satisfaction decreases as follows. Let \mathrm{last}(d,i) be the last day before day d (including d) on which a contest of type i was held. If contests of type i have never been held yet, we define \mathrm{last}(d,i)=0. At the end of day d, the satisfaction decreases by \sum _{i=1}^{26}c_i \times (d-\mathrm{last}(d,i)).
Scoring
Let S be the satisfaction at the end of day D in the contest schedule determined by the submitted program. Let B be the satisfaction at the end of day D in the baseline schedule that holds a contest of type ((d-1)\% 26) + 1 on day d (1\leq d\leq D). Here, (d-1)\% 26 denotes the remainder of dividing (d-1) by 26. Then, you will obtain a score of \max(S-B+1, 0).
For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}), where YOUR is your score and MAX is the maximum score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.
The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MAX calculation for those test cases.
The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.
Number of test cases
- Provisional test: 50
- System test: 1000. We will publish seeds.txt (sha256=83dc490c0904b4cbb1d541143bd1a6f478180b94df4f834d5d873330ffa62ad6) after the contest is over.
About relative evaluation system
In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MAX for each test case when calculating the relative scores.
The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the evaluation value for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.
About execution time
Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.
Input and Output
First, the number of days D and the rate of decrease in satisfaction c_i for each contest type i are given from Standard Input in the following format.
D
c_1 c_2 \cdots c_{26}
For all test cases, D = 365 is fixed and each c_i is an integer satisfying 0\leq c_i \leq 100.
After reading the above information, repeat the following process D times.
In the d-th process (1\leq d\leq D), the satisfaction s_{d,i} obtained by holding a contest of type i on day d is given from Standard Input in the following format.
s_{d,1} s_{d,2} \cdots s_{d,26}
Each s_{d,i} is an integer satisfying 0\leq s_{d,i} \leq 100000.
After reading the above information, output the contest type t_d (1\leq t_d\leq 26) to be held on day d to Standard Output in a single line. The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE. Note that the input for day d+1 will not be given until you output t_d.
Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines at the corresponding timing, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.
Example
| d | Input | Output |
|---|---|---|
| Prior information | 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 |
Input Generation
Each c_i is generated by \mathrm{rand}(0,100). For each i, the mean \mu_i and the standard deviation \sigma_i are generated by \mu_i=\mathrm{rand}(10000,20000) and \sigma_i=\mathrm{rand}(2000,8000). Using these values, each s_{d,i} is generated by \min(\max(\mathrm{round}(\mathrm{normal}(\mu_i,\sigma_i)), 0), 100000).
Tools (Input generator and visualizer)
- Web version
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.