2017年4月22日のAtCoderの記録。言語はRubyです。
問題はこちら：AtCoder Regular Contest 072
私の回答一覧はこちら：自分の結果
制限時間100分で、30分でD、90分経過でCを正解して2問完答。
もしABCだったらAとBの問題も解かなきゃいけなかったから、Dまで全問正解できなかったと思うとあんまり良くない。まぁ、レートが伸びたから良いとしよう。
C問題
何で手間取ったかというと「何かDPっぽい」と直感で考えてしまい、DPに囚われてしまったからである。正解は……これ、何になるんだろう。「貪欲法」って書いてた人を見かけたけど、貪欲で良いのかな。
「DPかなぁ」と
問題の例で言うと、「1 -3 1」は2回の操作で「1 -2 2」にできる。初項から第i項までの和は1, -1, 1で条件を満たす。
1つ増えて「1 -3 1 0」となった場合、まず2回の操作で「1 -2 2 0」とすると3つ目まではOK。あとは2回の操作で4つ目を-2にすれば全体が条件を満たす。めでたしめでたし……
一見上手く行くようだが、それは間違いである。「1 -3 1」の末尾に100を付け加えて「1 -3 1 100」となった場合、第4項を100から-2にするためには102回の操作をしなければいけない。この場合は、符号を逆にして「-1 2 -2 100」とすれば条件を満たし、操作は2+5+3 = 10回で済むのだ。ここで問題は、この「-1 2 -2 100」という列を考えるときに、改めて最初から考え直さなきゃいけないこと。
DPの表を埋めていく際に、1つのマスに入る値を求めるときに少し前の値をいくつか参照して計算すれば良い。そういう局所的な関係だけで解けるからDPなのだ。最後の一つのせいで最初からもう一度再計算しなきゃいけないような場合は、DPになり得ないということに気づけば早めにDPを捨てられたのに。
あとは単に「DPかな?」じゃなくて「どういう条件でDPテーブルを作れば良いか?」まで突っ込んで考えるべきだった。 DP[i][j]というような表を作るとして、「最後の1つを除いたときの操作回数がi、最後の値がj」か?いやそれが無理なのは前述のとおりだ。では……と考えると、上手いDPテーブルの作り方がないとわかり、DPの線を捨てられる。
一応、書いたコードも載せておく。arr2には全体を-1倍した配列を入れておいて、前半と同じように考えている。
N = gets.to_i
arr = gets.split(" ").map{ |v|
v.to_i
}
ans1 = 0
sum = 0
0.upto(N-1){ |i|
sum = sum + arr[i]
if i % 2 == 0 and sum <= 0 then
ans1 += (1 - sum)
sum = 1
elsif i % 2 == 1 and sum >= 0 then
ans1 += (sum - (-1))
sum = -1
end
}
arr2 = arr.map{ |v|
-v
}
ans2 = 0
sum = 0
0.upto(N-1){ |i|
sum = sum + arr2[i]
if i % 2 == 0 and sum <= 0 then
ans2 += (1 - sum)
sum = 1
elsif i % 2 == 1 and sum >= 0 then
ans2 += (sum - (-1))
sum = -1
end
}
puts [ans1 ans2].min
D問題
糸口がつかめなかったので、まず小さな数に対して勝ち負けを求めていった。
しばらく見ても条件がわからなかったが、「2-1だと負けパターンなのに、3-1と4-1と5-1だと全て勝ちパターン……ということは、2つの数の差が大きいと勝ちパターンなのか?」という点に気づき、2つの差を取ってみた。すると
- 2つの数の差が1以下だと負けパターン
- 2つの数の差が2以上だと勝ちパターン
という予想が立った。上記が実際に勝ちパターン／負けパターンであることを実際に示すには、以下の2つが示せれば良い。
- 「2つの数の差が1以下」の場合、どんな手を選んでもその結果は「2つの数の差が2以上」になってしまう
- 「2つの数の差が2以上」の場合。うまい手を選べば「2つの数の差が1以下」の負けパターンで相手の番にすることができる
略証：1回の操作は、「片方の山から2個減らし、逆の山を1個増やす」を何回か繰り返している。従って、石の個数をX,Yとしたとき、操作の前と後でX-Yは3の倍数だけ変化する。「2つの数の差が1以下」と「X-Yが-1, 0, 1のいずれか」が同値。|X-Y|が2以上ならば、適切に操作してX-Yがこの3つのいずれかになるようにできる。逆に、何らかの操作をすればX-Yが3以上増減するから、「X-Yが-1, 0, 1のいずれか」ならば、操作後のX-Yは必ずこの範囲外になる。
というわけで、コードは滅多にないほど簡単で済む。
a,b = gets.split(" ").map{ |v|
v.to_i
}
puts (a-b).abs <= 1 ? "Brown" : "Alice"
パフォーマンスは過去最高の1779、レートは1226→1306(+80)。