Codeforces Round #503 (by SIS, Div. 1)

Dashboard - Codeforces Round #503 (by SIS, Div. 1) - Codeforces

A. Elections

問題

政党がm個ある。 n人の有権者の投票先と、投票先を変えるために必要な金額が渡される。 党1の得票数が厳密に最多となるために必要な最小の金額を求めよ。

解法

党1の得票数で全探索する。 党1の最終的な得票数をxとする。 x以上の得票数を持つ政党への投票者をx未満にするために買収し、その後得票数がxに満たない場合はxになるまで貪欲に買収する。

B. The hat

問題

インタラクティブ問題(いつからかリアクティブとは呼ばれなくなったね) n人円卓に並んでいる。 i番目に座っている人は数x_{i}を持っている。 隣り合う人が持つx_{i}の値の差は\pm 1x_{i}を最大60回問い合わせることができるので x_{i} = x_{i+\frac{n}{2}} となるiを求めよ。 そのようなiが存在しない場合-1を出力せよ。

解法

f(i)=x_{i}-x_{i+\frac{n}{2}}という関数を考える。 f(i)=0となるiが解である。 まずn=4m+2の場合、f(i)は必ず奇数なので解なし。 そうでない場合解は必ず存在する。 f(i)=-f(i+\frac{n}{2})かつf(i)は連続なので中間値の定理よりf(i)=0となるiが存在が示され、それを二分法で求めることができる。

C.

D.

E.