pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 ...

解くときサイトが妙に重かったけど大丈夫なのかな…。