AT_ahc040_a [AHC040A] Packing Uncertain Rectangles

Description

[problemUrl]: https://atcoder.jp/contests/ahc040/tasks/ahc040_a $ N $ 個の長方形が与えられる。 $ i $ 番目の長方形の大きさは、横幅 $ w_i $ と縦幅 $ h_i $ である。入力として、それぞれの値に計測誤差が乗った観測値 $ w'_i=\mathrm{normal}(w_i,\ \sigma) $ と $ h'_i=\mathrm{normal}(h_i,\ \sigma) $ が与えられる。ここで、$ \mathrm{normal}(\mu,\ \sigma) $ は次の手順で値を生成する関数である。 1. 平均 $ \mu $、標準偏差 $ \sigma $ の正規分布からランダムに値を生成する。 2. 生成した値を四捨五入し、整数に変換する。 3. 値が $ 1 $ 未満の場合は $ 1 $ とし、$ 10^9 $ を超える場合は $ 10^9 $ とする。これらの長方形を、平面上で互いに重ならないように番号順に配置する。長方形は必要に応じて $ 90^\circ $ 回転させ、横幅と縦幅を入れ替えることができる。右方向に $ x $ 軸を、下方向に $ y $ 軸を取る。長方形は $ x\ \geq\ 0 $ かつ $ y\ \geq\ 0 $ の領域に配置することができる。配置方法は以下のような列 $ (p_0,\ r_0,\ d_0,\ b_0),\ (p_1,\ r_1,\ d_1,\ b_1),\ \dots $ として指定する。 - $ p_i $ は $ i $ 番目に配置する長方形の番号 ($ 0\ \leq\ p_i\ \leq\ N-1 $) を表す。**一部の長方形だけを配置することもできるが、番号は昇順に並んでいなければならず、すべての $ i\ $ W' $ $ H' $ **出力の後には改行をし、更に標準出力を flush しなければならない。** そうしない場合、TLEとなる可能性がある。解答プログラムは、# から始まるコメント行を出力に含めても良い。 Web版ビジュアライザを使用すると、コメント行を対応するタイミングで表示出来るため、デバッグや考察等に役立てることが出来る。ジャッジプログラムはコメント行を全て無視するため、コメント行を出力するプログラムをそのまま提出可能である。 #### 例 $ t $ Output Input 事前情報 ``` 4 3 1000 77685 46130 32459 75368 54192 88183 60740 42948 ``` 1 ``` 2 0 0 U -1 1 1 U 0 ``` ``` 153220 47195 ``` 2 ``` 4 0 0 U -1 1 1 L -1 2 1 L 1 3 0 U -1 ``` ``` 167543 86611 ``` 3 ``` 4 0 0 U -1 1 0 L -1 2 0 U -1 3 0 U 2 ``` ``` 113031 134437 ``` [例を見る](https://img.atcoder.jp/ahc040/RGoXy7re.html?lang=ja&seed=0&output=sample)

Input Format

N/A

Output Format

N/A

Explanation/Hint

### ストーリー AtCoder社は、ロゴ入りの限定グッズをいくつか販売している。このたび、それらの限定グッズをまとめて値引きした「スペシャルセット」の販売を開始することになった。高橋くんは、ベルトコンベアで順番に運ばれてくるグッズをダンボール箱に梱包し、配送業者に渡す作業を担当する予定である。そのため、販売開始に備えて梱包の練習を行うことにした。配送料はダンボール箱の横幅と縦幅の合計に比例するため、できるだけ小さな箱に詰める必要がある。各グッズは長方形であり、手元に計測器具がないため、高橋くんは横幅と縦幅を目分量で測り、最適化が得意なあなたに電話で相談することにした。あなたが電話越しにグッズの配置方法を指示すると、その指示に従って高橋くんは商品を配置する。そして、その配置において必要となるダンボール箱の横幅と縦幅を再び目分量で計測し、結果をあなたに伝える。あなたはその情報を元に新しい配置方法を指示する。このやりとりを繰り返し、すべてのグッズをできるだけ小さなダンボール箱に収める配置方法を求めて欲しい。 ### 得点 $ t $ 回目の配置における横幅を $ W_t $、縦幅を $ H_t $、使用しなかった長方形の集合を $ U_t $ とする。このとき、$ t $ 回目のスコア $ s_t $ を次のように定義する。 \\\[ s\_t = W\_t + H\_t + \\sum\_{i\\in U\_t}(w\_i+h\_i) \\\] このとき、$ \min_t\ s_t $ の値が絶対スコアとして得られる。 **絶対スコアは小さければ小さいほど良い。** 各テストケース毎に、$ \mathrm{round}(10^9\times\ \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。システムテストは **CE 以外の結果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50個 - システムテスト: 3000個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/ahc040/seeds.txt) (sha256=1e93374aa02130a1167c2893f1904b4234a3b517d1e7b9d25022a9125ff3777d) を公開 #### 相対評価システムについて暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。 #### 実行時間について実行時間には多少のブレが生じます。また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。 ### サンプルプログラム Pythonでの解答例を示す。このプログラムでは、各長方形を順番にランダムな回転・位置で配置することを $ T $ 回試している。 ```

import random

def query(prdb):
    print(len(prdb))
    for p, r, d, b in prdb:
        print(p, r, d, b)
    W, H = map(int, input().split())
    return W, H

N, T, sigma = map(int, input().split())
wh = [tuple(map(int, input().split())) for _ in range(N)]

rng = random.Random(1234)

for _ in range(T):
    prdb = []
    for i in range(N):
        prdb.append((
            i,
            rng.randint(0, 1),
            ['U', 'L'][rng.randint(0, 1)],
            rng.randint(-1, i - 1),
        ))
    query(prdb)
```

### 入力生成方法

- $ \mathrm{rand}(L,U) $: $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する。
- $ \mathrm{rand\_double}(L,U) $: $ L $ 以上 $ U $ 以下の実数値を一様ランダムに生成する。
 
#### $ N $, $ T $, $ \sigma $ の生成

- $ N=\mathrm{rand}(30,100) $
- $ T=\mathrm{round}(N\times\ 2^{\mathrm{rand\_double}(-1,2)}) $
- $ \sigma=\mathrm{rand}(1000,10000) $
 
#### $ w,\ h $ の生成

$ U=10^5 $ とし、$ L=\mathrm{rand}(U/10,U/2) $ を生成する。 各 $ i $ に対し、$ w_i=\mathrm{rand}(L,U),\ h_i=\mathrm{rand}(L,U) $ により生成される。

### ツール(入力ジェネレータ・ローカルテスタ・ビジュアライザ)

- [Web版](https://img.atcoder.jp/ahc040/RGoXy7re.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。
- [ローカル版](https://img.atcoder.jp/ahc040/RGoXy7re.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。
  - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc040/RGoXy7re_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
 
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

#### ツールで用いられる入力ファイルの仕様

ローカルテスタに与える入力ファイルは解答プログラムに与えられる事前情報の末尾に以下の形式の情報が追加されている。

> $ w_0 $ $ h_0 $ $ \vdots $ $ w_{N-1} $ $ h_{N-1} $ $ dW_0 $ $ dH_0 $ $ \vdots $ $ dW_{T-1} $ $ dH_{T-1} $

- $ w_i,\ h_i $ は $ i $ 番目の長方形の真の横幅と縦幅である。
- $ dW_t,\ dH_t $ は $ t $ ターン目の計測結果に加算される計測誤差である。