SnackDown Online Qualifier 2016
https://www.codechef.com/SNCKQL16
Kitchen Timetable
問題を読み間違えないように気を付けよう。
SnackDown Online Qualifier 2016 » Kitchen Timetabl ...
Better Maximal Sum
削除を使わない場合、末尾が a[i] であるような最大部分列は
- 末尾が a[i-1] の部分列に a[i] を付け加えたもの
- a[i] ひとつだけ
のどちらかである。ということで次のような DP を行えばいい。
- dp[i][j] := 末尾の要素が a[i] で、j 回削除を行った最大部分列
更新式はこんな感じ。
- dp[i][0]=max(dp[i-1][0]+a[i], a[i])
- dp[i][1]=max(dp[i+1][1]+a[i],dp[i][0])
SnackDown Online Qualifier 2016 » Better Maximal S ...
K-good Words
文字の出現頻度しか関係ないので、頻度 freq だけ見てあげる。
s が K-good であるというのは、freq の最小値と最大値の差が K 以下であるということと同じことである。
最小値を削るのは無駄なので、 freq=[2,3,5,5,5], K=1 だったら、freq=[2,3,3,3,3] みたいに削ればいい。
ただこれだと freq=[1,10,11,12], K=2 みたいなケースのときに freq=[1,3,3,3] と削ってしまう。本来であれば freq=[0,10,11,12] とするのが最善。
このようなケースを網羅するために、最小から i 個を 0 にした上で削るように修正する。
SnackDown Online Qualifier 2016 » K-good Word
Floor Division Game
実験してみると g(n)=g(n/12) が予想できる。予想が正しいことを n に関する帰納法で示そう。
1..n-1 で成り立っているとすれば、
$$ \begin{align} g(n)&=\mathrm{mex} \left( g\left( \frac{n}{2} \right), g \left( \frac{n}{3} \right) , \ldots, g \left( \frac{n}{6} \right) \right)\\ &=\mathrm{mex} \left( g\left( \frac{n}{2\cdot 12} \right), g \left( \frac{n}{3\cdot 12} \right) , \ldots, g \left( \frac{n}{6\cdot 12} \right) \right) \end{align} $$
である。一方で、
$$ g\left(\frac{n}{12}\right)=\mathrm{mex} \left( g\left( \frac{n}{2\cdot 12} \right), g \left( \frac{n}{3\cdot 12} \right) , \ldots, g \left( \frac{n}{6\cdot 12} \right) \right) $$
なので g(n)=g(n/12) が成り立っている。
サラッと書いたけど次の性質が証明には使われている。
$$ \left\lfloor \frac{\left\lfloor a/b \right\rfloor}{c}\right\rfloor= \left\lfloor \frac{\left\lfloor a/c \right\rfloor}{b}\right\rfloor= \left\lfloor \frac{a}{bc} \right\rfloor $$
数学的帰納法は予想が正しいことを示すのには楽なんだけど、どうしても天下り的になってしまい良くない。要するに 12 が鍵になる理由が分からない。
SnackDown Online Qualifier 2016 » Floor Division G ...
解くときサイトが妙に重かったけど大丈夫なのかな…。
