# Reply Codechallenge 2021

# 問題概要

## 概要

H * Wのグリッドを考える。

N個のビルが既にグリッドに置いてある。
M個のアンテナを持っている(まだグリッドに置かれていない)。

あなたの仕事は、アンテナをグリッドに配置して(なお、アンテナは置かなくても良い)、スコアを最大化することである。

ビルは
- パラメーター1 $B_L$
- パラメーター2 $B_C$

アンテナはそれぞれ
- 通信距離 $A_R$
- パラメーター $A_C$

を持つ。

## スコア計算

スコアは、**ビルごと**の「良さ」の総和である。ただし、全部のビルが通信できるアンテナを一つ以上持つ時、スコア R が追加で貰える。

### ビル b の良さ

アンテナ a とビル b の相性 s(a, b) は以下。

- s(a, b) = $B_C[b] \times A_C[a] - B_L[b] \times \mathrm{dist}(b, a)$

ビル b の良さは、ビルまでの距離が$A_R$以下のアンテナ全部についての、max s(a, b) である。

通信できるアンテナが一つもない場合は、ビルbの良さは0。(ビルの良さが負になりうることもある？)

## 注釈

- 距離は全部マンハッタン距離
- ビルの置いてある場所は全部distinct
- アンテナはビルと同じマスに置ける。
- アンテナ同士を同じマスに置くことは出来ない。

## 入力形式

W H
N M R
Bx1 By1 Bl1 Bc1
Bx2 By2 Bl2 Bc2
:
BxN ByN BlN BcN
Ar1 Ac1
Ar2 Ac2
:
ArN AcN

## 出力形式

M
id_1 Ax[id_1] Ay[id_1]
id_2 Ax[id_2] Ay[id_2]
:
id_M Ax[id_M] Ay[id_M]

実際は空行は消すこと

## スコア

スコア

# 便利ツール

## calcscore(予定)
置き場: ```Dropbox/Hashcode2020/2021/maroon/calcscore/calcscore.cpp```
使い方: `./calcscore infile outfile`
stdout に得点が出てくる
invalidな入力を入れるとぶっ壊れたりぶっ壊れなかったり

`g++ calcscore.cpp -o calcscore -std=c++14 -O2`

## watch
各自のディレクトリ下にa.outもしくはa_hoge.outとかのファイル名で出力を出しておくと勝手に収集する

# ケース解析

## A (W=15, H=10, N=5, M=4, R=100)

Bl Average : 2.6, Max: 4, Min: 1
Bc Average : 26.6, Max: 44, Min: 14
Ar Average : 2.25, Max: 4, Min: 1
Ac Average : 50, Max: 100, Min: 10
MaxScore: 13300

## B (W=400, H=400, N=50000, M=1014, R=4e7)

Bl Average : 50.0925, Max: 100, Min: 0
Bc Average : 49.86006, Max: 100, Min: 0
Ar Average : 2.87376725838264, Max: 100, Min: 0
Ac Average : 1983.71104536489, Max: 4992, Min: 500
MaxScore: 12445070976

## C (W=600, H=600, N=60000, M=60000, R=5e7)

N=Mなのがポイント！！！！多分マッチング的な完全解があるやつだとおもいます(chokudai)

Bl Average : 0, Max: 0, Min: 0
Bc Average : 50.0318666666667, Max: 100, Min: 0
Ar Average : 0, Max: 0, Min: 0
Ac Average : 500.63425, Max: 1000, Min: 1
MaxScore: 3001912000

## D (W=1200, H=1200, N=40000, M=1123, R=5e7)

$B_L = B_C$

ビルが固まってるところとそうでもないところがある（ビジュアライザ情報）

Bl Average : 55.106325, Max: 100, Min: 10
Bc Average : 55.106325, Max: 100, Min: 10
Ar Average : 7.28317008014248, Max: 100, Min: 0
Ac Average : 2351.53873552983, Max: 4994, Min: 1
MaxScore: 11008039482

## E (W=2000, H=2000, N=200000, M=6257, R=3e7)

Bl Average : 50.022235, Max: 76, Min: 23
Bc Average : 49.51128, Max: 86, Min: 23
Ar Average : 2.62090458686271, Max: 119, Min: 0
Ac Average : 1854.79319162538, Max: 7990, Min: 1
MaxScore: 79119025440

## F (W=6000, H=6000, N=350000, M=32515, R=2e8)

Bl Average : 49.0598457142857, Max: 97, Min: 2
Bc Average : 59.3232942857143, Max: 100, Min: 2
Ar Average : 3.33003229278794, Max: 200, Min: 0
Ac Average : 2450.33110871905, Max: 5000, Min: 1
MaxScore: 103815765000

Arが100以上：75個
Arが50以上：78個
Arが30以上：159個