2020-04-26

SLP 2018Cうめ

SLP

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の二次式で実験していると人数分かけた三次式になることが予測できて、小さいケースでの実験から式自体は立てられる）

2020-04-22

SLP Cうめ

SLP

SLP 2018 C4(IMO 2018 Problem 3)

概要

「反パスカル三角形」を、正三角形上に配置された数字であって、隣り合う数の差の絶対値が上の数になっているものと定める。
2018行からなる反パスカル三角形であって1~1+...+2018の全ての数を一回ずつ使う物は存在するか。

証明

題意の反パスカル三角形が構成できると仮定する。
まず、一番上の行の数字をx_1とし、x_iに対してx_(i+1)を「x_iの直下にある数のうち大きい方」と定める。
逆に、x_iに対してx_(i+1)でない方（小さい方）をy_iとする。このとき、x_(i+1)=x_i+y_iとなるので、x_2018=x_1+y_1~y_2017の和　となる。今、x_2018<=1+...+2018で、2018個の異なる数字の和なのでx_1+y_1~y_2017の和>=1+...+2018となる。
したがってx_1,y_1,…y_2017は1~2018の並べ替えになる。
続いて、x_2018,y_2017の書かれていた位置を2018行目の左からk,k+1番目であるとすると、1~k-1を底辺とする正三角形T1と、k+2~2018を底辺とする正三角形T2がとれ、これらは記入された数が全て異なる反パスカル三角形である。T1かT2のどちらかは一辺が1008以上であり、前半と同じ議論をすると、底辺に異なる1008(以上)の和で表せる数bが存在する。一方、1~2018はT1にもT2にも含まれないため、bは（2019~3016の和）以上になることが言える。これは計算すると1+...+2018より大きくなるので矛盾。

感想

迷走しまくって解ける気配がなかったので解説を見た。
上から順にわかる部分を追いかけると比較的ストレートに示せるタイプであった。
解説見るとすごく簡単に見えるが、迷走しやすさが尋常じゃないのがこの問題の特徴っぽい。実際IMOでもあまり解かれなかったらしい。
後半の不等式のガバガバ具合が証明しにくさの一因か。（nの二乗の係数が違うレベル）
この通りの構成ゲーとしては発展しなさそうだけど使う数字の制限を緩めて個数を聞く感じにしたら競プロにもある感じだろうか？

2020-04-21

SLP2018 Cうめ

SLP 2018 C3

概要

n+1個のマスが横一列に並んでいる。左端にn個の石が置かれている。
以下の操作を繰り返し行う。
石がk個あるマスから一つ石を選び、1~kマス右に移動する。
この時n個の石を全て右端に配置するためには[n/1]+[n/2]…+[n/n]([r]でr以上の最小の整数を表す)回以上の操作を必要とすることを示せ。

証明

（一連の操作で、ゴール（右端にたどり着く）順に石に1~nの番号をつける。→石iは石i-1までがゴールしているため条件より最大でもn-iしか動けない。したがって[n/(n-i)]回の操作がこの石に対して必要→ただしゴール前での順序に依存してしまうため、この部分を考慮する必要がある。→初めから番号をつけておき、操作を決める。）
予め石に1~n番号をつける。各操作で、小さい番号の石を選ぶことにする。
石kを動かしたということは選んだマスにはk以上の番号が書かれた石しかないため、最大でもn-kしか動けない。よって石kがゴールするためには[n/(n-k)]回操作が必要となる。これを足し合わせればよい。

感想

C2より簡単な気がした。
解説もほぼ同じ。確かに大きい番号選んだ方がみやすいな。
式から距離kずつ移動する石があれば良さそうなのは気づくのでそうなるようにストーリーづけ（上手な番号づけ、言い換え）をする感じ。
発展として等号が成立するnを全て求めよというのがあったので考える。

→わからん

2020-04-21

■

SLP

やっぱC苦手だなあ（現役時代に他に得意なものもなかったわけですが）

難易度はとりあえず10段階で描こうと思います。最初は多分ガバガバ。

2018SLP C1

https://www.imo-official.org/problems/IMO2018SL.pdf

概要

nを3以上の整数とする。2*n個の正整数からなる集合Sであって、以下を満たすものが存在することを示せ：

任意のm=2,...,nに対してSの部分集合T_mであってT_mがm個の元からなり、T_mの元の総和がSの総和の半分になるものが存在する。

証明

S={1,1,1,1,2,2,...,2^(n-2),2^(n-2)}とする。このとき

