#829062 (Crystal) No.5013 セクスタプル (open)

• 問題: No.5013 セクスタプル (open)
• ユーザー: tomerun
• 提出日時: 2022-12-29 16:17:32
• 言語: Crystal (1.11.2)
• 結果: AC
• 実行時間: 1,904 ms / 2,000 ms
• コード長: 7,039 bytes
• コンパイル時間: 18,653 ms
• 実行使用メモリ: 6,952 KB
• スコア: 18,452
• 最終ジャッジ日時: 2022-12-29 16:25:02
• 合計ジャッジ時間: 216,028 ms
• ジャッジサーバーID （参考情報）: judge13 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1,904 ms; 5,400 KB
testcase_01	AC	1,904 ms; 6,952 KB
testcase_02	AC	1,903 ms; 5,296 KB
testcase_03	AC	1,904 ms; 6,952 KB
testcase_04	AC	1,903 ms; 6,952 KB
testcase_05	AC	1,903 ms; 5,504 KB
testcase_06	AC	1,904 ms; 5,484 KB
testcase_07	AC	1,904 ms; 6,952 KB
testcase_08	AC	1,904 ms; 5,508 KB
testcase_09	AC	1,904 ms; 5,392 KB
testcase_10	AC	1,903 ms; 5,544 KB
testcase_11	AC	1,904 ms; 5,504 KB
testcase_12	AC	1,903 ms; 5,572 KB
testcase_13	AC	1,904 ms; 5,300 KB
testcase_14	AC	1,903 ms; 5,488 KB
testcase_15	AC	1,903 ms; 5,576 KB
testcase_16	AC	1,904 ms; 5,548 KB
testcase_17	AC	1,903 ms; 5,332 KB
testcase_18	AC	1,904 ms; 6,948 KB
testcase_19	AC	1,904 ms; 5,476 KB
testcase_20	AC	1,903 ms; 5,508 KB
testcase_21	AC	1,903 ms; 6,948 KB
testcase_22	AC	1,904 ms; 5,404 KB
testcase_23	AC	1,904 ms; 6,948 KB
testcase_24	AC	1,902 ms; 5,312 KB
testcase_25	AC	1,903 ms; 6,948 KB
testcase_26	AC	1,904 ms; 5,404 KB
testcase_27	AC	1,904 ms; 5,452 KB
testcase_28	AC	1,903 ms; 5,308 KB
testcase_29	AC	1,904 ms; 5,436 KB
testcase_30	AC	1,903 ms; 5,496 KB
testcase_31	AC	1,903 ms; 5,312 KB
testcase_32	AC	1,903 ms; 6,948 KB
testcase_33	AC	1,904 ms; 6,952 KB
testcase_34	AC	1,904 ms; 5,452 KB
testcase_35	AC	1,903 ms; 5,296 KB
testcase_36	AC	1,904 ms; 5,504 KB
testcase_37	AC	1,904 ms; 5,300 KB
testcase_38	AC	1,904 ms; 5,320 KB
testcase_39	AC	1,903 ms; 6,948 KB
testcase_40	AC	1,904 ms; 6,952 KB
testcase_41	AC	1,904 ms; 5,308 KB
testcase_42	AC	1,904 ms; 6,952 KB
testcase_43	AC	1,904 ms; 5,300 KB
testcase_44	AC	1,904 ms; 5,508 KB
testcase_45	AC	1,904 ms; 5,380 KB
testcase_46	AC	1,903 ms; 5,500 KB
testcase_47	AC	1,904 ms; 6,948 KB
testcase_48	AC	1,903 ms; 5,504 KB
testcase_49	AC	1,904 ms; 6,948 KB
testcase_50	AC	1,904 ms; 5,504 KB
testcase_51	AC	1,903 ms; 5,488 KB
testcase_52	AC	1,903 ms; 5,320 KB
testcase_53	AC	1,903 ms; 6,948 KB
testcase_54	AC	1,904 ms; 5,496 KB
testcase_55	AC	1,903 ms; 5,384 KB
testcase_56	AC	1,903 ms; 5,504 KB
testcase_57	AC	1,903 ms; 6,948 KB
testcase_58	AC	1,904 ms; 5,488 KB
testcase_59	AC	1,903 ms; 6,948 KB
testcase_60	AC	1,904 ms; 5,552 KB
testcase_61	AC	1,902 ms; 5,300 KB
testcase_62	AC	1,904 ms; 6,952 KB
testcase_63	AC	1,904 ms; 5,508 KB
testcase_64	AC	1,903 ms; 5,452 KB
testcase_65	AC	1,904 ms; 5,508 KB
testcase_66	AC	1,903 ms; 5,544 KB
testcase_67	AC	1,904 ms; 5,452 KB
testcase_68	AC	1,902 ms; 6,948 KB
testcase_69	AC	1,903 ms; 5,500 KB
testcase_70	AC	1,904 ms; 6,948 KB
testcase_71	AC	1,903 ms; 5,548 KB
testcase_72	AC	1,903 ms; 5,300 KB
testcase_73	AC	1,904 ms; 5,296 KB
testcase_74	AC	1,904 ms; 5,400 KB
testcase_75	AC	1,904 ms; 5,500 KB
testcase_76	AC	1,904 ms; 6,948 KB
testcase_77	AC	1,903 ms; 5,316 KB
testcase_78	AC	1,903 ms; 5,316 KB
testcase_79	AC	1,904 ms; 5,580 KB
testcase_80	AC	1,904 ms; 5,308 KB
testcase_81	AC	1,903 ms; 6,948 KB
testcase_82	AC	1,902 ms; 5,472 KB
testcase_83	AC	1,904 ms; 5,428 KB
testcase_84	AC	1,904 ms; 5,300 KB
testcase_85	AC	1,903 ms; 5,504 KB
testcase_86	AC	1,904 ms; 5,412 KB
testcase_87	AC	1,903 ms; 5,300 KB
testcase_88	AC	1,904 ms; 6,948 KB
testcase_89	AC	1,904 ms; 6,952 KB
testcase_90	AC	1,902 ms; 5,312 KB
testcase_91	AC	1,903 ms; 6,948 KB
testcase_92	AC	1,903 ms; 6,948 KB
testcase_93	AC	1,904 ms; 5,444 KB
testcase_94	AC	1,904 ms; 5,480 KB
testcase_95	AC	1,903 ms; 6,948 KB
testcase_96	AC	1,903 ms; 6,948 KB
testcase_97	AC	1,902 ms; 6,952 KB
testcase_98	AC	1,904 ms; 6,948 KB
testcase_99	AC	1,904 ms; 5,496 KB

