結果

問題 No.5020 Averaging
コンテスト
ユーザー tomerun
提出日時 2024-02-25 16:34:17
言語 Crystal
(1.14.0)
結果
AC  
実行時間 983 ms / 1,000 ms
コード長 6,889 bytes
コンパイル時間 10,560 ms
コンパイル使用メモリ 296,336 KB
実行使用メモリ 6,676 KB
スコア 85,092,132
最終ジャッジ日時 2024-02-25 16:35:21
合計ジャッジ時間 62,915 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

START_TIME = Time.utc.to_unix_ms
TL         = (ENV["TL"]? || 980).to_i
PART       = (ENV["PART"]? || 1).to_i
IC         = (ENV["IC"]? || 1).to_f
FC         = (ENV["FC"]? || 10).to_f
N          =                         45
MED        = 500_000_000_000_000_000i64
RND        = Random.new(2)

alias PI = Tuple(Int32, Int32)

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

class Result
  property :pairs, :v0, :v1
  getter :score
  @score : Float64

  def initialize(@pairs : Array(PI), @v0 : Int64, @v1 : Int64)
    @score = Math.log10({(@v0 - MED).abs, (@v1 - MED).abs}.max + 1)
  end

  def to_s(io)
    io << "#{@pairs.size}\n" << @pairs.map { |p| {p[0] + 1, p[1] + 1}.join(" ") }.join("\n")
  end
end

RES_EMPTY = Result.new([] of PI, 0u64, 0u64)

