naoya_t@hatenablog

いわゆるチラシノウラであります

CodeChef SnackDown2017 Online Elimination Round

f:id:n4_t:20170604112955p:plain
https://www.codechef.com/SNCKEL17
6/3土23:00 JST〜5時間(全11問)
Online Pre-Elimination Round A/B で勝ち上がった3403チーム (=A:1469 B:1934) が出場。
オンサイト決勝進出枠は57チーム、Tシャツは上位300チーム。

前回に引き続きケロン軍っぽいチーム(※メンバー1名)で
5時間頑張って、結果1完で758位;
(ボーダーは決勝が7完、Tシャツが4完だった)

Chef and Pairs (CHEFPRAD; 486, Accuracy=18.29%)

https://www.codechef.com/SNCKEL17/problems/CHEFPRAD
最大マッチング。辺が引かれたり引かれなかったり。
式を変形して…

plusmulのほうが解いてる人多かったので後回しにする

Add or Multiply (PLUSMUL; 1107, Accuracy=30.6%)

https://www.codechef.com/SNCKEL17/problems/PLUSMUL

[a,b,c]みたいな数列が与えられたとき、+とxを挟んで作れる a+bc みたいな式を全パターン作って合計を求める

掛け算部分の結果と足し算部分の結果に分割可能
掛け算部分は abc + ab + bc + ca
= (a+1)(b+1)(c+1) - (a+b+c-1)
みたいに求められる?とか思ったけど…
今回ca入らないでしょ
a+b+c, a+bc, ab+c, abc の4=2^(3-1)通り。
この合計は 2a+b+2c + ab+bc + abc
各項の値の計算はn=3だからまだ余裕だけど、n=100000とか行くわけで。DPで解けないと無理だ。DPで解けるに違いない。
n=2までの結果からn=3が導けるのか?
f(0) = ∅

f(1) = a
L(1) = |f(1)| = 2^(1-1) = 1
g(1) = aとおくと // L(0)+g(0)=1
f(1) = ∅ + g(1)
= Σ^(1-1) f(i) + g(1)

f(2) = a+b, ab
= 各f(1)+b + ab
= f(1) + L(1)b + ab
= f(1) + (L(1) + a)b
g(2) = (L(1) + g(1))bとおくと
= f(1) + g(2)
= Σ^(2-1) f(i) + g(2)

f(3) = a+b+c, a+bc, ab+c, abc
= [(a+b), (ab)]+c, [a]+bc, abc
= 各f(2)+c + 各f(1)+bc + abc
= f(2) + L(2)c + f(1) + L(1)bc + abc
= {f(2) + f(1)} + (L(2) + L(1)b + ab)c
= {f(2) + f(1)} + (L(2) + (L(1) + a)b)c
g(3) = (L(2) + g(2))cとおくと
= f(2)+f(1) + g(3)
= Σ^(3-1) f(i) + g(3)

てな感じでDPして行って f(n) を求められるね
→AC

Mex division (MEXDIV; 682, Accuracy=41.15%)

https://www.codechef.com/SNCKEL17/problems/MEXDIV

k ≧ n の場合
例えばk=5, n=5 (即ちa.size()==5)の場合、0,1,2,3,4,5 のうち少なくとも1つはaに含まれないから mex値は必ず5以下になる。
なので長さnなら、n-1箇所の分割ポイントの取り方の問題なので (n-1)C0 + (n-1)C1 + ... + (n-1)C(n-1) = 2^(n-1) 通り

k < n の場合
mexがkを上回ることがあり得るので左から見ていく
計算量減らしたいから尺取りになるように

TLE→WA→WA…
TLEはO(n^2)してたせい 。尺取りがちゃんと尺取りしてなかった

k=0の場合おかしくなるのは気づいて直したんだけど

検算のためにa[]をreverseしたものを食わせてみたら値が違う
(本来同じ結果になるべきでしょ)
直せずに試合終了