第8回Asprovaプログラミングコンテスト参戦記

# はじめに

本記事は、AtCoderで行われたヒューリスティックコンテスト「[第8回 Asprova プログラミングコンテスト](https://atcoder.jp/contests/asprocon8)」の参戦記です。
これまで、ヒューリスティックコンテストの解法関連の記事を書いてきましたが、今回はあまり整理せずに(生々しい感じで)時系列的にどのような形で取り組んできたかを中心に書いていこうと思います。

1週間程度のコンテストで、このようなことを考えながら取り組んでいるという参考にしていただければ幸いです。

# 問題概要
今回の問題は「[Automated Painting Line](https://atcoder.jp/contests/asprocon8/tasks/asprocon8_a)」というもので、概要は以下の通りです。

- 工場の円環状のラインで、4〜10種類の製品に、4〜10色の色を塗る
- 製品数×色数ごとに、生産数が与えられる(全組み合わせ合計で1000〜5000)
- 円環状のベルトコンベアーには250個のフックがついており、スタート地点でフックに製品を掛ける(そして戻ってきた製品を回収する)ことができる
- 製品の種類や色が変わるときは、所定のフック数だけ間隔を空ける必要がある(色が変わる時の方が必要な間隔が広め)
- フックに製品を掛けるとき、フックと製品の間に製品の種類ごとに専用のハンガーが必要で、ハンガーの数も与えられている
- ハンガーの着脱回数、製品がかかっていないフックの数に対して所定のペナルティが発生する

この条件で、ペナルティをなるべく少なくする問題です。

# 取り組み経緯
## サンプル・ジャッジの移植
今回、それなりのスコアが獲得できるレベルのサンプルプログラムがついていました。サンプルはC++ですが、筆者はJavaで参加しているので、Javaに移植してみました。
また、ジャッジプログラムもついていたので、これもJavaに移植しました。

- 移植をすることで問題に対する理解が深まる
- 基本的なプログラムの骨格のイメージができる
- 自プログラム内でのスコア計算ができるようになる

移植だけでこれだけのメリットが得られました。

## エリア固定方式
今回のスコアはハンガーの掛け替え回数を少なくした方が良いので、まずは250個のフックの一定範囲を決まった製品用のエリアとして固定することにしました。こうすれば最初に掛けたハンガーを掛け替えずに済みますし、ハンガーが足りるかどうかを心配する必要もなくなります。
また、色の変更時の必要間隔が全体的に長めなので、色も順番を決めておいて、ある色が全部終わったら次の色、というように色の変更回数が少なくなるようにすることにしました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202945/deb0f083-1706-957e-f531-cca2702b4f18.png)

製品の順番と、色の順番はそれぞれ巡回セールス問題で解きました。製品種類数も色数も10までなので、これは完全に解くことができます。

製品エリアと製品エリアの間は、その製品間で必要な間隔を空けておくことにして、250個から必要間隔を取り除いた分を、製品ごとの生産数で比例配分してエリアの幅を決めました。

色が1色終わったら必要な間隔をあけて、製品エリアに入ったら次の色のその製品を作るというようにしました。今回は実装が難しそうなので、まずはあまり複雑なことを考えずに一旦実装してみました。

この結果、暫定テストのスコアが492.8M(ペナルティ7.2M)となり、この時点で1位となりました。

## 貪欲方式
今回の問題では、空きフック数のペナルティの係数と、ハンガー掛け替え回数のペナルティの係数がそれぞれ与えられています。エリア固定方式だと、掛け替えペナルティは非常に少なくて済みますが、連続して実行する製品が細切れになりがちで、空きフックペナルティは少し多めになります。テストケースによっては、ハンガー掛け替えの係数が小さいこともあるようなので、掛け替え回数には目を瞑って、空きハンガー数を少なくなるように考えてみることにしました。

製品の順番と色の順番は先ほど同様に巡回セールスマンで求めた順番として、次の製品が掛けられれば掛けられるだけ連続して掛けるようにしてみました。
当然、ペナルティの係数によっては先ほどのエリア固定方式の方が良い場合もあるので、両方やってみて良い方で提出するようにしてみました。

ここまでで暫定スコアは493.7M(ペナルティ6.3M)となりました。

## 貪欲方式の改善
### 試行を増やす
ここまでの状況をビジュアライザーで見ていたところ、ある色の最後の時に1製品だけが残っていてなかなか順番が回って来ずに空きハンガー数がやたらと増えてしまうという状況があることに気がつきました。

製品や色で作った巡回セールス問題ルートはループになっているので、どこから始めても最短経路であることは変わりません。色の終わりにどの製品が残るかをうまくコントロールするのは難しそうですが、どの製品の種類・どの色から始めるかは比較的簡単に変えることができます。エリア固定方式も貪欲方式もほぼ一瞬で終わるので、差し当たり貪欲方式は始点となる製品種類・色を全通り(最大でも100通りの組み合わせ)試してみて、一番良いものを提出するようにしてみました。

これで494.1M(ペナルティ5.9M)で、まだ1位をキープしています。

### 逆周追加、ハンガー待ち方式改善
巡回セールス問題ルートは逆周でも当然最短距離なので、逆周も実行してみることにしました。実行時間にはまだまだ余裕があるので、試すパターンが増えれば増えるだけ確率的にスコアが上がります。

ここでビジュアライザを見ていると、やはり色の最後の製品がちょっとだけ残ってしまって、その製品が回ってくるまでハンガーの空きをかなり待たされるという状況が発生していました。
比較的簡単に改善できそうな方法として、その製品・色の残りがハンガーの数の1倍〜2倍の場合は2等分して実行するようにしてみました(例えば1.2倍だけ残っていたら、1倍＋0.2倍ではなく、0.6倍＋0.6倍で実行)。こうすることで、最後の製品の待ち時間が減り(間に入っている他の製品の幅が少し短くなるため)、スコアも少し改善しました。

ならばと、最初から何周するかを考えて等分するというのもやってみましたが、逆効果だったのでやめました。

ここまでの実装をしている中で、貪欲でハンガーの個数分だけ製品を掛けるときに、利用可能ハンガーがなかった場合にそのままその製品のハンガーが回収できるのを待つか、諦めて次の製品に進むか、考え方に二択あることに気がつきました。
試してみると、待った方が良いケースと、諦めた方が良いケースの両方ともあるようだったので、両方試して良い方を提出するようにしました。実行時間はまだまだ余裕があります。

ここまでで494.7M(ペナルティ5.3M)です。

## リファクタリング
参加された方はわかると思いますが、今回の問題は実装がかなり大変です。ベルトコンベアーがループしていたり、製品の順番もループにしたりと、ループになるものが多く、コンベアー上のある範囲にあるかどうかの判定とかも単純な大小だけでは判定できません。もちろん剰余を取ったり、場合分けして比較したりと、1つ1つは(アルゴリズムコンテストの難しい部類の問題に比べればはるかに)簡単に実装できるのですが、量が増えてくるとプログラムが読みにくくなり、本当に考えたいアルゴリズムを考える上で邪魔になってきます。人間の注意力は有限なので、こうした枝葉の部分で注意力を消耗するのはよろしくありません。

まだコンテスト期間も半分以上あったので、ここで大幅にリファクタリングを実施することにしました。骨子は以下の通りです。

- コンベアー上の座標や製品種類・色は専用クラスを作り、先に進めたりするときに`p.add(len)`みたいな感じで余計な剰余とかが目に入らないようにする
- ハンガーの状態、空きハンガー数、残り所要数といった状態管理専用のクラスを作り、`state.skip(len)`などとすれば、よろしくやってくれるようにする
- 貪欲法をやるときなど、ハンガーがあれば回収・なければスキップ、などというのも目に入ると鬱陶しいので`state.removeOrSkip(len)`などとすれば、あとは勝手にやってくれるようにする

こんな感じで、生産計画のアルゴリズムを考える上で本質的ではなさそうな、目に入るだけで注意力を消耗するような内容は極力目に入らないようなところに追いやることにしました。

あと細かいことですが、今回のスコアは各ケース「10000000-ペナルティ」となっていますが、ペナルティが大体10万点前後となっていて、スコア9900000みたいになります。9900000と9910000だと0.1%くらいしか変わっていないように見えますが、本質的にはペナルティが100000から90000に1割改善しているので、それがパッと見でわかるように、手元で結果を表示するときにペナルティの値が表示されるようにしました。
目に入れたいものが目に入るようにすることは大切だと思います。

## ゾーン型方式
リファクタリングにより大分見通しが良くなったので、新たな方法を考えることにしました。

最初のエリア固定方式は単純で良かったのですが、ハンガーは余っていますし、あと1個で作り終わるのも次の周回送りになったりと、全く融通が効かないので今ひとつです。

そこで、ベースとなる基本エリアは残しつつ、ここまでは拡張して良いという最大エリア(ゾーン)を定義することにしました。ゾーンは基本エリアを中心に、ハンガーの最大数分まで左右に広げます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202945/6e0d34dc-276b-b667-3909-4aa2afe9de26.png)

