estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）参加しました

はじめに

estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）に参加しました。

個人的な体験談で、解説にはなっていません。

atcoder.jp

ルールの確認

まずはルールをざっくり見ていきます。

• 長方形を作れるような位置に印をつけていく。
• 長方形を作るときに、外周上に4頂点以外の印があってはならない。
  • すでにある辺上に印をつけることはできる。
• 複数の長方形で辺を共有できない。
  • 交差はできる。

    得点

• それぞれの印ごとに、位置によって決まる点数を得られる。
• 「中心からのユークリッド距離の2乗+1」がその位置の点数になる。
• 印は多いほど良い。中心から離れているほど良い。

ビジュアライザ

ビジュアライザのマニュアルモードで遊んでみました。

• ルールがわかった。
• むやみに大きな長方形を作ると、後々長方形を作りづらくなる。
• 中心から離れた点に印をつけるのは、（人力では）かなり難しそう。
• できるだけ密集して印をつけていくのがよさそう？

得点計算関数

どこから手を付けたらよいかわかりませんが、とりあえず、必ず必要になるであろう得点計算関数を作ることにしました。 得点計算をするには、各格子点に印がついているかどうかという情報が必要です。

以下の状態を持つ型を定義して盤面の状態とし、それを引数として得点を返す関数を作りました。

• N
• M
• 各格子点の印の状態

ビジュアライザで表示される得点と比較して、ちゃんと計算できていることを確認。

盤面の状態を表現する

得点計算のためには印の有無さえ分かればよいですが、長方形を作っていくことを考えると、当然、長方形の外周となる「線」の情報も保持する必要があります。 線の情報の持ち方としては、以下の2つを思いつきました。

1. 線が引かれうる場所を最小単位（隣り合う格子点の間）に区切って、各区間に線が引かれているか/いないかで表す。
2. ２つの頂点のペアで表す

新たに線を引くときの処理は(2)のほうが実装が簡単そうですが、ある場所に線を引けるかどうかの判定のために、すでに引かれている線の情報を取り出すときには、(1)のほうが都合がよさそうです。とりあえず、(1)を採用することにします。

状態を正しく持てているか確認するために、標準出力で表示できるようにしました。

斜めがあるので結構難しかったです。ここまでで、すでにやり切った感。。

でもまだ何も提出していないので０点です。

正の点数を取る

順位表を見てみると、正の点数を取った人のうちの最低点が14,048,321で、同点のひとがたくさんいます。おそらくこれが、印を一つも追加しないときの得点だと思います。まずは、この14,048,321を超えることを目標にします。

なんとなく、小さい長方形を敷き詰めたほうが良い気がするので、辺の長さが１の正方形を描けるだけ描いていく、というアルゴリズムにします。 盤面全体を端から順にみていき、正方形を描けるなら描く、という処理を時間いっぱい繰り返します。

しょぼい！

得点は15,176,634 (15.1M)でした。正の点数が取れたのでよしとします。 以降点数はM(100万)単位で表記します。(0.1M未満切り捨て)

ところで、seed=0のときは初期状態が「estie社のロゴ」という特殊なパターンなので、seed=1以降の結果を見て考察したほうが良いのかな、と思いました。 seed=1だとこんな感じ。これ以降seed=1の画像を貼っていきます。

つづいて、45度傾いた最小の正方形も描けるだけ描くようにしてみました。

急に増えた！
でもまだまだ。

点数は19.7Mでした。

大きい長方形も描く＆高速化

大きい長方形も描いていきたいのですが、現状のアルゴリズムのままだと計算量が膨大になりそうです。 現状は、

• 結ぶと長方形になるような格子点4つを決める。
• 4つのうちちょうど3つに印がついていることを確かめる。
• 長方形の外周上に他の印や線がないことを確かめる。 という手順を踏んでいます。

盤面の端のほうの、まっさらなあたりでもこんなことをやっているので、かなり無駄です。 そこで、すでにある印を頂点として含む長方形を探す方法に変更します。 印を順番に見ていき、その印を利用して作れる長方形のうち、最も小さいものを作る、というアルゴリズムを実装しました。

だいぶそれらしくなったんじゃないでしょうか。 点数は30.0Mでした。

小さい順に描く

大きい長方形を不用意に描くと、あとから長方形を描き足しにくくなりそうです。 描いてよい長方形の大きさの閾値を決めておき、すべての印を調べても長方形を書き足せなくなったら、閾値を引き上げていきます。

