SLP 2018Cうめ - Ktya’s blog

SLP 2018 C5

概要

kを正整数とする。あるテニスの大会に2*k人が参加しており、1日に1回会場で試合が行われる。どの二人の試合もちょうど一回行うことにし、各プレイヤーは自分の最初の試合に会場に訪れ、最後の試合の後に会場を去り、この間日付の分コインを払う。全てのプレイヤーのコインの総数の最小値を求めよ。

証明

2k人の最初の試合の日付の集合をA、最後の試合の日付の集合をBとする。(multiset)

Aの中身を小さい順にソートしたものを ${a_1,\ldots,a_{2k}}$ としBの中身を大きい順にソートしたものを ${b_1,\ldots,b_{2k}}$ とする。このとき、コインの総数は、

$\displaystyle{ \sum_{i=1}^{2k} (b_i-a_i+1) }$

で表せる。各項を下から評価する。
$a_i$ に関してはi人目の来場よりも前に行うことのできる試合は高々(i-1)C2なので $a_i\geq (i-1)C2+1$
$b_i$ に関してはi人目の来場よりも後ろに行うことのできる試合は高々(i-1)C2なので $a_i\leq 2kC2-(i-1)C2$
これらを考慮すると下からの評価ができる。
また,i>kなる部分については、少なくとも2(i-1)-2k人の組み合わせの試合はダブルカウントして引いているので、この部分を考慮すると以下の二つの下からの評価を得る。

$\displaystyle{ (b_i-a_i+1)\geq 2kC2 - 2*((i-1)C2) = 2k^2-k-i^2+3i-2 }$

$\displaystyle{ (b_i-a_i+1)\geq 2kC2 - 2((i-1)C2 + (2i-2-2k)C2=(2k-i+1)^2 }$

両者を足し合わせると $\frac{1}{2}(4k^3+k^2-k)$ となる。
本数値の構成を以下のように行う。
2k人をk人ずつに分ける。片方をX,もう片方をYとする。内部の人をx1,...,xk,y1,...y_kと命名する。
①Xから一人ずつ会場に行き、既に会場にいる人と試合を行う。（この間のコストはi人いる日付がiC2日あるので、 $\sum_{i=1}^{k} i(iC2)$ )
②y_1から順に会場に来ることにする。y_iは来た後にx_j(j=k)と試合をし、その後去る。最終的にYの人間のみが残る。
このときのコストは,y_iがきてからx_iが去るまで(k-i+1)^2日なのでこれを基にコストが計算できる。
③Yから一人ずつ会場を去る。去る前に会場にいる人と試合を行う。（コストは $\sum_{i=1}^{k} i(iC2)$ )

本構成において、b_i-ai+1を計算すると上記の不等式の統合を見たし、最小値であることがわかる。

感想

構成が難しい問題。評価もわりと構成ありきなのでうまく構成できないと手が付かない難問。

k=5くらいまででいろいろ実験するととりあえず答えは見えてくるので出てきた式を変形して意味を考察する、的なことをすればできるかもしれない？（実際にペア自体はkの二次式で実験していると人数分かけた三次式になることが予測できて、小さいケースでの実験から式自体は立てられる）