/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
ストーリー
高橋社長は、うっかり AtCoder 社のオフィスの壁にいくつもの穴をあけてしまった。 青木副社長に見つかる前に何とかしたい高橋社長は、壁の前にレンガを積んで穴を隠すことにした。 ただし、レンガを買いすぎると、その出費から青木副社長に怪しまれるかもしれない。 できるだけ少ない費用ですべての穴を隠せるよう、レンガの配置を考えてほしい。
問題文
高さ H マス、幅 W マスの壁がある。 左下のマスの座標を (0,0) とし、そこから右方向に x マス、上方向に y マス進んだ先のマスの座標を (x,y) とする。 壁の最下段のすぐ下には床があり、K 個の異なるマス (a_0,b_0),\ldots,(a_{K-1},b_{K-1}) に穴があいている。
あなたは、この壁の手前にレンガを積み上げ、すべての穴のあいたマスを覆いたい。 レンガは高さが 1 マスで、幅が 1,3,5,7,9 マスの 5 種類あり、それぞれ何個でも使用できる。 幅 \ell のレンガ 1 個の代金は c_\ell である。 レンガは回転させることができず、左下の座標を整数座標 (x,y) として配置すると、(x,y),\ldots,(x+\ell-1,y) の \ell 個のマスを覆う。
各レンガは、底面の中央の 1 マスにある接続部を、床または直下のレンガに固定することで姿勢を保つ。 中央以外の部分が支えられている必要はなく、上に載るレンガの重さや重心は姿勢の維持に影響しない。
配置は、以下の条件をすべて満たさなければならない。
- 各レンガは壁内に収まる。 すなわち、左下の座標が (x,y)、幅が \ell のレンガについて、0\leq x、x+\ell\leq W、0\leq y<H を満たす。
- 異なるレンガが同じマスを覆うことはない。 ただし、辺が接していてもよい。
- 各レンガは中央で支持される。 すなわち、左下の座標が (x,y)、幅が \ell のレンガについて、y=0 であるか、マス \left(x+\frac{\ell-1}{2},y-1\right) が別のレンガで覆われている。
- すべての穴のあいたマスがレンガで覆われている。 穴のあいていないマスを覆ってもよい。
中央の直下が空いているレンガは、両端が支えられていても条件を満たさない。
以上の条件を満たす配置のうち、使用するレンガの代金の合計ができるだけ小さいものを求めよ。
得点
使用するレンガの個数を M、各レンガの幅を \ell_0,\ldots,\ell_{M-1} とし、費用 C を以下で定義する。
\[ C=\sum_{i=0}^{M-1}c_{\ell_i} \]
壁全体を幅 1 のレンガで覆うときの費用は WHc_1 である。 このとき、以下の得点が得られる。
\[ \max(0,WHc_1-C+1) \]
合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となり、提出の得点は 0 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
W H K
c_1 c_3 c_5 c_7 c_9
a_0 b_0
\vdots
a_{K-1} b_{K-1}
各値は以下の制約を満たす。
- W=60
- H=40
- K=120
- c_1=5
- 2\ell-1\leq c_\ell\leq 2\ell+4 (\ell=3,5,7,9)
- 0\leq a_j<W
- 0\leq b_j<H
- (a_j,b_j) はすべて異なる。
- 入力される値はすべて整数である。
レンガの代金は、幅が大きいほど高いとは限らない。
出力
以下の形式で標準出力に出力せよ。
M
x_0 y_0 \ell_0
\vdots
x_{M-1} y_{M-1} \ell_{M-1}
ここで、M は配置するレンガの個数であり、M\leq WH を満たさなければならない。 最初の行に M を整数で出力し、続く M 行のうち i+1 行目に、レンガ i の左下の座標 (x_i,y_i) と幅 \ell_i を整数で出力せよ。 \ell_i は 1,3,5,7,9 のいずれかでなければならない。 出力するレンガの順序は任意である。
実行時間制限内であれば、上記の形式の解を複数回出力してもよい。 複数回出力した場合、最後に出力された解のみが採点に用いられる。 各解は独立した完成配置を表し、先に出力した解へのレンガの追加を表すものではない。 Web版ビジュアライザでは、出力した複数の解を比較することができる。
入力生成方法
\mathrm{rand}(L,R) を、L 以上 R 以下の整数から一様ランダムに値を生成する関数とする。
まず、c_1=5 とし、\ell=3,5,7,9 の順に c_\ell=\mathrm{rand}(2\ell-1,2\ell+4) を生成する。
次に、穴の位置を以下の手順で生成する。 穴の個数が K 個になるまで、a=\mathrm{rand}(0,W-1)、b=\mathrm{rand}(0,H-1) の順に値を生成する。 マス (a,b) にまだ穴があいていなければ穴をあけ、すでに穴があいていればその組を捨てて再び a,b を生成する。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
コンパイルが通らない場合は
rustup updateをお試し下さい。- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。 ご注意下さい。
本コンテストでは、生成AIの利用は一部の例外を除き禁止されています。 詳細はこちらの記事をご確認ください。
Story
CEO Takahashi has accidentally made several holes in a wall of the AtCoder Inc. office. Hoping to hide the damage before Vice President Aoki notices, Takahashi decides to stack bricks in front of the wall to conceal the holes. However, buying too many bricks might arouse Aoki's suspicion because of the expense. Help Takahashi arrange the bricks to hide all the holes at as little cost as possible.
Problem Statement
There is a wall of height H cells and width W cells. Let (0,0) be the coordinates of the bottom-left cell, and let (x,y) be the coordinates of the cell located x cells to the right and y cells upward from there. There is a floor immediately below the bottom row of the wall, and K distinct cells (a_0,b_0),\ldots,(a_{K-1},b_{K-1}) contain holes.
You want to stack bricks in front of this wall to cover every cell containing a hole. There are five types of bricks, each 1 cell high, with widths of 1,3,5,7,9 cells, and you can use any number of each type. A brick of width \ell costs c_\ell. Bricks cannot be rotated; placing a brick with its bottom-left corner at integer coordinates (x,y) covers the \ell cells (x,y),\ldots,(x+\ell-1,y).
Each brick stays in place by attaching a connector in the central cell of its bottom face to the floor or the brick directly below it. No support is required elsewhere, and the weight and center of gravity of bricks above it do not affect its stability.
The arrangement must satisfy all of the following conditions.
- Each brick fits within the wall. That is, a brick with bottom-left coordinates (x,y) and width \ell satisfies 0\leq x, x+\ell\leq W, and 0\leq y<H.
- No two bricks cover the same cell. Their edges may touch.
- Each brick is supported at its center. That is, for a brick with bottom-left coordinates (x,y) and width \ell, either y=0 or the cell \left(x+\frac{\ell-1}{2},y-1\right) is covered by another brick.
- Every cell containing a hole is covered by a brick. Cells without holes may also be covered.
A brick with an empty cell directly below its center does not satisfy the conditions, even if both ends are supported.
Find an arrangement satisfying these conditions that minimizes the total cost of the bricks used.
Scoring
Let M be the number of bricks used and \ell_0,\ldots,\ell_{M-1} be their widths, and define the cost C as follows.
\[ C=\sum_{i=0}^{M-1}c_{\ell_i} \]
The cost of covering the entire wall with bricks of width 1 is WHc_1. You receive the following score.
\[ \max(0,WHc_1-C+1) \]
There are 150 test cases, and the score of a submission is the sum of the scores for all test cases. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format.
W H K
c_1 c_3 c_5 c_7 c_9
a_0 b_0
\vdots
a_{K-1} b_{K-1}
Each value satisfies the following constraints.
- W=60
- H=40
- K=120
- c_1=5
- 2\ell-1\leq c_\ell\leq 2\ell+4 (\ell=3,5,7,9)
- 0\leq a_j<W
- 0\leq b_j<H
- All (a_j,b_j) are distinct.
- All input values are integers.
A wider brick does not necessarily cost more.
Output
Output to Standard Output in the following format.
M
x_0 y_0 \ell_0
\vdots
x_{M-1} y_{M-1} \ell_{M-1}
Here, M is the number of bricks placed and must satisfy M\leq WH. Output the integer M on the first line, followed by M lines, the (i+1)-th of which contains the bottom-left coordinates (x_i,y_i) and width \ell_i of brick i, all as integers. \ell_i must be one of 1,3,5,7,9. The bricks may be output in any order.
You may output multiple solutions in the format above within the time limit. If you output multiple solutions, only the last one is used for scoring. Each solution represents a separate complete arrangement, rather than additions to a previously output solution. The web visualizer allows you to compare multiple solutions you have output.
Input Generation
Let \mathrm{rand}(L,R) be a function that generates an integer uniformly at random between L and R, inclusive.
First, set c_1=5, then generate c_\ell=\mathrm{rand}(2\ell-1,2\ell+4) for \ell=3,5,7,9 in this order.
Next, generate the hole positions as follows. Until there are K holes, generate a=\mathrm{rand}(0,W-1) and then b=\mathrm{rand}(0,H-1). If cell (a,b) does not already contain a hole, make a hole there; otherwise, discard the pair and generate a,b again.
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations.
- Local version: You need a compilation environment of Rust language.
If it does not compile, please try
rustup update.- 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.
The use of generative AI in this contest is prohibited, with limited exceptions. Please refer to this post for further details.