SnackDown Online Pre-elimination round A
https://www.codechef.com/SNCKPA16
Art
A の中に同じ値が 3 つ以上連続している部分がないと作れないのは明らか。逆に 3 つ以上連続している部分があればどのような数列でも構成できる。
時間を逆行させて考えてみると、一度塗った場所は塗り替えられないと見なせる。
例えば [1, 2, 3, 3, 3, 4, 5] という数列を塗りたければ、次のような手順で塗ればいい。
[-, -, -, -, -, -, -] [-, -, 3, 3, 3, -, -] [-, 2, 3, 3, 3, -, -] [1, 2, 3, 3, 3, -, -] [1, 2, 3, 3, 3, 4, -] [1, 2, 3, 3, 3, 4, 5]
このように、3 つ連続している部分から 1 マスずつ塗り広げていくことで構成することができる。
N different palindromes
同じ文字を N 回繰り返した文字列は N(N+1)/2 個の回文を含む。
aaaaaa + bbbbbbb + ccc + ... のように文字列を構成すれば、x(x+1)/2+y(y+1)/2+z(z+1)/2+.... 個の回文を持つ部分列を作れる。
Sharing Candies
|(A+Cx)-(B+Dy)| を x,y≧0 のもとで最小化する問題。Cx-Dy が任意の gcd(C,D) の倍数を取れることを使えば、解は(A-B) mod gcd(C,D) 周辺になることが分かる。
Cx-Dy が任意の gcd(C,D) の倍数を取れることを一応証明しておく。
方程式
$$ ax-by=g $$
の整数解は当然存在し、その一般解はどちらも
$$ x=kb+x_0, \quad y = ka + y_0 $$
と表せる。$k$ を十分大きく取ることで $x,y \ge 0$ の解が作れる。
方程式
$$ ax-by=-g $$
の非負整数解も同様に存在する。この 2 つの解を使えば $ax-by=ng$ の解を構成できる。
Longest Increasing Subsequence
x..N の順列はもう作ってあるとする。x-1,x-2,x-3 を下図のように配置すればパターン数を 3 倍にできる。
x..N の LIS長が 4 だったら下図のように 4 つ付け加えるとパターン数を +1 できる。
x..N の LIS長が 4 だったら下図のように 4 つ付け加えるとパターン数を +2 できる。
x3, +1,+2 を駆使すれば 3 進法の原理ですべてのパターン数を構成できる。なんでわざわざ 3 進法にしたかというと、2進法だと 100 個で収まらないため。+1 するのに LIS 長分だけ必要なのが痛い。
Chef and Super Array
現在の数列を a[n]、操作後の数列を a'[n] とすると、次のような漸化式が成り立つ。
$$ a'[n] = \begin{cases} a\left[\frac{n+1}{2}\right]+a\left[\frac{n-1}{2}\right] & (n \bmod 2 = 1) \\ a\left[\frac{n}{2}\right] & (n \bmod 2 = 0) \end{cases} $$
これの総和 S[n]=a[0]+a[1]+...+a[n] の漸化式は次のように機械的に立てられる。
$$ S'[n] = \begin{cases} a\left[\frac{n+1}{2}\right]+a\left[\frac{n-1}{2}\right]+S'[n-1] & (n \bmod 2 = 1) \\ a\left[\frac{n}{2}\right]+S'[n-1] & (n \bmod 2 = 0) \end{cases} $$
S'[n-1] を展開していく。面倒なので n mod 2 = 1 の方だけ。
$$ \begin{align} S'[n] &= a_{\frac{n+1}{2}} +a_{\frac{n-1}{2}} + S'[n-1] \\ &= a_{\frac{n+1}{2}} +a_{\frac{n-1}{2}}+a_{\frac{n-1}{2}}+S'[n-2] \\ &= a_{\frac{n+1}{2}} +a_{\frac{n-1}{2}}+a_{\frac{n-1}{2}} + a_{\frac{n-1}{2}} +a_{\frac{n-3}{2}} + S'[n-3] \\ &= a_{\frac{n+1}{2}} +a_{\frac{n-1}{2}}+a_{\frac{n-1}{2}} + a_{\frac{n-1}{2}} +a_{\frac{n-3}{2}} + a_{\frac{n-3}{2}} + S'[n-4] \\ &= a_{\frac{n+1}{2}} +a_{\frac{n-1}{2}}+a_{\frac{n-1}{2}} + a_{\frac{n-1}{2}} +a_{\frac{n-3}{2}} + a_{\frac{n-3}{2}} + a_{\frac{n-3}{2}} +a_{\frac{n-5}{2}} + S'[n-5] \\ \end{align} $$
このぐらいまで展開すれば
$$ S'[n]=a\left[\frac{n+1}{2}\right]+3 S\left[\frac{n-1}{2}\right]-a[0] $$
が分かる。最後の a[0] は忘れないように。n mod 2=0 の方も上の計算過程を使い回せば
$$ S'[n]=2a\left[\frac{n}{2}\right]+3S\left[\frac{n-2}{2}\right]-a[0] $$
が分かる。結果をまとめると次のようになる。
$$ S'[n] = \begin{cases} a\left[\frac{n+1}{2}\right]+3 S\left[\frac{n-1}{2}\right]-a[0] & (n \bmod 2 = 1) \\ 2a\left[\frac{n}{2}\right]+3S\left[\frac{n-2}{2}\right]-a[0] & (n \bmod 2 = 0) \end{cases} $$
S[n] の計算量は a[n] の計算量に定数が掛かるだけなので、問題になるのは a[n] の計算量。適当に大きい数で試してみると a[n] も一瞬で求まるのでこれで OK。
分岐しにくいから大抵のケースで速いのは分かるけど、最悪ケースだとどうなのかと言われると微妙。
Chef and his study plans
ほぼ区間スケジューリング問題だが、[L,R] に完全に含まれる区間しか使えないという点で少し異なる。
ある区間を使ったとき、その次に使うべき区間を予め計算しておく。
そうすると、左端が L 以上で右端が最小の区間を k としたとき、k→k'→k''→k'''→…と進めていけば最大区間数が求まる。 しかしこれでは最悪 O(n) ステップ掛かってしまう。
この操作を高速化するには 20,21,22,23,... 個先の区間も前計算しておけばいい。こうすることで二分探索により最後の区間を求めることができる。
Chef and his study で手元のランダムテストでは正しく動くバグを埋め込んでしまい辛かった。誤読を疑ったが配列外参照が原因だった…。
