START_TIME = Time.utc.to_unix_ms TL = (ENV["TL"]? || 1900).to_i N = 3000 L = 14 T = 400 INF = 1_000_000_000 RND = Random.new(2) DP = [L, -1, -L, 1] DIR_DOWN = 0 DIR_LEFT = 1 DIR_UP = 2 DIR_RIGHT = 3 DIST_NORMAL = 360 DIST_HIGHWAY = 81 # 距離 % 40 で高速を使った本数がわかる INITIAL_MONEY = 1_000_000i64 MAX_EDGE_CNT = (ENV["MEC"]? || 20).to_i MAX_WORK_TH = 50_000i64 macro debug(msg) {% if flag?(:local) %} STDERR.puts({{msg}}) {% end %} end macro debugf(format_string, *args) {% if flag?(:local) %} STDERR.printf({{format_string}}, {{*args}}) {% end %} end def crash(msg, caller_line = __LINE__) puts "[ERROR] line #{caller_line}: #{msg}" exit end macro assert(cond, msg = "", caller_line = __LINE__) {% if flag?(:local) %} if !({{cond}}) crash({{msg}}, {{caller_line}}) end {% end %} end struct Build def initialize(@y0 : Int32, @x0 : Int32, @y1 : Int32, @x1 : Int32) end def to_s(io) io << "1 #{@y0 + 1} #{@x0 + 1} #{@y1 + 1} #{@x1 + 1}" return io end end struct Gather def initialize end def to_s(io) io << "2" return io end end struct Work def initialize end def to_s(io) io << "3" return io end end alias Action = (Build | Gather | Work) struct Pos getter :p def initialize(y : Int32, x : Int32) @p = y * L + x end end struct Edge getter :y, :x, :dir def initialize(@y : Int32, @x : Int32, @dir : Int32) end end struct Strategy getter :work_th def initialize(@work_th : Int64) end end def calc_dist(graph, dist) dist.each { |v| v.fill(INF) } q = [] of Tuple(Int32, Int32) (L * L).times do |i| q.clear q << {i, 0} dist[i][i] = 0 qi = 0 while qi < q.size cp, cd = q[qi] qi += 1 next if dist[i][cp] < cd dist[cp][i] = cd 4.times do |dir| next if graph[cp][dir] == INF np = cp + DP[dir] nd = cd + graph[cp][dir] if nd < dist[i][np] # if i == 0 # debug([cp, np, nd]) # end dist[i][np] = nd q << {np, nd} end end end end end class Solver def initialize read_line @ps = Array(Tuple(Int32, Int32)).new @sps = Array(Array(Int32)).new(L * L) { [] of Int32 } N.times do a, b, c, d = read_line.split.map { |v| v.to_i - 1 } @ps << {a * L + b, c * L + d} @sps[a * L + b] << c * L + d end @graph = Array(Array(Int32)).new(L * L) do |i| r = i // L c = i % L d = [DIST_NORMAL, DIST_NORMAL, DIST_NORMAL, DIST_NORMAL] if r == 0 d[DIR_UP] = INF elsif r == L - 1 d[DIR_DOWN] = INF end if c == 0 d[DIR_LEFT] = INF elsif c == L - 1 d[DIR_RIGHT] = INF end d end @dist = Array(Array(Int32)).new(L * L) do Array.new(L * L, INF) end @money = INITIAL_MONEY @member = 1 end def solve best_score = 0i64 best_actions = [] of Action turn = 0 while true if Time.utc.to_unix_ms - START_TIME > TL debug("total_turn=#{turn}") break end es = create_highway(MAX_EDGE_CNT - turn % 10) es.each do |e| @graph[e.y * L + e.x][e.dir] = DIST_HIGHWAY @graph[e.y * L + e.x + DP[e.dir]][e.dir ^ 2] = DIST_HIGHWAY end ecs = count_used_edge(@graph, es) es = es.size.times.to_a.sort_by { |i| -ecs[i] }.map { |i| es[i] } work_th = 50000 edge_cnt = es.size while true if Time.utc.to_unix_ms - START_TIME > TL break end es.each do |e| @graph[e.y * L + e.x][e.dir] = DIST_NORMAL @graph[e.y * L + e.x + DP[e.dir]][e.dir ^ 2] = DIST_NORMAL end strategy = Strategy.new(work_th) actions, score = simulate(es[0, edge_cnt], strategy) debug([work_th, edge_cnt, score]) if score > best_score best_score = score best_actions = actions end work_th *= 2 if work_th >= MAX_WORK_TH work_th = 50000 edge_cnt -= 1 break if edge_cnt == 5 end end turn += 1 end return best_actions, best_score end def simulate(es, strategy) @money = INITIAL_MONEY @member = 1 ret = [] of Action build_cnt = 0 use_cnt = 0 T.times do # if @member < strategy.initial_member # ret << Gather.new # @member += 1 # next # end if build_cnt == es.size ret << Work.new @money += 50000 elsif @money > 10_000_000i64 / (@member ** 0.5) @money -= (10_000_000i64 / (@member ** 0.5)).floor.to_i64 e = es[build_cnt] @graph[e.y * L + e.x][e.dir] = DIST_HIGHWAY @graph[e.y * L + e.x + DP[e.dir]][e.dir ^ 2] = DIST_HIGHWAY if e.dir == DIR_DOWN ret << Build.new(e.y, e.x, e.y + 1, e.x) else ret << Build.new(e.y, e.x, e.y, e.x + 1) end build_cnt += 1 calc_dist(@graph, @dist) use_cnt = 0 @ps.each do |p| use_cnt += @dist[p[0]][p[1]] % 40 end # debug("build_cnt=#{build_cnt} use_cnt=#{use_cnt}") else cur_cost = (10_000_000i64 / (@member ** 0.5)).floor.to_i64 next_cost = (10_000_000i64 / ((@member + 1) ** 0.5)).floor.to_i64 if (cur_cost - next_cost) * (es.size - build_cnt) < 5000000 ret << Work.new @money += 50000 else ret << Gather.new @member += 1 end end @money += use_cnt * 60 end return ret, @money end def create_highway(edge_cnt) all_edges = [] of Edge L.times do |y| L.times do |x| if y < L - 1 all_edges << Edge.new(y, x, DIR_DOWN) end if x < L - 1 all_edges << Edge.new(y, x, DIR_RIGHT) end end end all_edges.size.times do |i| sp = RND.rand(all_edges.size - i) + i all_edges.swap(i, sp) end best_edges = [] of Edge best_hc = 0 500.times do sp0 = RND.rand(edge_cnt) sp1 = RND.rand(all_edges.size - edge_cnt) + edge_cnt all_edges.swap(sp0, sp1) edge_cnt.times do |i| e = all_edges[i] @graph[e.y * L + e.x][e.dir] = DIST_HIGHWAY @graph[e.y * L + e.x + DP[e.dir]][e.dir ^ 2] = DIST_HIGHWAY end calc_dist(@graph, @dist) hc = 0 @ps.each do |p| hc += @dist[p[0]][p[1]] % 40 end # debug("hc=#{hc}") edge_cnt.times do |i| e = all_edges[i] @graph[e.y * L + e.x][e.dir] = DIST_NORMAL @graph[e.y * L + e.x + DP[e.dir]][e.dir ^ 2] = DIST_NORMAL end if hc > best_hc best_hc = hc best_edges = all_edges[0, edge_cnt] else all_edges.swap(sp0, sp1) end end debug("best_hc=#{best_hc}") # road = Array.new(L * 2 - 1) do |i| # i % 2 == 0 ? Array.new(L * 2 - 1) { |i| i % 2 == 0 ? '*' : ' ' } : Array.new(L * 2 - 1, ' ') # end # best_edges.each do |e| # if e.dir == DIR_DOWN # road[e.y * 2 + 1][e.x * 2] = '|' # else # road[e.y * 2][e.x * 2 + 1] = '-' # end # end # road.each do |row| # debug(row.join) # end return best_edges end def count_used_edge(graph, edges) ret = Array.new(edges.size, 0) ei = Array.new(L * L) { Array.new(4, -1) } edges.each_with_index do |e, i| ei[e.y * L + e.x][e.dir] = i ei[e.y * L + e.x + DP[e.dir]][e.dir ^ 2] = i end dist = Array.new(L * L, 0) prev = Array.new(L * L, 0) q = [] of Tuple(Int32, Int32) (L * L).times do |sp| next if @sps[sp].empty? dist.fill(INF) q.clear q << {sp, 0} dist[sp] = 0 qi = 0 while qi < q.size cp, cd = q[qi] qi += 1 next if dist[cp] < cd 4.times do |dir| next if graph[cp][dir] == INF np = cp + DP[dir] nd = cd + graph[cp][dir] if nd < dist[np] dist[np] = nd prev[np] = dir q << {np, nd} end end end @sps[sp].each do |gp| while gp != sp if ei[gp][prev[gp] ^ 2] != -1 ret[ei[gp][prev[gp] ^ 2]] += 1 end gp -= DP[prev[gp]] end end end return ret end end solver = Solver.new res, score = solver.solve debug("score=#{score}") {% if flag?(:local) %} puts res.join("\n") {% else %} T.times do |i| read_line puts res[i] STDOUT.flush end {% end %}