結果
問題 | No.5013 セクスタプル (open) |
ユーザー |
![]() |
提出日時 | 2022-12-29 15:25:07 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 1,904 ms / 2,000 ms |
コード長 | 7,036 bytes |
コンパイル時間 | 18,305 ms |
実行使用メモリ | 5,584 KB |
スコア | 10,743 |
最終ジャッジ日時 | 2022-12-29 15:28:44 |
合計ジャッジ時間 | 215,128 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
START_TIME = Time.utc.to_unix_msTL = 1900IC = (ENV["IC"]? || 50).to_i * 0.01FC = (ENV["FC"]? || 300).to_i * 0.01INITIAL_CNT_COEF = (ENV["INI_COEF"]? || 10).to_iPART = (ENV["PART"]? || 10).to_iROW_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 %}endmacro debugf(format_string, *args){% if flag?(:local) %}STDERR.printf({{format_string}}, {{*args}}){% end %}enddef crash(msg, caller_line = __LINE__)puts "[ERROR] line #{caller_line}: #{msg}"exitendmacro assert(cond, msg = "", caller_line = __LINE__){% if flag?(:local) %}if !({{cond}})crash({{msg}}, {{caller_line}})end{% end %}endclass Resultproperty :pos, :scoredef initialize(@pos : Array(Int32), @score : Int32)enddef to_s(io)pos.each do |p|io << p // 6 + 1 << " " << p % 6 + 1 << "\n"endioendendRES_EMPTY = Result.new([] of Int32, 0)class Solver@dice_bits : Array(Int32)@cnt_coef : Int32def initialize(@dices : Array(Array(Int32)))@dice_bits = @dices.map do |da|bits = 06.times do |i|bits |= (1 << i) if da[i] > 0endbitsend@cnt_coef = INITIAL_CNT_COEFenddef 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] > 0row_sum[i][k] += @dices[place[i * 6 + j]][k]col_cnt[j][k] += 1 if @dices[place[i * 6 + j]][k] > 0col_sum[j][k] += @dices[place[i * 6 + j]][k]endendendrow_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.sumbest_res = RES_EMPTYinitial_cooler = ICfinal_cooler = FCcooler = initial_coolerturn = 0begin_time = Time.utc.to_unix_mstotal_time = timelimit - begin_timewhile trueif (turn & 0xFF) == 0cur_time = Time.utc.to_unix_msif cur_time > timelimitdebug("turn: #{turn}")breakendratio = (cur_time - begin_time) / total_timecooler = initial_cooler + (final_cooler - initial_cooler) * rationew_cnt_coef = (INITIAL_CNT_COEF * (1.0 - ratio)).round.to_iif new_cnt_coef != @cnt_coef@cnt_coef = new_cnt_coef6.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])endcur_val = row_val.sum + col_val.sumendendp0 = RND.rand(36)p1 = RND.rand(35)p1 += 1 if p0 <= p1r0, c0 = p0.divmod(6)r1, c1 = p1.divmod(6)d0 = place[p0]d1 = place[p1]6.times do |i|if @dices[d0][i] > 0row_cnt[r0][i] -= 1col_cnt[c0][i] -= 1row_cnt[r1][i] += 1col_cnt[c1][i] += 1row_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]endif @dices[d1][i] > 0row_cnt[r1][i] -= 1col_cnt[c1][i] -= 1row_cnt[r0][i] += 1col_cnt[c0][i] += 1row_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]endenddiff = eval_line(row_cnt[r0], row_sum[r0]) + eval_line(col_cnt[c0], col_sum[c0]) - row_val[r0] - col_val[c0]if r0 != r1diff += eval_line(row_cnt[r1], row_sum[r1]) - row_val[r1]endif c0 != c1diff += eval_line(col_cnt[c1], col_sum[c1]) - col_val[c1]endif accept(diff, cooler)cur_val += diffplace.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_valdebug("best_score:#{cur_val} turn:#{turn}")best_res.score = cur_valbest_res.pos = place.dupassert(cur_val == calc_score(place))endelse6.times do |i|if @dices[d0][i] > 0row_cnt[r0][i] += 1col_cnt[c0][i] += 1row_cnt[r1][i] -= 1col_cnt[c1][i] -= 1row_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]endif @dices[d1][i] > 0row_cnt[r1][i] += 1col_cnt[c1][i] += 1row_cnt[r0][i] -= 1col_cnt[c0][i] -= 1row_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]endendendturn += 1endreal_pos = Array.new(36, 0)36.times do |i|real_pos[best_res.pos[i]] = iendbest_res.pos = real_posreturn best_resenddef calc_score(place)score = 06.times do |i|6.times do |j|sum = 0cnt = 06.times do |k|ds = @dices[place[j * 6 + k]]if ds[i] > 0sum += ds[i]cnt += 1endendif cnt == 6score += 3 + (sum - 6)endsum = 0cnt = 06.times do |k|ds = @dices[place[k * 6 + j]]if ds[i] > 0sum += ds[i]cnt += 1endendif cnt == 6score += 3 + (sum - 6)endendendreturn scoreenddef eval_line(cnt, sum)6.times.sum do |i|cnt[i] * @cnt_coef + (cnt[i] == 6 ? sum[i] - 3 : 0)endenddef accept(diff, cooler)return true if diff >= 0v = diff * coolerreturn false if v < -8# return falsereturn RND.rand < Math.exp(v)endenddef maindices = Array.new(36) dovs = read_line.split.map(&.to_i)Array.new(6) { |i| vs.count(i + 1) }endsolver = Solver.new(dices)part = PARTbest_res = RES_EMPTYpart.times do |i|res = solver.solve(START_TIME + TL * (i + 1) // part)if res.score > best_res.scorebest_res = resendendputs best_resdebug("final_score=#{best_res.score}")endmain