32.0M。ちょっと上がった。 そろそろ、楽に実装できる改善点がおもいつかなくなってきました。

時間は足りてる？

今のプログラムは4.8秒で処理を打ち切って出力しています。試しに処理時間を変えて実行してみます。時間を長くするとスコアが伸びるようであれば、高速化でスコアが伸びる余地がある、ということになります。また、時間を短くしてもスコアが変化しないようであれば、時間が余っていて、遠慮なく処理を増やしてよいということです。

結果は……

実行時間[秒]	seed=1のスコア
0.01	432543
0.05	604477
0.1	604477
1.0	604477
3.0	604477
4.8	604477
10.0	604477

全然余ってた！

敷き詰める

上図のように、印と縦横の線が隙間なく描かれている状態を考えると、四角形は辺を共有できないという制約上、下図のような四角形の組み合わせでできているはずです。

つまり、最小の正方形が市松模様状に並んでいるパターンです。これを実現するために、チェス盤でいう同色のマスにのみ、最小の正方形を描いてよい、という制約を設けました。

斜めの最小の正方形を描く場合においては、上図の緑の線と紫の線は互いに影響しません。

それぞれのレイヤごとに、正方形が市松模様に並ぶように、正方形を描く場所を制限します。

各レイヤで敷き詰め方が2パターンあるので、2x2x2の8パターン試して最良のものを採用。

結果はこちら。

かなり敷き詰まってる！！　提出結果は35.8M点！

焼鈍

そろそろ焼きなましをしたいです。（なおコンテスト中は以下の方法を山登り法だと思っていました。）

一部の印を消して、長方形を描き直していきたいのですが、印を消した時には、その印を利用して描いた印も消さなければ、不正な出力になってしまいます。

それぞれの印に、その印を描いた時に作られた長方形の情報を持たせます。長方形の残りの３頂点が、依存先の印になります。逆方向にもたどれるようにしておきます。

ランダムに印を一つ選び（初期状態からあるものは除く）、削除します。その印に依存するすべての印を再帰的に探索し、すべて削除します。その状態から長方形をかけるだけ描き、元の状態と点数を比較し、良くなっていたら更新します。

得点は跳ね上がり、46.8M点！　暫定順位80位になりました。

まさかこんな順位に来れるとは思っていませんでした。でも、強い人たちがラストスパートをかけてきそうなので、あまり浮かれるとがっかりするかも。

その後、消す印の数に上限を設けたり、なるべく外側に印をつけるようにしたりして少し改善し、暫定48.5M点、82位となりました。

最終結果

システムテストの結果が出たら書きます。

感想

苦しくも楽しかった！　ビジュアライザでいい感じの絵が出たときはとても興奮します。

単純なルールでありながら、人によって考察がいろいろあり、それでいてアルゴ的な最適解が出るわけでもないのが面白いです。問題作る人すごすぎ。

方法を思いつくことと、それを実装することの間には大きな隔たりがあるということを改めて実感しました。

今後の課題

もっと多くのテストケースを試したほうがよさそう。

いろいろな定数を直感で決めてしまったけれど、ちゃんとデータを見て調整するべきだった。そのためにも、いろいろなデータを見える化すべき。焼きなましが回った回数や改善度合いとか、テストケースの種類（印の密度など）による得点の傾向とか。

おまけ　用意した主な関数一覧

• 指定した座標から指定した座標を見た方向（0~7）を返す
• 指定した座標が盤面内にあるか返す
• 指定した座標に印があるか返す
• 2つの座標を結ぶ線上に印があるか返す
• 指定した座標に印をつける/消す（依存関係も修正する）
• 指定した座標から指定した方向に線が引かれているか返す
• ２つの座標を結ぶ線上に線が引かれている箇所があるか返す
• ２つの座標の間に線を引く/消す
• 指定した座標から指定方向に向かって最も近い印を返す
• 指定した長方形を描けるか確かめる
• 指定した印を頂点とする、作れる長方形のリストを返す
• 指定した長方形を描く/消す
• 指定した印と、それに依存する全ての印と長方形を消す
• 回答用文字列を生成する
• 指定した座標の重みを返す
• 盤面の印の重みの総和を返す
• 盤面の得点を返す
• 盤面の状態を出力する