問題一覧 > スコア問題

No.5004 Room Assignment

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 39
作問者 : butsurizukibutsurizuki
2 ProblemId : 7297 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-01 09:33:17

メモ

スコアとしての順位はこちらをご覧ください https://yukicoder.me/problems/no/5004/score

この問題は、Advent Calendar Contest 2021 1日目の問題です。
難易度は、Advent Calendar Contest 用に付けられたものです。正当な出力を行うことが出来ればコンテストで得点を獲得できます。

スコア問題であるため、最後の提出から5分間は次の提出を行うことができません。

この問題に対しての、(Writerが想定している)コンテスト中の言及ルールは以下です。

  • 解法に直接かかわらない部分(ローカルテストの方法等)について、議論や相談を認めます。
  • ビジュアライザを有志で作成し公開するなどしても構いません。
  • さらに、自身の解法を直接言及することも、コードを共有することも認めます。
    • ただし、そのことによって他の方が解を改良した場合、その得点は改良したコードの提出者のものとなります。
なお、コンテスト期間終了後のリジャッジ、システムテスト等は予定しておりません。
2021-12-25 23:30:00 をもってコンテスト期間終了とし、解説ページにてケース生成に用いたシードを公開します。

問題文

この問題はインタラクティブな問題です。

あなたは、とあるネットゲームのサーバーエンジニアです。
あなたの任務は、出現するプレイヤーを、なるべく実力の近いプレイヤー同士が同じ部屋になるように、かつなるべく速やかに部屋分けするプログラムを書くことです。

最初に、 $2$ 整数 $T,R$ が以下の形式で与えられます。

$T$ $R$
これから $T$ ティックにわたって、プレイヤーが出現します。あなたのプログラムは、以下で説明するやりとりを $T$ 回行う必要があります。
$R$ は、同じ部屋に割り当てられる人数の上限を表します。

ジャッジとプログラムとの間で、 $t$ ($0 \le t < T$) ティック目に行われるべきやりとりは以下です。
まず、 $t$ ティック目のはじめに、以下の形式で $t$ ティック目に出現するプレイヤーの情報が与えられます。
$N$ $S_1$ $S_2$ $\dots$ $S_N$
$N$ は $t$ ティック目に出現したプレイヤーの数を表します。
$t-1$ ティック目以前に出現したプレイヤーの数を $p$ とすると、 $t$ ティック目にはプレイヤー $p+1,$ プレイヤー $p+2,$ $\dots,$ プレイヤー $p+N$ が出現しました。
$S_i$ は、 プレイヤー $p+i$ の「スキル値」を表します。「スキル値」は、採点に用いられるパラメータです。
出現したプレイヤーは、最初はそのプレイヤー $1$ 人だけが存在する部屋に割り当てられます。

続いて、あなたは以下の形式で $t$ ティック目に行う操作を出力する必要があります。
$M$
$U_1$ $V_1$
$U_2$ $V_2$
$\dots$
$U_M$ $V_M$
$M$ は $0$ 以上の整数であるべきで、このティックで行う操作の数を表します。
$M$ の上限は特に制限しませんが、出力があまりに大きい場合、OLEやREなどの予期せぬエラーが出る可能性があります。その場合について救済措置は取りません。
出力全体で $M$ の総和が $10^4$ 以下である場合をジャッジのサポート対象とするので、これを満足する出力に対し予期せぬエラーが生じた場合は、「質問」からお問い合わせください。
$i$ 個目の操作は $U_i,V_i$ の $2$ 整数で表され、これはプレイヤー $U_i$ のいる部屋とプレイヤー $V_i$ のいる部屋を併合する操作です。(Union-Find の併合クエリに相当します)
ここで、部屋を併合する際に、合計の人数が $R$ 人を超えてはなりません。まだ出現していないプレイヤーを併合に使うこともできません。
また、同じ部屋同士を併合しようとした場合、その操作は無視されます。(WA とはなりません)
ジャッジの入力を必ず最後まで全て受け取ってください。行わなかった場合WAとなる可能性があります。
出力を行った後、必ず標準出力をflushしてください。行わなかった場合TLEする可能性があります。

採点方法

部屋を構成するプレイヤーのうち、最もスキル値の大きいプレイヤーのスキル値を $S_M$ 、最もスキル値の小さいプレイヤーのスキル値を $S_m$ とします。
また、 $E$ を以下のように定義します。
$E=\sum_{i,j}$ ( $i$ が $x$ ティック目に出現し、 $(i,j)$ が $y$ ティック目に同じ部屋になった場合、 $y-x$ )
但し、 $\sum_{i,j}$ で同じ部屋にいる全ての相異なるプレイヤーの組 $(i,j)$ $(i \neq j)$ についての総和を表します。
このとき、各部屋の価値を以下のように定義します。

  • 部屋に $1$ 人いる場合、部屋の価値は $0$
  • 部屋に $2$ 人いる場合、部屋の価値は $\max(1 \times (200-(S_M-S_m)^2) - E,0)$
  • 部屋に $3$ 人いる場合、部屋の価値は $\max(3 \times (200-(S_M-S_m)^2) - E,0)$
  • 部屋に $4$ 人いる場合、部屋の価値は $\max(6 \times (200-(S_M-S_m)^2) - E,0)$

$1$ つのテストケースに対するスコアは、全ての部屋の価値の合計です。また、最終的なスコアは、全てのテストケースに対するスコアの総和です。
AC 以外の判定を受けたケースが存在する場合は、そのケースについて $0$ 点であるものとして採点が行われます。

