RECRUIT 日本橋ハーフマラソン 2022夏 (AHC013) に参加したので記録しておく。

結果

1種類の数字を揃える方針で取り組み、システムテストで9,213,499点、129位だった。
1種類の満点100×99÷2×2,000=9,900,000点に対して93%くらいなので1種類勢の中では健闘したほうだと思う。

基本方針

(以下、問題文のコンピュータは数字として扱う)
同じ数字の2乗がスコアになることから、なるべく1種類の数字を多く揃えたほうがよさそうだった。手数が少ないので、2種類以上のことはいったん置いておいて、まずは1種類の数字だけ揃えることにした。
(最終的に良いアイディアが浮かばなかったので1種類の数字だけの対策で終わった)

検討したこと

最初は2種類の数字を揃えることを検討してみた。
なるべくお互いの数字が干渉しない単純な図形を落書きして検討した。
↓ このように上下(または左右)の端と、縦には交互に配置すれば、左右に少し動かせば上端または下端とつなげることができると考えた。(いなにわさんはこれを実装したようですごい)

1-----1-----1
|     |     |
|  2  |  2  |
1  |  1  |  1
   |     |
2--2-----2--2

実装を少し進めてみると、1種類の100個を揃えるだけでもかなり手数が必要そうだったので、まずは1種類の数字pを揃えることに注力して、手数が余れば2種類目に費やすことにした。

バージョン1

少し無駄でもいいので、できる限り単純な模様になるように考えてみた。
全体の模様を眺めていたところ、数字pをマス目状、すなわち、直線的かつ直線の交点に配置すれば、全てを連結することができて、また、その他の数字pは、一番近い直線上に移動すればよさそう、という気がしてきた。
(下の図で、Aの位置にいたらBの位置に移動する)

p--------p--------p--------p--------p
|        |        |        |        |
|        |        |        |        |
|     A->B        |        |        |
|        |        |        |        |
|        |        |        |        |
p--------p--------p--------p--------p
|        |        |        |        |
|        |        |        |        |
|        |        |        |        |
|        |        |        |        |
|        |        |        |        |
p--------p--------p--------p--------p

横と縦の線をどこに引くかは、重みつきでスコアを計算してソートして決めるようにしてみた。重みは、同じラインに数字pがあれば+2、違う数字があれば-1のような感じ。また、その他の数字が退避しやすいように、隣り合うラインは選ばないようにした。

処理の流れは以下の通り。

揃える数字pを決める
横と縦で、線の位置を決める
線の上にある数字pでないものを、空いている場所にどかす
横と縦が交差する場所に数字pを移動する
線の上にない数字pを、線の上、または、線の上の数字pとつなぐことができる位置に移動する
数字p同士を接続する
手数が余っていたら他の数字を接続
出力

これをうまくいくように調整していったら二日目に20万点を超えた。おおむね100個中90個くらいつないだことになる。
方針としては素朴だが、validationや場当たり的な書き方をしたせいで1000行くらい書くことになった。

結果

seed 130 5,157点
横の線を1本、縦の線を5本ひいている。

バージョン2

残り時間も考えて、バージョン1を土台にして別のバリエーションも試すことにした。
盤面を4区画に分割して、それぞれの区画ごとに横または縦の線をひくようにしてみた。

                  |     |     p    |
-p----p-----p-----p     p     |    |
                  |     |     |    p
--p------p----p---p     |     p    |
                  |     p     |    p
                  |     |     |    |
---p----p----p----p-----p-----p----p-
   |    |    |    |
   |    p    |    |
   p    |    p    p-----p------p-----
   |    |    |    |
   p    p    |    |
   |    |    p    p----p-----p----p--

最初に中央に水平と垂直の線を配置しておく。各区画の処理では、それぞれの線を決めたら、中央の線上に置くようにすることで全体を連結にする。また、各区画では、水平線と垂直線の両方を試して、手数が少ない方を採用する。
処理の流れはバージョン1とだいたい同じで、線の上にない数字pを、線の上、または、線の上の数字pとつなぐことができる位置に移動していく。
バージョン1と2を両方試し、スコアが良い方を採用するようにしたら22万点を超えた。

結果

seed 130 5,120点

工夫・実装内容など

線の上にある数字をどかす

邪魔な数字を移動する処理は、1マスずつ移動可能な空きマスをBFSで探すようにした。
ただし、周りを数字で囲まれていて動かせない場合があることに気づいたので、空きマスをそのマスに移動してくることで、囲まれていても解決できるようにした。

パラメータ毎に試す

まず0000から9999までの10000ケースを生成してから、NとKの値によってディレクトリにふりわけた。Kが4通り、各KでNが25通りで、おおむね100個のケースのディレクトリが100個できた。
特定のKとNで10個くらいバッチ実行して最小・最大・平均値を出せるようにして、いくつかのKとNで試して、スコアが低いKとNを見つけるようにした。

↓ ふりわけに使ったスクリプト

rename_by_size.rb

#!/usr/bin/env ruby

require 'fileutils'
require 'json'
require 'open3'

rootdir = Dir.pwd
tools_directory = "#{rootdir}/tools"
input_case_directory = "in"
output_directory_prefix = "in_"

Dir.chdir(tools_directory)
Dir.glob("#{input_case_directory}/*.txt").sort.each do |filename|
  File.open(filename, 'r') do |f|
    N, K = f.gets.split(' ').map { |x| x.to_i }
    output_directory = "#{output_directory_prefix}#{K}/#{N}"
    output_filename = "#{output_directory}/#{filename.split('/').last}"
    FileUtils.mkdir_p(output_directory)
    FileUtils.cp(filename, output_filename)
  end
end

取り組み方について

焼きなまし法にすればいいんだろうなとは思ったが、数百万回の試行ができそうな軽いデータの持ち方を思いつかなかったので早々に諦めた。
が思いついた方法だけで実装しきれたのはよかったと思う。
途中ABCとAGCがはさまり、短期コンテストやってる場合じゃないのに! と思いながら参加した。コンテストのことで頭がいっぱいになるのは良いものである。
あまりメモを取らずに進めたので、次回は適宜記録を残していきたい。