T_m={2^(n-2),...,2^(n-m),2^(n-m)}ととればSが条件を満たすとわかる。

→解説を見たらどうやらdistinctという条件がつくらしい。ちゃんと書いて。（Setでそういう意味なのか？)

distinctでも構成の際の発想はおなじで、T_mの最後尾の元を二つの元に分解してT_(m+1)を構成する感じ。

(1,2,4-1,4,...,2^(n-1)-1,2^(n-1),2^n-1,x} (x=1項から2*n-4項までの和)

x=2^n-n-2となる。nがある程度大きいと2^(n-1)>n-1なのでxは2^(n-1)よりも大きくなり、既に存在する元と一致しない。n=3の時のみ、{1,2,3,4,7,3}となり、不適切なので以下のように構成する。

{1,2,3,4,5,9}(T_2={9,3},T_3={9,1,2})

感想

構成ゲー。後半が少々面倒だが、これは奇数項目をうまく大きくとればすぐに示せる。実際解説では３ベキを上手く使っていた。

後半部分はおいといて意外と競プロの役に立つんじゃないか？

難易度1

2018SLP C2(IMO2018 Problem 4)

概要

AさんとBさんが20*20のチェスボード上でゲームをしている。

Aさんが黒のナイトを、今までにおいた黒のナイトを攻撃しないように（＝距離√5はNG）空のマスにおき、Bさんは白のナイトを空のマスにおく。これを繰り返し、どちらかが置けなくなったら終了する。

Bさんの行動によらずAさんが少なくともK個の黒ナイトを置くことができるようなKの最大値を求めよ。

証明

K=100が最大値である。

まず、チェスボードの通り市松模様に塗る。同じ色同士は距離√5にならないのでAさんは同じ色に置き続ければ少なくとも20*20/4=100個おける。

K<=100を示す。

（Aさんがコマをおくと置けなくなる場所が0個以上発生するが、Bさんがうまく次の一手を塞ぐようにすると四個の組ごとに潰せる、と言ったことを示したい）

4*4のマス目に以下のように番号づけ（塗り分け）を行う。

1 2 3 4

3 4 1 2

2 1 4 3

4 3 2 1

Aさんがどこかに一つナイトを置くと同じ番号内の二つにAさんがナイトを置けなくなる。

残った一つにBさんがナイトを置けば、常に４つ以上Aさんがナイトをおけるマス目の候補が消える。20*20を4*4のマスに分解して上記の議論を行うことで、K<=100となる。

感想

競プロにもありそうっちゃありそうだけど証明の方が難しいタイプだから微妙か。もしくはインタラクティブ？

証明は解説と同様の手法だったが、他にも塗り分けはありそう。なぜかK=100の構成にとても苦戦した。

IMOの4番にしては難しい気がする。Shortlist上の問題文とIMOでの問題文で雰囲気が変わってておもしろい。チェスのくだりがなくなって問題は分かりやすいけど解くのは難しくなってるような。しかしちゃんとわかりやすくreviseしてるんですね。

難易度4

2020-04-20

■

JOI

09JOI予選5

https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_e

概要:n(<1e9)枚のカードをm(<5000)回シャッフルする。シャッフルは以下の通り

(1~x)(x+1~y)(y+1~n)->(y+1~n)(x+1~y)(1~x)

この時、シャッフル後にp枚目からq枚目にr以下のものは何枚あるか。

解法:順序を保つブロックで考える（座圧的な）。各シャッフルでブロックが高々二個増える。ブロックの左端の情報のみでシャッフルを行い、最後にブロックごとに[p,q]との交差であってr以下になるものを数えればよい。

実装:半開区間で整理するのがよい。添字に関してよく整理してから実装する。

感想:複数の処理がある。特に区間の交差の処理でもたついた。何度か書くと良さそうな問題。

09JOI本選5

https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=12

概要:二つの建物があり、それぞれW_k*H_k（それぞれ500以下）マスの部屋の塊で構成される。各部屋には数字が振られており、一つ入り口がある。ある数字N_kが与えられた時に建物kにおいて、今いる部屋と隣接していて、N_k以下の数字が振られている部屋に移動することができる。二つの建物で合わせてR以上の部屋を訪問するために必要なN_1+N_2として考えられる最小値を求めよ。

解法:建物kに対してnum_k[r]=r個訪れるのに必要な番号の最小値　を求める。