入力生成方法

  • 採点に用いられるテストケースの数は $100$
  • $T=3600$ で固定
  • $R=4$ で固定
  • $N$ の総和は $5400$ で固定
  • 全ての $S_i$ に対し、 $0 \le S_i \le 100$
テストケースの生成方法
平均 $\mu$ 、標準偏差 $\sigma$ で正規分布に従う実数乱数を生成する関数を $\mathrm{nd}(\mu,\sigma)$ とします。
下限 $l$ 、上限 $r$ の一様実数乱数を生成する関数を $\mathrm{rnd}(l,r)$ とします。
$x$ を四捨五入したものを $\mathrm{round}(x)$ とします。

$S_i$ の生成について
$S_i$ は $\mathrm{round}(\mathrm{nd}(50,20))$ により生成されます。
ただし、生成された値が $S_i$ の制約に違反する場合、制約を満たす値が出るまで生成を繰り返します。

プレイヤーの出現タイミングの生成について
まず、実数 $\omega$ を $\mathrm{rnd}(0,2 \pi)$ で定めます。
最初に、出現速度として関数 $f(t)=1.5+\sin(\frac{2 \pi t}{T} + \omega)$ と定義します。これは、 $t$ ティック目に出現する標準的なプレイヤーの数を表します。
次に、標準的な累積の出現人数を表す関数 $F$ を求めます。
これは、 $f$ の積分である $F(t)=1.5t-\dfrac{T\cos\left(\frac{2{\pi}t}{T}+{\omega}\right)}{2{\pi}} + C$ (但し、 $C$ は $F(0)=0$ を満足するようにとった積分定数)です。
次に、 $F$ の逆関数を $G$ とします。 $G(x)$ = (標準何ティック後に出現したプレイヤーの数が $x$ 人になるか) を表します。
そして、数列 $B$ を $B_i=\mathrm{round}(G(i-0.5) + \mathrm{rnd}(-20,20))\mod T$ ($1 \le i \le 5400$) とします。
このとき、数列 $B$ の要素として $k$ が $l$ 個含まれたとすると、 $k$ ティック目には $l$ 人のプレイヤーが出現します。

配布物等

こちらから配布物(zip)を入手してください。
githubからも同一の内容が入手可能です。
この配布物を解答に用いたり、この配布物を他言語に翻訳したものを再配布しても構いません。
ローカルテストの際の注意:
この問題では、入力ファイルの内容がそのまま、インタラクションにより順を追ってコードに与えられることで採点が行われます。
そのため、ローカルテストの際は、ジャッジによるインタラクションは不要です。
適切なタイミングで適切な情報を受け取る実装にしてコードを実行して出力ファイルを生成し、それを採点プログラムに与えて採点結果を得てください。

サンプル

サンプル1
入力
6 4
1 5
2 4 7
2 50 4
3 4 4 4
2 0 51
2 100 100
出力
0
2
1 2
2 3
0
4
8 7
7 6
6 5
5 8
0
2
4 10
9 11

この入力はケースの生成方法に違反する例であることに注意してください。

$0$ ティック目 : スキル値 $5$ のプレイヤー $1$ が出現しました。プログラムは操作をしません。

$1$ ティック目 : スキル値 $4$ のプレイヤー $2$ と スキル値 $7$ のプレイヤー $3$ が出現しました。
プログラムはプレイヤー $1$ のいる部屋とプレイヤー $2$ のいる部屋を併合しました。
プログラムはプレイヤー $2$ のいる部屋とプレイヤー $3$ のいる部屋を併合しました。

$2$ ティック目 : スキル値 $50$ のプレイヤー $4$ とスキル値 $4$ のプレイヤー $5$ が出現しました。プログラムは操作をしません。

$3$ ティック目 : スキル値 $4$ のプレイヤー $6,7,8$ が出現しました。
プログラムはプレイヤー $8$ のいる部屋とプレイヤー $7$ のいる部屋を併合しました。
プログラムはプレイヤー $7$ のいる部屋とプレイヤー $6$ のいる部屋を併合しました。
プログラムはプレイヤー $6$ のいる部屋とプレイヤー $5$ のいる部屋を併合しました。
プログラムはプレイヤー $5$ のいる部屋とプレイヤー $8$ のいる部屋を併合しようとしましたが、この $2$ つは同じであるためこの操作は無視されます。

$4$ ティック目 : スキル値 $0$ のプレイヤー $9$ と スキル値 $51$ のプレイヤー $10$ が出現しました。プログラムは操作をしません。

$5$ ティック目 : スキル値 $100$ のプレイヤー $11,12$ が出現しました。
プログラムはプレイヤー $4$ のいる部屋とプレイヤー $10$ のいる部屋を併合しました。
プログラムはプレイヤー $9$ のいる部屋とプレイヤー $11$ のいる部屋を併合しました。

プレイヤー $1,2,3$ を含む部屋の価値は $3 \times (200 - (7-4)^2) - 2 = 571$
プレイヤー $5,6,7,8$ を含む部屋の価値は $6 \times (200 - (4-4)^2) - 3 = 1197$
プレイヤー $4,10$ を含む部屋の価値は $1 \times (200 - (51-50)^2) - 4 = 195$
プレイヤー $9,11$ を含む部屋、およびプレイヤー $12$ のみを含む部屋の価値は $0$ です。
最終的に、このプログラムのこのテストケースに対する得点は $571 + 1197 + 195 + 0 + 0 = 1963$ となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。