ソースコード

START_TIME       = Time.utc.to_unix_ms
TL               = 1900
IC               = (ENV["IC"]? || 50).to_i * 0.01
FC               = (ENV["FC"]? || 300).to_i * 0.01
INITIAL_CNT_COEF = (ENV["INI_COEF"]? || 10).to_i
PART             = (ENV["PART"]? || 5).to_i
ROW_MASK         = Array.new(6) { |i| 0x3Fi64 << (6 * i) }
COL_MASK         = Array.new(6) { |i| 0x414141i64 << i }
RND              = Random.new(2)

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 :pos, :score

  def initialize(@pos : Array(Int32), @score : Int32)
  end

  def to_s(io)
    pos.each do |p|
      io << p // 6 + 1 << " " << p % 6 + 1 << "\n"
    end
    io
  end
end

class Solver
  @dice_bits : Array(Int32)
  @cnt_coef : Int32

  def initialize(@dices : Array(Array(Int32)))
    @dice_bits = @dices.map do |da|
      bits = 0
      6.times do |i|
        bits |= (1 << i) if da[i] > 0
      end
      bits
    end
    @cnt_coef = INITIAL_CNT_COEF
  end

  def solve(timelimit)
    row_cnt = Array.new(6) { Array.new(6, 0) }
    col_cnt = Array.new(6) { Array.new(6, 0) }
    row_sum = Array.new(6) { Array.new(6, 0) }
    col_sum = Array.new(6) { Array.new(6, 0) }
    place = Array.new(36) { |i| i }
    6.times do |i|
      6.times do |j|
        6.times do |k|
          row_cnt[i][k] += 1 if @dices[place[i * 6 + j]][k] > 0
          row_sum[i][k] += @dices[place[i * 6 + j]][k]
          col_cnt[j][k] += 1 if @dices[place[i * 6 + j]][k] > 0
          col_sum[j][k] += @dices[place[i * 6 + j]][k]
        end
      end
    end
    row_val = Array.new(6) { |i| eval_line(row_cnt[i], row_sum[i]) }
    col_val = Array.new(6) { |i| eval_line(col_cnt[i], col_sum[i]) }
    cur_val = row_val.sum + col_val.sum
    best_res = Result.new([] of Int32, 0)
    initial_cooler = IC
    final_cooler = FC
    cooler = initial_cooler
    turn = 0
    begin_time = Time.utc.to_unix_ms
    total_time = timelimit - begin_time
    while true
      if (turn & 0xFF) == 0
        cur_time = Time.utc.to_unix_ms
        if cur_time > timelimit
          debug("turn: #{turn}")
          break
        end
        ratio = (cur_time - begin_time) / total_time
        cooler = initial_cooler + (final_cooler - initial_cooler) * ratio
        new_cnt_coef = (INITIAL_CNT_COEF * (1.0 - ratio)).round.to_i
        if new_cnt_coef != @cnt_coef
          @cnt_coef = new_cnt_coef
          6.times do |i|
            row_val[i] = eval_line(row_cnt[i], row_sum[i])
            col_val[i] = eval_line(col_cnt[i], col_sum[i])
          end
          cur_val = row_val.sum + col_val.sum
        end
      end
      p0 = RND.rand(35)
      p1 = RND.rand(34)
      p1 += 1 if p0 <= p1
      r0, c0 = p0.divmod(6)
      r1, c1 = p1.divmod(6)
      d0 = place[p0]
      d1 = place[p1]
      6.times do |i|
        if @dices[d0][i] > 0
          row_cnt[r0][i] -= 1
          col_cnt[c0][i] -= 1
          row_cnt[r1][i] += 1
          col_cnt[c1][i] += 1
          row_sum[r0][i] -= @dices[d0][i]
          col_sum[c0][i] -= @dices[d0][i]
          row_sum[r1][i] += @dices[d0][i]
          col_sum[c1][i] += @dices[d0][i]
        end
        if @dices[d1][i] > 0
          row_cnt[r1][i] -= 1
          col_cnt[c1][i] -= 1
          row_cnt[r0][i] += 1
          col_cnt[c0][i] += 1
          row_sum[r1][i] -= @dices[d1][i]
          col_sum[c1][i] -= @dices[d1][i]
          row_sum[r0][i] += @dices[d1][i]
          col_sum[c0][i] += @dices[d1][i]
        end
      end
      diff = eval_line(row_cnt[r0], row_sum[r0]) + eval_line(col_cnt[c0], col_sum[c0]) - row_val[r0] - col_val[c0]
      if r0 != r1
        diff += eval_line(row_cnt[r1], row_sum[r1]) - row_val[r1]
      end
      if c0 != c1
        diff += eval_line(col_cnt[c1], col_sum[c1]) - col_val[c1]
      end
      if accept(diff, cooler)
        cur_val += diff
        place.swap(p0, p1)
        row_val[r0] = eval_line(row_cnt[r0], row_sum[r0])
        row_val[r1] = eval_line(row_cnt[r1], row_sum[r1])
        col_val[c0] = eval_line(col_cnt[c0], col_sum[c0])
        col_val[c1] = eval_line(col_cnt[c1], col_sum[c1])
        # debug("score:#{cur_val} turn:#{turn}")
        if @cnt_coef == 0 && best_res.score < cur_val
          debug("best_score:#{cur_val} turn:#{turn}")
          best_res.score = cur_val
          best_res.pos = place.clone
          assert(cur_val == calc_score(place))
        end
      else
        6.times do |i|
          if @dices[d0][i] > 0
            row_cnt[r0][i] += 1
            col_cnt[c0][i] += 1
            row_cnt[r1][i] -= 1
            col_cnt[c1][i] -= 1
            row_sum[r0][i] += @dices[d0][i]
            col_sum[c0][i] += @dices[d0][i]
            row_sum[r1][i] -= @dices[d0][i]
            col_sum[c1][i] -= @dices[d0][i]
          end
          if @dices[d1][i] > 0
            row_cnt[r1][i] += 1
            col_cnt[c1][i] += 1
            row_cnt[r0][i] -= 1
            col_cnt[c0][i] -= 1
            row_sum[r1][i] += @dices[d1][i]
            col_sum[c1][i] += @dices[d1][i]
            row_sum[r0][i] -= @dices[d1][i]
            col_sum[c0][i] -= @dices[d1][i]
          end
        end
      end
      turn += 1
    end
    real_pos = Array.new(36, 0)
    36.times do |i|
      real_pos[best_res.pos[i]] = i
    end
    best_res.pos = real_pos
    return best_res
  end

  def calc_score(place)
    score = 0
    6.times do |i|
      6.times do |j|
        sum = 0
        cnt = 0
        6.times do |k|
          ds = @dices[place[j * 6 + k]]
          if ds[i] > 0
            sum += ds[i]
            cnt += 1
          end
        end
        if cnt == 6
          score += 3 + (sum - 6)
        end
        sum = 0
        cnt = 0
        6.times do |k|
          ds = @dices[place[k * 6 + j]]
          if ds[i] > 0
            sum += ds[i]
            cnt += 1
          end
        end
        if cnt == 6
          score += 3 + (sum - 6)
        end
      end
    end
    return score
  end

  def eval_line(cnt, sum)
    6.times.sum do |i|
      cnt[i] * @cnt_coef + (cnt[i] == 6 ? sum[i] - 3 : 0)
    end
  end

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

def main
  dices = Array.new(36) do
    vs = read_line.split.map(&.to_i)
    Array.new(6) { |i| vs.count(i + 1) }
  end
  solver = Solver.new(dices)
  part = PART
  best_res = Result.new([] of Int32, 0)
  part.times do |i|
    res = solver.solve(START_TIME + TL * (i + 1) // part)
    if res.score > best_res.score
      best_res = res
    end
  end
  print best_res.to_s
  debug("final_score=#{best_res.score}")
end

main