結果

問題 No.5013 セクスタプル (open)
ユーザー tomeruntomerun
提出日時 2022-12-29 18:36:30
言語 Crystal
(1.11.2)
結果
AC  
実行時間 1,984 ms / 2,000 ms
コード長 7,243 bytes
コンパイル時間 17,227 ms
実行使用メモリ 5,164 KB
スコア 18,565
最終ジャッジ日時 2022-12-29 18:40:16
合計ジャッジ時間 221,956 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,982 ms
4,900 KB
testcase_01 AC 1,983 ms
4,900 KB
testcase_02 AC 1,984 ms
5,008 KB
testcase_03 AC 1,984 ms
5,088 KB
testcase_04 AC 1,983 ms
5,008 KB
testcase_05 AC 1,982 ms
5,028 KB
testcase_06 AC 1,984 ms
5,060 KB
testcase_07 AC 1,983 ms
4,964 KB
testcase_08 AC 1,984 ms
5,052 KB
testcase_09 AC 1,983 ms
5,016 KB
testcase_10 AC 1,983 ms
5,052 KB
testcase_11 AC 1,984 ms
4,900 KB
testcase_12 AC 1,984 ms
4,900 KB
testcase_13 AC 1,982 ms
5,028 KB
testcase_14 AC 1,984 ms
4,904 KB
testcase_15 AC 1,984 ms
4,944 KB
testcase_16 AC 1,983 ms
4,896 KB
testcase_17 AC 1,982 ms
4,876 KB
testcase_18 AC 1,983 ms
5,036 KB
testcase_19 AC 1,983 ms
5,008 KB
testcase_20 AC 1,983 ms
5,064 KB
testcase_21 AC 1,983 ms
4,984 KB
testcase_22 AC 1,984 ms
5,012 KB
testcase_23 AC 1,983 ms
5,044 KB
testcase_24 AC 1,984 ms
5,084 KB
testcase_25 AC 1,982 ms
4,908 KB
testcase_26 AC 1,983 ms
5,084 KB
testcase_27 AC 1,983 ms
5,056 KB
testcase_28 AC 1,984 ms
5,004 KB
testcase_29 AC 1,983 ms
4,952 KB
testcase_30 AC 1,984 ms
4,840 KB
testcase_31 AC 1,984 ms
5,044 KB
testcase_32 AC 1,983 ms
5,060 KB
testcase_33 AC 1,982 ms
4,968 KB
testcase_34 AC 1,984 ms
5,056 KB
testcase_35 AC 1,982 ms
5,016 KB
testcase_36 AC 1,983 ms
4,948 KB
testcase_37 AC 1,983 ms
5,092 KB
testcase_38 AC 1,983 ms
5,092 KB
testcase_39 AC 1,984 ms
5,020 KB
testcase_40 AC 1,984 ms
5,032 KB
testcase_41 AC 1,984 ms
5,156 KB
testcase_42 AC 1,982 ms
4,880 KB
testcase_43 AC 1,983 ms
5,040 KB
testcase_44 AC 1,984 ms
5,052 KB
testcase_45 AC 1,983 ms
4,960 KB
testcase_46 AC 1,982 ms
5,020 KB
testcase_47 AC 1,984 ms
5,072 KB
testcase_48 AC 1,984 ms
5,048 KB
testcase_49 AC 1,982 ms
5,124 KB
testcase_50 AC 1,983 ms
5,012 KB
testcase_51 AC 1,983 ms
5,036 KB
testcase_52 AC 1,984 ms
5,080 KB
testcase_53 AC 1,983 ms
4,904 KB
testcase_54 AC 1,983 ms
4,956 KB
testcase_55 AC 1,984 ms
4,968 KB
testcase_56 AC 1,983 ms
5,040 KB
testcase_57 AC 1,983 ms
4,928 KB
testcase_58 AC 1,983 ms
4,980 KB
testcase_59 AC 1,983 ms
4,880 KB
testcase_60 AC 1,983 ms
5,056 KB
testcase_61 AC 1,984 ms
4,904 KB
testcase_62 AC 1,983 ms
4,956 KB
testcase_63 AC 1,983 ms
5,072 KB
testcase_64 AC 1,983 ms
5,012 KB
testcase_65 AC 1,983 ms
5,084 KB
testcase_66 AC 1,983 ms
5,060 KB
testcase_67 AC 1,983 ms
5,008 KB
testcase_68 AC 1,983 ms
4,876 KB
testcase_69 AC 1,983 ms
5,096 KB
testcase_70 AC 1,982 ms
4,952 KB
testcase_71 AC 1,984 ms
5,120 KB
testcase_72 AC 1,984 ms
4,876 KB
testcase_73 AC 1,983 ms
5,016 KB
testcase_74 AC 1,983 ms
4,904 KB
testcase_75 AC 1,983 ms
5,092 KB
testcase_76 AC 1,984 ms
5,148 KB
testcase_77 AC 1,983 ms
5,052 KB
testcase_78 AC 1,984 ms
5,164 KB
testcase_79 AC 1,982 ms
5,064 KB
testcase_80 AC 1,983 ms
5,160 KB
testcase_81 AC 1,983 ms
5,092 KB
testcase_82 AC 1,983 ms
4,904 KB
testcase_83 AC 1,983 ms
4,924 KB
testcase_84 AC 1,983 ms
5,160 KB
testcase_85 AC 1,983 ms
5,020 KB
testcase_86 AC 1,983 ms
5,156 KB
testcase_87 AC 1,983 ms
5,048 KB
testcase_88 AC 1,983 ms
4,904 KB
testcase_89 AC 1,983 ms
4,968 KB
testcase_90 AC 1,984 ms
5,160 KB
testcase_91 AC 1,983 ms
4,964 KB
testcase_92 AC 1,983 ms
5,156 KB
testcase_93 AC 1,984 ms
4,900 KB
testcase_94 AC 1,983 ms
5,088 KB
testcase_95 AC 1,983 ms
5,160 KB
testcase_96 AC 1,984 ms
5,016 KB
testcase_97 AC 1,984 ms
5,160 KB
testcase_98 AC 1,983 ms
5,064 KB
testcase_99 AC 1,982 ms
5,160 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