広げたゾーン内であっても、ゾーン幅はハンガー数までにしているので、ハンガー不足を気にすることなく計画を立てることができます。

実行計画は以下のような感じにしました。

- 色が開始されたら、その色の実行計画を立てる
- 各製品間の必要間隔は変わらないため、ゾーン内で実際に製品を掛ける範囲の幅が変わったとしても1周の合計数は変わらないので、最低何周しないと行けないかはわかる
- 最後の1周はなるべく前半の製品に寄せて、後半はその前の周までに終わらせるようにする

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202945/ceed939d-15d9-815c-e71c-c9e3e284bb91.png)

これで495.2M(ペナルティ4.8M)まで改善しました。ただ、実はこの時に実行計画を立てるプログラムにバグを仕込んでいて正しく動作していなかったので、本来はこの考え方でもう少し改善していたと思われます。

## 巡回セールスマンなし貪欲
これまでは巡回セールスマンで求めたルートをベースに実行していましたが、貪欲方式だったらもはやハンガー待ちの方が支配的でルートはあまり関係なくなっているのではないかと思い立ちました。

そこで、ルートを予め決めずに、以下のような考え方で貪欲をしてみることにしました。

- 色ごとに終わらせていく考え方は踏襲
- ハンガー数を元に、各製品残り何周かを管理
- 残り周数の多い方から実行。残り周数が同じ場合は、実行待ちが少なくて済むものから実行

