2017年7月9日のAtCoderの記録。言語はRubyです。
問題はこちら：AtCoder Grand Contest 017
私の回答一覧はこちら：自分の結果
制限時間120分で、14分でA、38分経過でBを正解して2問完答。
残り1時間程度Cを考えていたが、まるで解けなくて諦めた。
#A問題
1次元DP。
e[i], o[i]を「1番めからi番目までに対して、問題の通り選んで合計が偶数/奇数になる場合の数」とする。
a_iが偶数ならば
e[i] = e[i-1] * 2
o[i] = o[i-1] * 2
a_iが奇数ならば
e[i] = o[i] = e[i-1] + o[i-1]
である。これを実装すればよい。
#B問題
最初「DPっぽいなー、今日DPばっかなのかな」と言いながら考えたが、DPだと上手く行かなかった。以下、DPの解法。
DP[len][dif] を、「両端の差がdifであり、全部でlen個のマスがあるときに、条件を満たす数の書き込みができるかできないか(true/false)」だと考える。(dif $\geq$ 0の部分だけ考えればよい。)
DP[2][dif] = true (C $\leq$ dif $\leq$ Dの場合) , false(それ以外の場合)である。
DP[n+1][dif] がtrueになるのは
「dif+C $\leq$ i $\leq$ dif+D または dif-D $\leq$ i $\leq$ dif-C 」かつ DP[n][i] = true となるiが存在するときである。それ以外のときはfalseである。
ここでDP表のサイズを考えると、nは2からNまで求めればよいが、問題はiだ。正確な条件は求めていないが、最大で $10^9$程度になるのは間違いない。これでは時間が足りない。この解法ではダメだ。
ここまで来て行き詰まって、サンプルを見て「1,−1,3,7,5」という答えに「何で最初から減少するんだよ、増加させればいいのに……あっ、増加と減少でまとめれば良いんだ」と気づいた。
増加と減少の個数は合計で(N-1)回。N' = N-1として、増加がp回、減少が(N'-p)回ならば、
B-Aの最大値はDp - C(N'-p)
B-Aの最小値はCp - D(N'-p) であり、
さらにこの2つの間の全ての数はB-Aの値として取ることができる。
あとはpが全ての場合について計算して、どれかのpに対して最大値と最小値の間に入ってたらYES、そうでなければNOだ。
n,a,b,c,d = gets.split(" ").map { |v|
v.to_i
}
n = n - 1
dif = b-a
for p in 0 .. n do
difmax= d * p - c * (n-p)
difmin= c * p - d * (n-p)
if difmin <= dif and dif <= difmax then
puts "YES"
exit
end
end
puts "NO"
#C問題
問題の意味は理解して、方針を立てて書いてみたものの、例題に対して違う結果が出てきて、「あっこれじゃダメじゃん」
大きい順にソートしてから数字を変換しようと思ったけど、数字を変換した後が大きい順になっているままとは限らないことに気づくのが遅れた。
解答にあるような「数直線上の区間をすべてカバーするか」という話に置き換えられないと、正答にたどり着くのは無理なのかなー。だとすると、結構難しい発想を要求している気がする。
パフォーマンスは過去最高の1888、レートは1349→1423(+74)。
今回は名前が黄色(2000~2400)やオレンジ(2400~2800)でも「30分以内にABを解いたけどその後C以降が解けない」という人がいたようだ。C問題以降がどれもだいぶ難しかったということだろう。