Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
Xの会社では毎週巨大モニターを用いてゲーム大会が行われます。
次回の大会では「モノス」という発売されたばかりのパズルゲームが使用される予定です。
モノスのルールは次のように定義されています。
- 幅 W 列、高さ無限段のグリッド状のフィールドを用いる。列には左から順に 0, 1, ..., W-1 と番号が振られている。
- 1 \times 1 の正方形のブロック「モノミノ」がフィールド上方から1個ずつ、全部で N 個落下してくる。
- モノミノには色と価値が決められている。色は全部で K 種類あり、 0 以上 K-1 以下の整数で表される。また、価値は 1 以上 V 以下の整数である。
- ゲーム開始時に、そのゲームで出現するモノミノの情報が全て明かされる。 i 番目に落下してくるモノミノの色は c_{i} 、価値は v_{i} である。
- プレイヤーはモノミノを落とす列を指定し、モノミノを落下させる。
- モノミノはフィールド最下段、または他のモノミノの上に着地するとその位置に固定される。そして新しいモノミノが出現する。
- フィールドのある段が全てモノミノで埋め尽くされると、その段の得点が得られる。得点は次のように決まる。
- その段に配置されたモノミノの色別の価値の合計を求める。
- 色別の価値の合計のうち最大のものを得点として得る。
- 全てのモノミノを落下させた時点での得点の合計がそのゲームの得点となる。
何が何でもゲーム大会で優勝したいXの代わりに、モノスにおいてできるだけ高得点を取るAIを作成し、Xを優勝へ導いてあげてください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、各段で得られる得点の合計がそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N W K V
c_{0} v_{0}
\(\vdots\)
c_{i} v_{i}
\(\vdots\)
c_{N-1} v_{N-1}
- N は出現するモノミノの数を表す整数で、 N=1000 を満たします。
- W は使用するフィールドの幅を表す整数で、 W=8 を満たします。
- K は出現するモノミノの色の種類の数を表す整数で、 K=6 を満たします。
- V は出現するモノミノの価値の最大値を表す整数で、 V=8 を満たします。
- c_{i} は i 番目に出現するモノミノの色を表す整数で、 0≤c_{i}≤K-1 を満たします。
- v_{i} は i 番目に出現するモノミノの価値を表す整数で、 1≤v_{i} ≤V を満たします。
出力
i 行目に、 i 番目のモノミノを落とす列 col_{i} (0 \le col_{i} \le W-1)を出力してください。
col_{0}
\(\vdots\)
col_{i}
\(\vdots\)
col_{N-1}
テストケースの生成について
モノミノの色と価値は一様ランダムに生成されています。
入力例1
7 3 2 3 0 2 1 3 0 1 0 3 0 2 1 2 0 3
注意: この入力はテストケースとしての制約を満たしていません。
出力例1
0 0 0 1 2 1 2
1段目は色 0 のモノミノの価値合計が 7 になるため得点 7 を得ます。
2段目は色 0 のモノミノの価値合計が 3 、色 1 のモノミノの価値合計が 5 であるため得点 5 を得ます。
3段目は色 0 のモノミノの価値合計が 1 になりますがその段全てにモノミノが埋め尽くされていないため得点は得られません。
そのためこの出力例で得られる得点は 7+5+0 で 12 点となります。
フィールドをビジュアライズした結果を以下に図示します。
各段の右にその段で得られる得点が表示されています。
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
イラストレーターのXは、不思議なペンを使って絵を描きます。このペンから出る色は、1秒ごとに赤色 → 青色 → 緑色 → 黄色 の順に繰り返し変わります。
下の画像は、Xがこれから描こうとしている絵の計画の例です。
Xは以下の手順で絵を描きます。
- （1）絵を描く紙をN 行 N 列のグリッドに区切ります。上から i 行目、左から j 列目のセルを (i, j) と表します。それぞれのセルについて、ペンのどの色で塗りたいかを計画します。
- （2）四隅のセルに色を塗ります。(0, 0) を赤色に、(0, N-1) を青色に、(N-1, 0) を緑色に、(N-1, N-1) を黄色に塗ります。それ以外のセルには色が塗られていません。
- （3）M 秒間の間、1秒ごとに以下のいずれかを選んで実行します。初回はペンを使うと赤色で塗ることができます。
- 線を塗る: ペンを使って色を塗ります。今から塗ろうとしている色と同じ色のセルを選び、そこから上下左右のいずれかの方向に 5 つ色を塗ります。
- たとえば、(r,c)から上方向に塗った場合、(r-1,c) から (r-5,c) までを塗ります。
- ただし、グリッドからはみでる部分に関しては塗りません。
- 塗ろうとしたセルに既に色が塗られている場合、古い色は消えて、塗ろうとしている色で上書きされます。
- 何もしない: 次の色に切り替わるのを待ちます。
Xは絵を描く手順の（1）と（2）を終えて、まさに（3）を始めようとしているところです。各セルをどの色で塗る計画かが決められている状態で、うまく塗ることでXの計画通りに着色されたセルの個数を最大化してください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、Xの計画通りに着色されたセルの個数がそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
\(\begin{array}{lll}
N ~ M & & \\
A_{ 0,0 } & \ldots & A_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
A_{ N-1,0 } & \ldots & A_{ N-1,N-1 }
\end{array}\)
- N は絵を描く紙の大きさを表す整数で、N = 50 を満たします。
- M はXが手順（3）で定められた操作を実行する回数で、M = 500 を満たします。
- A_{i,j} は i 行 j 列目にXが塗りたい色を表し、 0 ≤ A_{i,j} ≤ 3 を満たします。 A_{i,j} が 0 なら赤色に、 1 なら青色に、 2 なら緑色に、 3 なら黄色に塗りたいことを表します。
- A_{0,0} = 0 , A_{0,N-1} = 1 , A_{N-1,0} = 2 , A_{N-1,N-1} = 3 を満たします。
出力
M 行出力してください。上から順に、実行する操作を出力してください。
- 線を塗る場合、選択したセルの位置 (r,c) （ 0 ≤ r,c ≤ N-1 ）と、塗る方向を表す文字を
UDLR（それぞれ上下左右に対応します）の中からひとつ、スペース区切りで出力してください。選択したセルの色がこれから塗ろうとしている色と一致しない場合、 となります。 - 何もしない場合、
-1と出力してください。
テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
Xの絵の計画の例として挙げた画像は seed = 1, 2, 3 の例です。
テストケースジェネレータは以下の手順でケースを生成します。厳密にはテスターの実装を見てください。説明・実装ともに、必ずしも目を通す必要はありません。
- まず、グリッドのセルおよび生成時に使われるリストを以下のように初期化します。
- 最初、全てのセルは色が塗られていません。
- 四隅を着色します。 (0, 0) を赤色に、(0, N-1) を青色に、(N-1, 0) を緑色に、(N-1, N-1) を黄色に塗ります。
- 各色について、まだ色が塗られていないセルをランダムに 3 から 10 マス選び、着色します。
- 着色された各セル (i, j) をピックアップし、そこから上下左右のセルについて、 (i, j) の色とセルの座標をペアにしたものをリストに追加します。
- 次に、リストが空になるまで以下の操作を繰り返し、グリッドに色を塗っていきます。
- リストからランダムにペアを取り出し、ペアのセルが既に塗られているならスキップします。そうでなければセルをペアの色で塗った後、塗った色と四近傍のセルを先ほど同様にリストに追加します。
- 最後に、グリッドが以下の条件を満たすかチェックします。条件を満たさない場合、このケースの生成を最初からやり直します。
- 出力が満たす条件: 各色のセルの数が \( \lfloor N ^ 2 / 6 \rfloor \) 個以上であること。
入力例
7 8 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 2 2 2 2 2 1 1 2 2 2 2 3 1 1 2 2 2 3 3 3 3 2 2 3 3 3 3 3このケースは説明用のもので、入力の制約を満たしていません。
出力例
0 0 R 0 6 L 6 0 R 6 6 D -1 0 2 D 6 3 R -1
- (0, 0) を起点に、 (0, 1) から右に (0, 5) までを赤色で塗ります。
- (0, 6) を起点に、 (0, 5) から左に (0, 1) までを青色で塗ります。既に赤色で塗った部分も上塗りされます。
- (6, 0) を起点に、 (6, 1) から右に (6, 5) までを緑色で塗ります。
- (6, 6) を起点に下を黄色で塗ろうとしますが、グリッドからはみでるため、どこも塗られません。
- 赤色で塗る番ですが、何もしないこともできます。
- (0, 2) を起点に、 (1, 2) から下に (5, 2) までを青色で塗ります。
- (6, 3) を起点に、 (6, 4) から右に (6, 6) までを緑色で塗ります。グリッドからはみでる部分は塗られません。
- 黄色く塗られたセルが存在しないため、黄色ではどこも塗ることができず、何もできません。
- 計画通りに塗られたセルは7個のため、7点を獲得します。
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。