これで微改善し495.3M(ペナルティ4.7M)となりました。この頃には周りの方もスコアが伸びていて、順位的には6位に後退していました。

この方式は、最終的にビームサーチ的な方法にしたかったのですが、そこまではできませんでした。

## ルートバリエーションを増やす
ここまでは、巡回セールスマン問題のルートは最短1つでやっていましたが、製品数は高々10個なので、全パターンの経路を考えることができるオーダーです。実行時間にもまだまだ余裕があるので、全パターンの経路を考えて経路長の短いものから1000個くらい取ってきて、順番に実行してみることにしました。

今まで考えてきたエリア固定方式、貪欲方式、ゾーン型方式の全てに対して、ルート長の短いものから順番に試していき、制限時間になったら打ち切るようにしてみました。

これで495.4M(ペナルティ4.6M)となりました。思ったほど伸びません。

## 伸び悩みとバグ修正
ここでしばらく伸び悩みます。この期間で以下のような対応をしました。

- 製品だけでなく、色のルートも全パターン用意して、製品ルートとの組み合わせで実行していく
- ゾーン型はゾーンが広すぎて必要以上に掛け替えが多発するかもしれないと思い、隣の基本エリアまでは侵食しない範囲で設定するアルゴリズムも追加(元のアルゴリズムと併用)
- 製品ルートと色ルートのバリエーションは元々製品ルートのバリエーションを重視していたが、色ルートのバリエーションが多い方が良いようだったので、試す順番を変更