START_TIME       = Time.utc.to_unix_ms
TL               = 1980
IC               = (ENV["IC"]? || 50).to_i * 0.01
FC               = (ENV["FC"]? || 200).to_i * 0.01
INITIAL_CNT_COEF = (ENV["INI_COEF"]? || 3).to_i
PART             = (ENV["PART"]? || 20).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 : Int64)
  end

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

class Solver
  @cnt_coef : Int32

  def initialize(@dices : Array(Array(Int32)))
    @dices_sum = Array(Int64).new(36) do |i|
      v = 0i64
      6.times do |j|
        v |= @dices[i][j].to_i64 << (8 * j)
      end
      v
    end
    @dices_exist = Array(Int64).new(36) do |i|
      v = 0i64
      6.times do |j|
        v |= (@dices[i][j] != 0 ? 1i64 : 0i64) << (8 * j)
      end
      v
    end
    @cnt_coef = INITIAL_CNT_COEF
  end

  def solve(timelimit)
    row_cnt = Array.new(6, 0i64)
    col_cnt = Array.new(6, 0i64)
    row_sum = Array.new(6, 0i64)
    col_sum = Array.new(6, 0i64)
    place = Array.new(36) { |i| i }
    6.times do |i|
      6.times do |j|
        row_cnt[i] += @dices_exist[place[i * 6 + j]]
        row_sum[i] += @dices_sum[place[i * 6 + j]]
        col_cnt[j] += @dices_exist[place[i * 6 + j]]
        col_sum[j] += @dices_sum[place[i * 6 + j]]
      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
    @cnt_coef = INITIAL_CNT_COEF
    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
    if total_time == 0
      return best_res
    end
    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(36)
      p1 = RND.rand(35)
      p1 += 1 if p0 <= p1
      r0, c0 = p0.divmod(6)
      r1, c1 = p1.divmod(6)
      d0 = place[p0]
      d1 = place[p1]
      diff = 0
      if r0 != r1
        row_cnt[r0] -= @dices_exist[d0]
        row_sum[r0] -= @dices_sum[d0]
        row_cnt[r1] += @dices_exist[d0]
        row_sum[r1] += @dices_sum[d0]
        row_cnt[r1] -= @dices_exist[d1]
        row_sum[r1] -= @dices_sum[d1]
        row_cnt[r0] += @dices_exist[d1]
        row_sum[r0] += @dices_sum[d1]
        diff += eval_line(row_cnt[r0], row_sum[r0]) + eval_line(row_cnt[r1], row_sum[r1]) - row_val[r0] - row_val[r1]
      end
      if c0 != c1
        col_cnt[c0] -= @dices_exist[d0]
        col_sum[c0] -= @dices_sum[d0]
        col_cnt[c1] += @dices_exist[d0]
        col_sum[c1] += @dices_sum[d0]
        col_cnt[c1] -= @dices_exist[d1]
        col_sum[c1] -= @dices_sum[d1]
        col_cnt[c0] += @dices_exist[d1]
        col_sum[c0] += @dices_sum[d1]
        diff += eval_line(col_cnt[c0], col_sum[c0]) + eval_line(col_cnt[c1], col_sum[c1]) - col_val[c0] - 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
        row_cnt[r0] += @dices_exist[d0]
        row_sum[r0] += @dices_sum[d0]
        row_cnt[r1] -= @dices_exist[d0]
        row_sum[r1] -= @dices_sum[d0]
        col_cnt[c0] += @dices_exist[d0]
        col_sum[c0] += @dices_sum[d0]
        col_cnt[c1] -= @dices_exist[d0]
        col_sum[c1] -= @dices_sum[d0]
        row_cnt[r1] += @dices_exist[d1]
        row_sum[r1] += @dices_sum[d1]
        row_cnt[r0] -= @dices_exist[d1]
        row_sum[r0] -= @dices_sum[d1]
        col_cnt[c1] += @dices_exist[d1]
        col_sum[c1] += @dices_sum[d1]
        col_cnt[c0] -= @dices_exist[d1]
        col_sum[c0] -= @dices_sum[d1]
      end
      turn += 1
    end
    if best_res.score > 0
      real_pos = Array.new(36, 0)
      36.times do |i|
        real_pos[best_res.pos[i]] = i
      end
      best_res.pos = real_pos
    end
    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)
    t = (cnt & (cnt >> 1)) & 0x020202020202i64
    t = (t >> 1) & ~cnt
    mask = t * 0xFFi64
    ret = t.popcount * @cnt_coef
    s = sum & mask
    s = ((s >> 8) + s) & 0x00FF00FF00FFi64
    s = ((s >> 16) + s) & 0x00FF000000FFi64
    s = ((s >> 32) + s) & 0x0000000000FFi64
    ret += s - t.popcount * 3
    return ret
  end

  def accept(diff, cooler)
    return true if diff >= 0
    v = diff * cooler
    return false if v < -8
    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
0