#864723 (Crystal) No.5016 Worst Mayor

提出ソース

結果

問題	No.5016 Worst Mayor
ユーザー	tomerun
提出日時	2023-04-29 17:00:01
言語	Crystal (1.11.2)
結果	AC
実行時間	1,987 ms / 2,000 ms
コード長	9,727 bytes
コンパイル時間	22,866 ms
コンパイル使用メモリ	265,608 KB
実行使用メモリ	24,492 KB
スコア	11,648,706,057
平均クエリ数	320.00
最終ジャッジ日時	2023-04-29 17:06:37
合計ジャッジ時間	109,455 ms
ジャッジサーバーID （参考情報）	judge15 / judge16
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,971 ms 23,520 KB
testcase_01	AC	1,968 ms 23,400 KB
testcase_02	AC	1,964 ms 23,868 KB
testcase_03	AC	1,965 ms 23,424 KB
testcase_04	AC	1,968 ms 23,868 KB
testcase_05	AC	1,966 ms 24,384 KB
testcase_06	AC	1,966 ms 24,036 KB
testcase_07	AC	1,966 ms 24,084 KB
testcase_08	AC	1,963 ms 24,072 KB
testcase_09	AC	1,963 ms 24,072 KB
testcase_10	AC	1,967 ms 24,024 KB
testcase_11	AC	1,965 ms 23,664 KB
testcase_12	AC	1,966 ms 23,868 KB
testcase_13	AC	1,968 ms 23,832 KB
testcase_14	AC	1,966 ms 23,424 KB
testcase_15	AC	1,964 ms 23,880 KB
testcase_16	AC	1,967 ms 24,252 KB
testcase_17	AC	1,967 ms 24,372 KB
testcase_18	AC	1,966 ms 23,424 KB
testcase_19	AC	1,967 ms 23,520 KB
testcase_20	AC	1,965 ms 23,400 KB
testcase_21	AC	1,968 ms 23,628 KB
testcase_22	AC	1,964 ms 23,868 KB
testcase_23	AC	1,965 ms 23,580 KB
testcase_24	AC	1,965 ms 23,412 KB
testcase_25	AC	1,964 ms 23,364 KB
testcase_26	AC	1,965 ms 23,424 KB
testcase_27	AC	1,968 ms 24,360 KB
testcase_28	AC	1,966 ms 24,360 KB
testcase_29	AC	1,968 ms 23,436 KB
testcase_30	AC	1,964 ms 24,048 KB
testcase_31	AC	1,966 ms 24,312 KB
testcase_32	AC	1,965 ms 23,412 KB
testcase_33	AC	1,964 ms 23,520 KB
testcase_34	AC	1,965 ms 23,472 KB
testcase_35	AC	1,964 ms 24,324 KB
testcase_36	AC	1,965 ms 23,652 KB
testcase_37	AC	1,964 ms 23,664 KB
testcase_38	AC	1,966 ms 23,868 KB
testcase_39	AC	1,968 ms 24,360 KB
testcase_40	AC	1,987 ms 23,388 KB
testcase_41	AC	1,965 ms 24,492 KB
testcase_42	AC	1,964 ms 24,396 KB
testcase_43	AC	1,967 ms 24,048 KB
testcase_44	AC	1,966 ms 24,396 KB
testcase_45	AC	1,964 ms 24,036 KB
testcase_46	AC	1,967 ms 24,348 KB
testcase_47	AC	1,966 ms 23,388 KB
testcase_48	AC	1,965 ms 23,640 KB
testcase_49	AC	1,966 ms 24,048 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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"]? || 120).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 if cd < dist[cp][i]
      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] }
      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

      work_th = 50000
      edge_cnt = es.size
      while true
        if Time.utc.to_unix_ms - START_TIME > TL
          break
        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
        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
        work_th *= 2
        if work_th >= MAX_WORK_TH
          work_th = 50000
          edge_cnt -= 1
          break if edge_cnt == MAX_EDGE_CNT - 10
        end
        # break
      end
      turn += 1
      # break
    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 Time.utc.to_unix_ms - START_TIME > TL
        return ret, 0i64
      end

      # 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
        assert(@graph.sum { |row| row.count(DIST_HIGHWAY) } == build_cnt * 2)
        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 - 1).times do |i|
      all_edges << Edge.new(L // 2, i, DIR_RIGHT)
      all_edges << Edge.new(i, 1, DIR_DOWN)
      all_edges << Edge.new(i, L - 2, DIR_DOWN)
    end
    fix_ec = all_edges.size
    L.times do |y|
      L.times do |x|
        if y < L - 1
          e = Edge.new(y, x, DIR_DOWN)
          if !all_edges.includes?(e)
            all_edges << e
          end
        end
        if x < L - 1
          e = Edge.new(y, x, DIR_RIGHT)
          if !all_edges.includes?(e)
            all_edges << e
          end
        end
      end
    end
    (all_edges.size - fix_ec).times do |i|
      sp = RND.rand(all_edges.size - fix_ec - i) + i + fix_ec
      all_edges.swap(i + fix_ec, sp)
    end
    best_edges = [] of Edge
    best_hc = 0
    500.times do |i|
      if i % 50 == 0 && Time.utc.to_unix_ms - START_TIME > TL
        break
      end
      sp0 = RND.rand(edge_cnt - fix_ec) + fix_ec
      sp1 = RND.rand(all_edges.size - fix_ec - edge_cnt) + edge_cnt + fix_ec
      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|
    u, v = read_line.split.map(&.to_i64)
    if u == -1
      exit
    end
    puts res[i]
    STDOUT.flush
  end
{% end %}

yukicoder

結果

テストケース

ソースコード