それぞれ少しずつ改善はしているのですが、あまり劇的ではなく、上記を全部やっても495.47M(ペナルティ4.53M)でした。

ここで、ゾーン型の実行計画に仕込んでしまっていたバグに気がつき、この修正で一気に495.87M(ペナルティ4.13M)まで改善しました。順位も3位まで浮上しました。

## 高速化
### 複数命令の一括化
ここまで、状態管理や命令の実行は1ステップずつやっていましたが、製品を掛けるにせよスキップするにせよ、ほとんどの場合は連続して何回か実行することになります。これを1回ずつやっていくのは実行時間的にはもったいないです。

コンテスト期間は残り2日(土日)でしたが、他にできそうなこともなくなってきていたので、複数回の実行を一気にできるよう、状態管理クラスを改造することにしました。この改造は土曜日だけで終わり、試行回数は数倍程度に増えました。スコアは微増ではありますが495.92M(ペナルティ4.08M)です。

### 役に立たない方式の実行回避
ここまでの改善で、既にエリア固定型が役に立っているケースはほとんどなかったので、廃止することにしました。(ゾーン型で代替できていたものと思われます)
また、貪欲型が役に立つのも架け替えペナルティ係数が低い場合に限られていたので、そのような場合のみ実行するようにしました。

これによって、効果が出る可能性の高いアルゴリズムの試行回数が増えて、若干スコアが改善しました。

### ゾーン型の実行計画立案の高速化
ゾーン型の実行計画を立てる際に、どの製品で終わるかの目標を1つずつ進めていき、その目標に対して各製品がうまく収まるか、という製品の2乗のループになっていたのですが、よく考えるとdfsで行きは+1周したとした時の実行幅を求めていき、帰りは±0周とした時の幅を求めていって、ちょうど折り合うところを見つければ1乗のオーダで済むことに気がつきました。

この改造をしていく中で、おそらく細かい不具合の修正もできたようで、両方合わせて496.03M(ペナルティ3.97M)に到達しました。

## 可変ゾーン型
さて、最終日です。最後に1つやろうと思っていたことがありました。これまでのゾーン型は、最初にゾーンを決めていましたが、基本範囲だけ最初に決めておき、残りの余力については必要に応じて拡張して行った方が効率が良いのではないかと思っていました。
色々とソースも整備されてきたので、最後のこの改造に取り組んでみました。基本的にはゾーン型と同じ仕組みですが、実行計画を立てる際に、余力分で可能な場合はその実行計画を許容し、その計画で確定したらエリアを拡大するというような実装です。

これで496.096M(ペナルティ3.904M)になりました。

## 微調整
最終日も午後に入ってきたので、残りは試行回数に関する微調整をすることにしました。テストケースは300用意し、以下のような形で色々調整し、スコアが良くなったものを採用しました。

- 製品ルート・色ルートに関する試行は、製品ルートを最善より+1長いところまで実行し、なくなったら次の色ルートに進んで試行、というようにしていたが、移り変わるタイミングを色ルートがある程度の数実行できるように調整
- 色ルートの2つ目以降は、そこまでで最善のアルゴリズム以外は実行しないように変更(最善アルゴリズムが変わる場合が少なかったので)

最終的に496.104M(ペナルティ3.896M)で、暫定順位では5位となりました。

## 強化テスト
2000ケースでテストを実行しました。本当はもう少し数を増やしてテストすべきだったかもしれません。

# まとめ
今回はこの規模のコンテストでは初めて(暫定ではありますが)1桁の順位を取ることができました。
今回大切だと思ったことは以下の通りです。

- 人間の注意力は有限。見たくない細かい処理は見えないところに追いやる
- あるパターンだけ通用しそうな考え方でも、複数組み合わせればそれなりに戦える
- 正確な実装は難しくても、大体正しい実装ができればそれなりに戦える

皆様のヒューリスティックコンテストライフの参考になれば幸いです。