class Solver
  def initialize(@a : Array(Int64), @b : Array(Int64))
  end

  def solve(timelimit)
    av = @a.dup
    bv = @b.dup
    level = N.times.to_a.map { |i| i + 1 }
    level[-1] -= 1
    N.times do |i|
      level.swap(i, RND.rand(N - i) + i)
    end
    med = MED
    sum_a = N.times.sum { |i| av[i] >> level[i] }
    sum_b = N.times.sum { |i| bv[i] >> level[i] }
    add0 = -1
    add1 = -1
    best_add0 = -1
    best_add1 = -1
    # cost = {(sum_a - med).abs, (sum_b - med).abs}.max
    cost = (sum_a - med).to_f ** 2 + (sum_b - med).to_f ** 2
    best_cost = cost
    best_level = level.dup
    debug("initial_cost:#{cost} #{sum_a} #{sum_b} #{med}")
    turn = 0
    cooler = IC
    init_time = Time.utc.to_unix_ms
    while true
      turn += 1
      if (turn & 0xFFF) == 0
        cur_time = Time.utc.to_unix_ms
        if cur_time > timelimit
          debug("turn:#{turn}\n")
          break
        end
        ratio = (cur_time - init_time) / (timelimit - init_time)
        cooler = (1.0 - ratio) * IC + ratio * FC
      end
      if (RND.rand(Int32) & 0xFF) == 0
        if add0 == -1
          n0 = RND.rand(N)
          n1 = RND.rand(N - 1)
          n1 += 1 if n0 <= n1
          new_a = (@a[n0] + @a[n1]) // 2
          new_b = (@b[n0] + @b[n1]) // 2
          na = sum_a + (new_a >> level[n0]) - (av[n0] >> level[n0]) + (new_a >> level[n1]) - (av[n1] >> level[n1])
          nb = sum_b + (new_b >> level[n0]) - (bv[n0] >> level[n0]) + (new_b >> level[n1]) - (bv[n1] >> level[n1])
          nc = (na - med).to_f ** 2 + (nb - med).to_f ** 2
          if (accept(nc, cost, cooler) || (turn & 0x3FFF) == 0)
            cost = nc
            add0 = n0
            add1 = n1
            av[add0] = new_a
            bv[add0] = new_b
            av[add1] = new_a
            bv[add1] = new_b
            sum_a = na
            sum_b = nb
            if nc < best_cost
              debug("0 best_cost:#{nc} turn:#{turn} diff_a:#{sum_a - med} diff_b:#{sum_b - med}")
              best_cost = nc
              best_add0 = add0
              best_add1 = add1
              best_level = level.dup
            end
          end
        else
          na = sum_a + (@a[add0] >> level[add0]) - (av[add0] >> level[add0]) + (@a[add1] >> level[add1]) - (av[add1] >> level[add1])
          nb = sum_b + (@b[add0] >> level[add0]) - (bv[add0] >> level[add0]) + (@b[add1] >> level[add1]) - (bv[add1] >> level[add1])
          nc = (na - med).to_f ** 2 + (nb - med).to_f ** 2
          if (accept(nc, cost, cooler) || (turn & 0x3FFF) == 0)
            cost = nc
            av[add0] = @a[add0]
            bv[add0] = @b[add0]
            av[add1] = @a[add1]
            bv[add1] = @b[add1]
            sum_a = na
            sum_b = nb
            add0 = -1
            add1 = -1
            if nc < best_cost
              debug("1 best_cost:#{nc} turn:#{turn} diff_a:#{sum_a - med} diff_b:#{sum_b - med}")
              best_cost = nc
              best_add0 = add0
              best_add1 = add1
              best_level = level.dup
            end
          end
        end
      else
        v0 = RND.rand(N)
        v1 = RND.rand(N - 1)
        v1 += 1 if v1 >= v0
        while level[v0] == level[v1]
          v0 = RND.rand(N)
          v1 = RND.rand(N - 1)
          v1 += 1 if v1 >= v0
        end
        na = sum_a + (av[v0] >> level[v1]) - (av[v0] >> level[v0]) + (av[v1] >> level[v0]) - (av[v1] >> level[v1])
        nb = sum_b + (bv[v0] >> level[v1]) - (bv[v0] >> level[v0]) + (bv[v1] >> level[v0]) - (bv[v1] >> level[v1])
        # nc = {(na - med).abs, (nb - med).abs}.max
        nc = (na - med).to_f ** 2 + (nb - med).to_f ** 2
        if (accept(nc, cost, cooler) || (turn & 0x3FFF) == 0)
          cost = nc
          level.swap(v0, v1)
          sum_a = na
          sum_b = nb
          if nc < best_cost
            debug("best_cost:#{nc} turn:#{turn} diff_a:#{sum_a - med} diff_b:#{sum_b - med}")
            best_cost = nc
            best_add0 = add0
            best_add1 = add1
            best_level = level.dup
          end
        end
      end
    end
    debug("add0:#{best_add0} add1:#{best_add1}")
    la = @a.dup
    lb = @b.dup
    ans = [] of PI
    if best_add0 != -1
      ans << {best_add0, best_add1}
      sa = (la[best_add0] + la[best_add1]) // 2
      sb = (lb[best_add0] + lb[best_add1]) // 2
      la[best_add0] = la[best_add1] = sa
      lb[best_add0] = lb[best_add1] = sb
    end
    ords = Array.new(N + 1) { [] of Int32 }
    N.times { |i| ords[N - 1 - best_level[i]] << i }
    ords.size.times do |i|
      ord = ords[i]
      while ord.size > 1
        i0 = ord.pop
        i1 = ord.pop
        ans << {i0, i1}
        ords[i + 1] << {i0, i1}.min
        sa = (la[i0] + la[i1]) // 2
        sb = (lb[i0] + lb[i1]) // 2
        la[i0] = la[i1] = sa
        lb[i0] = lb[i1] = sb
      end
    end
    return Result.new(ans, la[0], lb[0])
  end

  def accept(new_cost, old_cost, cooler)
    return true if new_cost <= old_cost
    # return false
    # diff = new_cost - old_cost
    diff = Math.log10(new_cost) - Math.log10(old_cost)
    v = -diff * cooler
    return false if v < -8
    return RND.rand < Math.exp(v)
  end
end

def main
  gets
  a = [] of Int64
  b = [] of Int64
  N.times do |i|
    u, v = read_line.split.map(&.to_i64)
    a << u
    b << v
  end
  solver = Solver.new(a, b)
  best_res = Result.new([] of PI, a[0], b[0])
  part = PART
  part.times do |i|
    res = solver.solve(START_TIME + TL * (i + 1) // part)
    if res.score < best_res.score
      best_res = res
    end
  end
  puts best_res
  {% if flag?(:local) %}
    STDERR.printf("raw:%7f score:%d\n", best_res.score, (2000000 - 100000 * best_res.score).floor)
  {% end %}
end

main
0