結果

問題 No.5013 セクスタプル (open)
ユーザー tomeruntomerun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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"]? || 10).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
RES_EMPTY = Result.new([] of Int32, 0)
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 = RES_EMPTY
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(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]
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.dup
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 = RES_EMPTY
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
debug("final_score=#{best_res.score}")
end
main
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0