まず、隣接するコストで最も小さいものをmとし、m以下の部分を掘り進める。この時の部屋の数をrとし、num_k[r]=mとする。（間は埋める）

このあとはnum_1[x]+num_2[R-x]の最小値を求める。

実装：priority_queue

感想：４より簡単のような。

2020-04-20

淡々とやります

Atcoder Cがまだ残っていますが、一通り問題は見たのでメインを以下にシフト。

・JOI埋め（レベル8〜）

・IMOSLP、C埋め

地力上げです。いや学生かお前は。

SLPはC以外も載せるかも？（JMOもやるかも）

2018-12-03

えでゅふぉ 55

1082A - Vasya and Book

題意: n ページからなる本があり現在 x ページ目にいる。一度操作をすると前に d ページもしくは後ろに d ページ分飛ぶことができる（ただし0以下なら1になりn+1以上ならnとなる）このとき y ページ目に到達することができるか。できるなら最小で操作何回でいけるか。

このクエリを t 回分解く。

解法: ためす。mod d的には3通りしかないので。

反省:実装・題意把握　遅　最初例が間違っているのに騙された

1082B - Vova and Trophies

題意: GもしくはSからなる文字列がある。今文字列のどこかを一回入れ替えることができる。Gの連続部分長は最大でいくつになるか。

解法: まず連続している部分ごとにまとめる。Sの長さが1なら両隣をくっつけることができる。Gの連結成分の数によって場合分けが生じるので注意。

反省:実装　遅　場合分けの処理が下手でバグりまくった。

1082C - Multi-Subject Competition

題意: n 人の人と m 個の科目があり，それぞれの人には担当できる科目（一つ）とそれに対するスキル（-1000〜1000）が定まっている。

正整数 k およびいくつかの科目を選び，各科目ごと担当できる k 人を選んで全員のスキルの和をチームのスキルとみなす。

チームのスキルの最大値を求めよ。

解法:科目ごとに担当できる人のスキル値を保持し，大きい順にソート（nlogn）。上からx人目までの和をvec_score[x]に挿入。

vec_score[x]のなかで正の値をとるもののみ加算し値をans[x]としたときans[x]の最大値を求めれば良い。

反省:素直な問題だが発想にてこずった。実装は比較的ストレートにかけたがオーバーフローした（アホ）

1082D - Maximum Diameter Graph

題意: n 個の頂点があり，各頂点には正整数 a_i が書かれている。この n 個の頂点を用いて木を作る。ただし頂点 i から伸びる辺は a_i 個以下である。

このような木を作ることが可能か判定せよ。構成可能ならそのうち直径が最大になるものをひとつ与えよ。

解法:まず１より大きい数字をもつ頂点を横一列につなげる。そこに次数1の頂点をどんどん付け足すだけで良い。a_i = 1となる頂点が m 個あるとすると，直径は (n-m) + min(m, 2) となるのであとは頂点の対応をきちんと求めればok

反省:最小だと思って「大きい数字を持つ頂点をどんどん繋げて」とか考えて時間食ってました。問題文はよく読もう。ただ最小と言う誤読をしたことを加味しても実装がめっちゃ遅かったけど。流石に難易度的に最小だと決めつけてやっていた自分が悪い。

1082E - Increasing Frequency

題意: 長さ n の数列がある。ある区間 [l,r] と整数 k を選んで区間 [l,r] 内の数に全て +k するという操作を行うことができる。(kは負でもよい)この操作後に数列内に c は最大でいくつ存在するか。

解法:整数 d に対して f(d,[l,r]) を [l, r] 内にある d の個数とすると，求めるべきは

f(c,[1, l-1]) + f(d, [l, r]) + f(c, [r+1, n])

の最大値と言うことになる。これは以下のように式変形可能

f(c,[1, n]) + f(d, [l, r]) - f(c, [l, r])

一項目は定数で三項目を小さくしたいので[l,r]についてa[l]=a[r]=dであることが必要となる。したがって数列内に存在するdに対してa_i=dになる添字を取ってきて，上記部分和の最大値を求める。この部分和問題については添字の個数xに対してO(x)で解くことができ，したがって全体でO(n)で解くことができる。

実装中。

反省:最大部分和がdpで求まることを学んだ。

1082F - Speed Dial

題意:未読

1082G - Petya and Graph

題意: 単純グラフが与えられ，頂点と辺それぞれに重みが定まっている。このグラフの部分グラフの重みを (辺の重みの和) - (頂点の重みの和) で定める時，その最大値を求めよ。

解法:考え中