【AHC034】AHC034をRubyで解いたことを今更振り返る【AtCoder】
AHC034 の参加しましたのでその振り返りを
やっと記事を書くモチベが上がったので AHC034 を振り返ります
結果としては 971 人中 337 位でパフォーマンスは 1480 でした
結構シンプルな問題でやりやすかったです
Web 版のビジュアライザで動きを試しやすく見ていて面白いので AHC 始めたての人にはよいかもしれません
自分の点数は 4,974,294,229 点でした
ではどのように解いたか振り返っていきます
A - Leveling with a Dump Truck
20 * 20 のマスに土砂が敷き詰められておりダンプカーで土砂を積んだり掘ったして整地する問題です
初めの状態として土砂が盛り上がっているマスもあれば掘られてへこんでいるマスもあります
これをいかに早く整地できるか、たくさん積まずに運べるかを考える必要があります
解き方
初めに行った方法として先に盛り上がっている土砂を積めるだけ積みへこんでいるマスに埋めていく方法をとりました...が結果としてこの方法だと全然点が伸びなかったです
なぜ点数が低いのか考えたところ
この問題において大事なのは如何に移動せずに整地するかではなく如何にダンプカーに積まずに整地できるかということに気が付きました
次にとった方法として行ごとに完結できるものから整地化していくというものです
例えば ダンプカーの積載量が0の時以下の行のマスの場合だとどうでしょうか？
10 10 10 10 10 10 10 10 10 10 -10 -10 -10 -10 -10 -10 -10 -10 -10 -10
その行の土砂量を平均すると 0 で整地化した後でもダンプカーの積載量は0のままになります
しかし 以下の行の場合ではどうでしょうかす
100 100 100 100 100 100 100 100 100 100 -10 -10 -10 -10 -10 -10 -10 -10 -10 -10
この行を整地化しても大量の土砂がダンプカーに積まれて残ってしまいます
大量の土砂がダンプカーに積まれてしまうと移動するコストも増えてしまうのでよくありません
そのため整地化してもダンプカーにできるだけ土砂が残らない順に整地するようにしました
基本的にはこの動きで行うようにして小さな改善も加えました
- 行だけで判断せず列の場合も試しよりスコアが高い方法を選ぶ
- ある時点で少しダンプカーに土砂が積まれていた場合はその土砂量も考慮して整地する行(または列)を選ぶ
最終的な動きはビジュアライザを見てもらうとわかりやすいと思います
ソースコード
実装は汚いので見る必要はないです
def main
# 計測開始
start_time = Time.now
n = int
jun = []
mm = []
map = []
n.times do |i|
now = intary
mm << now
jun << [i, now.sum]
end
mm.each do |i|
map << i.dup
end
tatejun = []
map.transpose.each.with_index do |v, i|
tatejun << [i, v.sum]
end
mirujun = []
tatemirujun = []
# pp jun
cost = 0
zanmiru = 1000000
kesuin = 0
20.times do
zanmiru = [11111, 1000000]
jun.each.with_index do |i, index|
if i[1] >= cost
if i[1] - cost <= zanmiru[1] - cost
zanmiru = i
kesuin = index
end
end
end
mirujun << zanmiru[0]
jun.delete_at(kesuin)
cost -= zanmiru[1]
end
cost = 0
zanmiru = 1000000
kesuin = 0
20.times do
zanmiru = [11111, 1000000]
tatejun.each.with_index do |i, index|
if i[1] >= cost
if i[1] - cost <= zanmiru[1] - cost
zanmiru = i
kesuin = index
end
end
end
tatemirujun << zanmiru[0]
tatejun.delete_at(kesuin)
cost -= zanmiru[1]
end
cost = 0
x = 0
y = 0
dump = 0
tatecost = 0
x = 0
dump = 0
y = 0
tatedousa = []
tatemirujun.each do |ii|
#所定の列へ移動
if x >= ii
(x - ii).times {tatedousa << "L"}
tatecost += (x - ii) * 100
else
(ii - x).times {tatedousa << "R"}
tatecost += (ii - x) * 100
end
x = ii
# 下まで行き戻る
(0..19).each do |i|
if map[i][ii] > 0
tatedousa << "+#{map[i][ii]}"
dump += map[i][ii]
tatecost += 100 + dump + map[i][ii]
map[i][ii] = 0
elsif map[i][ii] <= -1
if dump == 0
elsif -map[i][ii] > dump
tatedousa << "-#{dump}"
tatecost += dump
map[i][ii] += dump
dump = 0
else
tatedousa << "-#{-map[i][ii]}"
tatecost += -map[i][ii]
dump -= -map[i][ii]
map[i][ii] = 0
end
end
tatedousa << "D"
end
tatedousa.pop
(0..19).each do |i|
i = 19 - i
if map[i][ii] > 0
tatedousa << "+#{map[i][ii]}"
dump += map[i][ii]
tatecost += 100 + dump + map[i][ii]
map[i][ii] = 0
elsif map[i][ii] <= -1
if dump == 0
elsif -map[i][ii] > dump
tatedousa << "-#{dump}"
tatecost += dump
map[i][ii] += dump
dump = 0
else
tatedousa << "-#{-map[i][ii]}"
tatecost += -map[i][ii]
dump -= -map[i][ii]
map[i][ii] = 0
end
end
tatedousa << "U"
end
tatedousa.pop
end
nowcost = 0
x = 0
dump = 0
y = 0
dousa = []
map = []
mm.each do |i|
map << i.dup
end
mirujun.each do |ii|
#所定の行へ移動
if y >= ii
(y - ii).times {dousa << "U"}
nowcost += (y - ii) * 100
else
(ii - y).times {dousa << "D"}
nowcost += (ii - y) * 100
end
y = ii
# 右端まで行き戻る
(0..19).each do |i|
if map[ii][i] > 0
dousa << "+#{map[ii][i]}"
dump += map[ii][i]
nowcost += 100 + dump + map[ii][i]
map[ii][i] = 0
elsif map[ii][i] <= -1
if dump == 0
elsif -map[ii][i] > dump
dousa << "-#{dump}"
nowcost += dump
map[ii][i] += dump
dump = 0
else
dousa << "-#{-map[ii][i]}"
nowcost += -map[ii][i]
dump -= -map[ii][i]
map[ii][i] = 0
end
end
dousa << "R"
end
dousa.pop
(0..19).each do |i|
i = 19 - i
if map[ii][i] > 0
dousa << "+#{map[ii][i]}"
dump += map[ii][i]
nowcost += 100 + dump + map[ii][i]
map[ii][i] = 0
elsif map[ii][i] <= -1
if dump == 0
elsif -map[ii][i] > dump
dousa << "-#{dump}"
nowcost += dump
map[ii][i] += dump
dump = 0
else
dousa << "-#{-map[ii][i]}"
nowcost += -map[ii][i]
dump -= -map[ii][i]
map[ii][i] = 0
end
end
dousa << "L"
end
dousa.pop
end
if nowcost <= tatecost
dousa.each do |i|
puts i
end
else
tatedousa.each do |i|
puts i
end
end
end
#----------------------------------------------------------------------------------
require "set"
def int
gets.chomp.to_i
end
def intary
gets.chomp.split(" ").map(&:to_i)
end
main
感想
TOPの人の解答を見ると特定の列または行に一度土砂をためて管理し適切に土砂を埋めて最後にその土砂をためたラインを整地する方法でした
シンプルな方法ですが自分には思いつかないのでさすがだと思います
またこの程度の動きであれば茶や緑のコーダーでも実装できるので今回は本当に発想次第で伸ばせれる問題だったのだなと感じました
今回は比較的上位に食い込めた(当社比)のでモチベがとても上がりました
早く水色になれるように今後も頑張っていきます
Discussion