AtCoder Regular Contest 074

2017年5月20日のAtCoderの記録。言語はRubyです。

問題はこちら：AtCoder Regular Contest 074
私の回答一覧はこちら：自分の結果
制限時間100分で、20分でC、86分経過でDを正解して2問完答。

#C問題
切り方を正しく4通り思いつくことができたので、それぞれの切り方について最小値を取って、全体の最小値を求める。
最初のカットは全体の1/3となるようにすればよい。幅がWのとき、1/3に近いものを切る場合はW/3 (小数切り捨て)の場合とW/3 + 1の場合だけを考える。それ以外だと全体の1/3から離れてしまうので最適解になりえない(あまり厳密な証明はしていないけど、直感的には1/3のすぐ上とすぐ下の整数だけ考えれば良い。)

h, w= gets.split(" ").map{ |v|
	v.to_i
}

ans = 100000 * 10000

# 最初を縦に切る
w1 = w / 3

if ((w - w1) % 2 == 0 || h % 2 == 0) then
	tem = ((w-w1)*h/2 - w1 * h).abs
	ans = [tem, ans].min
else
	temarr = [w1*h, (w-w1)/2*h, ((w-w1)/2+1)*h ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
	
	temarr = [w1*h, (w-w1)*(h/2), (w-w1)*(h/2+1) ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
end

w1 = w / 3 + 1

if ((w - w1) % 2 == 0 || h % 2 == 0) then
	tem = ((w-w1)*h/2 - w1 * h).abs
	ans = [tem, ans].min
else
	temarr = [w1*h, (w-w1)/2*h, ((w-w1)/2+1)*h ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
	
	temarr = [w1*h, (w-w1)*(h/2), (w-w1)*(h/2+1) ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
end

#最初を横に切る
h1 = h / 3
if ((h - h1) % 2 == 0 || w % 2 == 0) then
	tem = ((h-h1)*w/2 - h1 * w).abs
	ans = [tem, ans].min
else
	temarr = [h1*w, (h-h1)/2*w, ((h-h1)/2+1)*w ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
	
	temarr = [h1*w, (h-h1)*(w/2), (h-h1)*(w/2+1) ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
end

h1 = h / 3 + 1
if ((h - h1) % 2 == 0 || w % 2 == 0) then
	tem = ((h-h1)*w/2 - h1 * w).abs
	ans = [tem, ans].min
else
	temarr = [h1*w, (h-h1)/2*w, ((h-h1)/2+1)*w ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
	
	temarr = [h1*w, (h-h1)*(w/2), (h-h1)*(w/2+1) ]
	tem = temarr.max - temarr.min
	ans = [tem, ans].min
end

puts ans

多分もうちょっと簡潔に書く方法はあると思うけど、速さ重視だったのでコピペを使って済ませた。

#D問題
これはパッと見て色々なやり方を考えつくことができる。そのうちどれが「筋がいい」やり方なのか素早く判断することが必要。

競技中の実際の考えを書き殴ってみる。
(1) N=1で試してみる→よくわからない
(2) 「3N個の数から1つずつ削除しながら、先頭N個の和 - 末尾N個の和 を計算する」で貪欲法かな? →一見良さそうだが反例っぽいものを思いついた。先頭N個や末尾N個の中から削除していくなら良いが、真ん中の数から削除していく必要があるケースが難しい。

以下の2つの場合を区別できないと思うので、この方法では無理
10, 10, 1, 7, 5, 1 →7と5を削除して10, 10, 1, 1が正解。5を最初に削除するのは「最初は損だけど最終的には得」となる
10, 10, 9, 7, 5, 1 →9と7を削除して10, 10, 1, 1が正解。5を最初に削除するのはダメ

(3) ラチがあかなくなったので極端なケースを考える。
もとの数が大きい順に並んでいるならば答えは明らかで、O(N)で答えが出せる
もとの数が小さい順に並んでいるなら?
最適解は「ある仕切り線を考えて、その左側N個と右側N個」という形に必ずなるはず。仕切り線を(N+1)個試せば良い。そして、仕切り線を1つ右にずらしたときの合計値は、左端の数を引いて右端の数を足せば良いので、定数時間で求められる。結果、O(N)で答えが出せる

と、ここまで来てやっと「仕切り線に着目すればよさそう」と気づく。
仕切り線を1つ固定したときの値は、ソートしてから上位／下位N個を取り出せばよいので、O(NlogN)で求められる。全体はO(N^2・logN)で求められる。部分点の解法はこれで良い。

満点の解法は、入力個数の最大値から考えておそらくO(N)だろう。

ということは仕切り線を一つ右にずらした場合の計算を、定数時間で済ませねばならない。それは無理だろう……ということで部分点解法を書いて提出。

解説を見て気づいた、満点解法にたどり着くために足りなかったこと2つ。
優先度付きキューという概念を知らなかった。これは知識の問題なので仕方ない。
2点目はアルゴリズム上の工夫。**仕切りの右と左は独立なので、同時に求める必要はない。したがって別個に考えてよく、すると右と左で同一の方法が使える。**つまり、「仕切りの左側をN個→2N個に増やしながら、それぞれの数を求める。次に仕切りの右側をN個→2N個に増やしながら(このとき仕切りは左側に動く)、それぞれの数を求める。」という感じ。
「仕切りを左から右に動かしていくから、仕切りの左側はN個から増えていく、同時に右側は2N個から減っていく……」という考えをしてしまった。

n = gets.to_i
arr = gets.split(" ").map{ |v|
	v.to_i
}

ans = - (10 ** 15)
n.upto(2*n) { |b|
	tem = arr[0..b-1].sort.reverse[0..n-1].inject(:+) - arr[b..3*n-1].sort[0..n-1].inject(:+)
	if ans < tem then
		ans = tem
	end
}

puts ans

パフォーマンスは1571、レートは1318→1349(+31)。