ハル研究所プログラミングコンテスト2017をやってみよう
この記事はtraP Advent Calendar 2017 20日目の記事です。
こんにちは、nariです。普段はおふとんで競プロをしています。たまにゲームも作ります。Twitterはやってません。
10月27日まで開催していた ハル研究所プログラミングコンテスト2017 に参加して、めちゃくちゃ楽しかったのでこちらで紹介します。ちなみに順位は終了時点で6位でした。
ハル研究所プログラミングコンテストとは
http://www.hallab.co.jp/progcon/
星のカービィシリーズ等を作っているゲーム製作会社、ハル研究所が主催するプログラミングコンテストです。
年に一度開催しており、上位入賞者には賞金や記念品が授与されます。
ハル研プロコンは社内でのプロコンを含めるとすでに20年以上の歴史を持っているらしいコンテストで、基本的には「解くのに時間がかかる、または最適解が基本的に求まらない」問題を数週間かけて解くということを行います。
現在残っている特設サイトは2013年が最古ですが、そこからの問題は「2次元平面で幾つかのオブジェクトが動いている」「その動きを最適化したい」というものになっています。ゲームっぽい問題ですね。
例えば2013年はクリーナーロボットを動かしてゴミを回収したり、2014年は敵よりステータスの劣る忍者を動かしてレースを行ったりしています。
また、ハル研プロコンの特徴として問題パッケージに解のビュアーが付属しているため、ダウンロードしてすぐに動きのビジュアライズが出来ます。自分でビュアーを書く必要がないため、本体のプログラムに専念でき、また初心者でもとっつきやすいコンテストになっています。
参加できるのは学生とハル研究所の社員のみで、毎年熾烈な戦いが繰り広げられています。ハル研社員が深夜にスコア更新したりしていて本業に支障が出ないかすごく心配になるんですが……
改善がうまくいくとスコアが一気に良くなったり、ちまちまと改善を重ねたり、いろいろやることがあってすごく楽しいコンテストです。僕は今回最終日は夜通し実装をしていました。
ハルコン2017を実際にやってみる
ハル研究所プログラミングコンテストはすごく楽しいです！みんなやってね！
と言ってもすでにハルコン2017は終わってしまいました……
じゃあもう参加できないのか？というとそうではなく、現在でも問題パッケージはダウンロードでき、ローカルで本番同様に実行することが出来ます。今回はこれを使って、実際にハルコン2017に擬似参加してみましょう！
目標スコアは、本番でチャレンジスコアに設定されていた22,222にします。実際のコンテストでチャレンジスコアを達成すると記念品が抽選で貰えるようになるので、ここが一つの目標となると思います。
問題概要
ハルコンは割とスケールの大きい問題になるので、問題概要をしっかり把握するのが大事です。
http://www.hallab.co.jp/progcon/2017/question/
今回の問題の大事なポイントは以下の通り。
- 大UFO2個と小UFO8個を操作して、農場の周りの家に箱(農場産のオレンジが入っている)を運ぶ
- 大UFOはいっぱい箱を持てるけどスピードが遅い、小UFOは素早いけど少ししか箱を持てない
- ほとんどの家は「街」になっていてまとまって配置されているが、一部の家は街から離れたところに配置されている
- UFOは「農場で箱を積み込む」「家で箱を配達する」「UFO同士で箱を受け渡す」というアクションができる
- 出来るだけ早く箱を全ての家に積み込むとスコアが良い
実際に動かしてみる
文章で書かれていてもいまいちピンときませんね、そこで実際にサンプルプログラムを動かしてみましょう。
http://www.hallab.co.jp/progcon/2017/question/package/
ページから問題パッケージをダウンロードして解凍します。
実際にプログラムをコンパイルする必要があるのでそのための環境が必要ですが、WindowsならVisual Studio用の、MacならXcode用の設定ファイルがあるので、それを使うと便利です。また他のエディタを使う場合でもMakefileが用意されているので、これを使うことも出来ます。
コンパイル(ビルド、またはmake)すると hpc2017.exe という名前の実行ファイルが生成されます。
これを実際に実行すると、次のように出力されます。
$ ./hpc2017.exe
stage | turn
0 | 648
1 | 690
2 | 519
3 | 498
4 | 689
5 | 1013
6 | 532
7 | 560
8 | 477
9 | 661
10 | 710
(省略)
190 | 636
191 | 549
192 | 500
193 | 612
194 | 565
195 | 418
196 | 764
197 | 162
198 | 568
199 | 716
TotalTurn: 111975
Time: 0.083 sec
これがサンプルプログラムで問題を解いた時の結果となります。
200個並んでいる数字は各ステージのステージIDとそのステージをクリアするのにかかったターン数で、TotalTurnがターン数の200ステージの合計です。
またTimeとして出ているのが実行時間で、これは環境によって変わります。実際のコンテストではサーバ側での実行時間が60秒以内に入る必要がありますが、今回は気にせず進めましょう。
今回サンプルプログラムの結果、111975というスコアが得られました。目標の22222にはおよそ5倍の改善が必要そうですが……
ビュアーで見てみる
では、実際にこの時のUFOの動きをビュアーで見てみましょう。
まず、ビュアーで見るために実行結果を記録する必要があります。コンパイルで作成されたファイル hpc2017.exe を使って、次のようにすると実行記録が出力されます。
$ ./hpc2017.exe -j > result.json
次に、ビュアーを立ち上げます。ビュアーはパッケージ内の viewer フォルダに入っており、index.html をブラウザで開くと見れます。
ビュアーの左上のボタンを押して先程の result.json を選択すると、実際の動きが見られます。(少し重いかもしれません)
真っ赤なセルが200個出てきました。色は緑が良く、赤が悪いということを表しているので、このサンプルプログラムは最悪ですね……
動きを見るには、セルをどれかクリックして、再生を押します。各セルが各ステージに対応しています。
うわあ……なんだこれは……たまげたなぁ……
あるUFOに着目して眺めるとわかりますが、1つのUFOが無駄に縦横無尽に走ってしまっています。明らかに他のUFOが行くべき家にお邪魔していたり、逆にまとめて行ったほうがいいところをスルーして遠いところに向かったりしています。これはひどい。
しかも大UFOがまだ動いているのに小UFOは幾つか運んだ後はサボっています。これはひどい。
さて、UFOの動きがひどいことはさておき、家の配置をよく見てみましょう。複数のステージをいろいろと見てください。
問題概要であったように、家は2個か3個の「街」に集中していて、「街」以外にも幾つか家が点々としています。
また、農場はステージのど真ん中にあるということもわかります。
さらに、各UFOのスピードもどれぐらい違うかわかると思います。大UFOはおっそろしく遅いです。
ビュアーではUFOにマウスカーソルを載せると、UFOのIDと、UFOが今いくつ箱を持っているかが分かります。これを見ると、大UFOは最大で40個の箱を、小UFOは最大で5個の箱を積めることもわかります。
初めてのプログラム読解
では、このひどすぎるサンプルプログラムがどのようにプログラムされているかを実際に見ていきます。
結論から言うと、プログラムは src フォルダ内の Answer.cpp に書いてあります。また今後書き換えるプログラムは全て Answer.cpp にしか書きません。それ以外のファイルは実際にプログラムを動かしたりするために必要なだけで、いじりません。いじってもハルコンに提出できる(できた)のは Answer.cpp のみなので、意味がありません。
ということで、Answer.cpp を見ていきます。と思ったのですが、ハルコンの規約でパッケージのソースコードはコンテスト参加以外の目的で再配布するのが禁止されているので、実際のソースコードは提示せず、どのようなプログラムが書いてあるかだけここに書きます。実際のソースコードはパッケージをダウンロードして見てみてください。
Answer.cpp には Answer.hpp にあるようなクラス・メソッドを実装する必要があり、それが下の方に書いてあります。
サンプルプログラムでは Answer クラスはあくまで Answer.hpp の通りに実装しただけで、実際は Solver クラスのメソッドを呼び出しているだけなので、サンプルプログラムの本体は Solver クラスにあります。これが Answer.cpp の上部分です。
実際に Solver クラスを見ると、init メソッド、moveItems メソッド、moveUFOs メソッドがあります。
init メソッドは各ステージの開始時に一度だけ呼び出されます。ここでUFOの動きを決めてしまうことになります。その他の関数はステージのターンごとに何度も呼び出されるので、一度だけ実行したいことはinitメソッドに書きます。引数のaStageにステージ情報が入っています。
moveItemsメソッドでは箱の移動を実行します。引数のaActionsに、行いたい動作に対応するActionを追加することで、箱を移動させる事ができます。一応aActionsに追加できる数に上限はありますが、普通のプログラムでは上限に達することがないはずなので実質無制限です。
moveUFOsメソッドでは各UFOの移動先を指定します。引数のaTargetPositionsに、UFOのID順に目的地を追加することでUFOを移動させることができます。つまり、aTargetPositionsの0番目には0番目のUFOの目的地を、1番目には1番目のUFOの目的地を、という形になります。実際にはUFOのスピードに応じて、目的地に近づくように移動します。
サンプルプログラムでは、initメソッドで各UFOに担当する家を割り振って、毎ターン「箱が0個だったら農場に積みに行く」「箱を持っていたら担当している家に向かう」という動作を行っていることがわかります。
サンプルプログラムの問題点
サンプルプログラムの実行結果をビュアーで見た時の問題点として、「UFOが行ったり来たりしすぎ」というのがありました。サンプルプログラムでは担当する家を、位置関係を何も見ずに適当に割り振っていました。とりあえずここが問題でしょう。
改善1 : 角度ソート
ではどのように割り振ればいいでしょう？今回は農場が中心にあり、その周りに家があります。なので、農場を中心とした時の家の位置の角度でソートして、順番に割り振ると良さそうです。
これを実装したのが次のプログラムです。なお、ArrayとVector2はハルコンで用意されているクラスで、Arrayは上限付き可変長配列、Vector2は2次元ベクトルを管理できます。便利なので使いましょう。
また、ソートするために std::sort を使っています。これを使うために Answer.cpp の先頭に #include <algorithm> を追記する必要があります。
class Solver
{
private:
/// 各UFOが次に向かう家のIDリストのインデックス。
Array<int, Parameter::UFOCount> mTargetHouseIndices;
/// 各UFOの担当している家のIDリスト
Array<int, Parameter::MaxHouseCount> mTargetHouseIdList[10];
public:
void init(const Stage& aStage)
{
int ufoCount = aStage.ufos().count();
mTargetHouseIndices.clear();
for(int i=0; i<ufoCount; i++){
mTargetHouseIdList[i].clear();
}
// 家を、農場中心の角度でソートする
int houseCount = aStage.houses().count();
Array<int, Parameter::MaxHouseCount> houseIds;
for(int i=0; i<houseCount; i++){
houseIds.add(i);
}
Vector2 basePoint = Vector2(100.0f, 0.0f);
// #include <algorithm>
std::sort(houseIds.begin(), houseIds.end(), [&](int a, int b){
Vector2 to_a = aStage.houses()[a].pos() - aStage.office().pos();
Vector2 to_b = aStage.houses()[b].pos() - aStage.office().pos();
return basePoint.rotSign(to_a) < basePoint.rotSign(to_b);
});
// 各UFOは、(houseCount/ufoCount)または(houseCount/ufoCount)+1個の家を担当する
int head = 0;
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
int num = houseCount / ufoCount;
if(ufoIndex < houseCount % ufoCount){
num++;
}
mTargetHouseIndices.add(0);
// num個の家を割り振る
for(int i=0; i<num; i++){
mTargetHouseIdList[ufoIndex].add(houseIds[head]);
head++;
}
}
}
void moveItems(const Stage& aStage, Actions& aActions)
{
int ufoCount = aStage.ufos().count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = aStage.ufos()[ufoIndex];
// 農場の上にいたら箱を積み込む
if (Util::IsIntersect(ufo, aStage.office())) {
aActions.add(Action::PickUp(ufoIndex));
}
// 担当の家の上にいたら配達する
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex == TARGET_HOUSE_NONE) {
continue;
}
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
if (ufo.itemCount() == 0 || !Util::IsIntersect(ufo, aStage.houses()[houseIndex])) {
continue;
}
aActions.add(Action::Deliver(ufoIndex, houseIndex));
// 目標の家を更新
mTargetHouseIndices[ufoIndex]++;
if (mTargetHouseIndices[ufoIndex] >= mTargetHouseIdList[ufoIndex].count()) {
// 担当の家はすべて配達終了
mTargetHouseIndices[ufoIndex] = TARGET_HOUSE_NONE;
}
}
}
void moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions)
{
int ufoCount = aStage.ufos().count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = aStage.ufos()[ufoIndex];
if (ufo.itemCount() == 0) {
// 箱がなければ農場に向かう
aTargetPositions.add(aStage.office().pos());
} else {
// 箱を積んでいれば担当の家に向かう
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex != TARGET_HOUSE_NONE) {
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
aTargetPositions.add(aStage.houses()[houseIndex].pos());
} else {
aTargetPositions.add(ufo.pos());
}
}
}
}
};
少し解説すると、initメソッドでまず家を角度ソートしています。Vector2にはrotSignというメソッドがあり、他のベクトルとの符号付き角度がわかります。なので、基準のベクトルとして(100,0)を作り、このベクトルからの角度を計算して、これでソートを行っています。
ソートしたら、各UFOに担当する家の配列を用意しておき、家の数が等しくなるようにソート順で割り振ります。
あとは、moveItemsメソッドとmoveUFOsメソッドを、この配列に沿って動くように変更しました。
コンパイルして実行すると
stage | turn
0 | 145
1 | 198
2 | 251
3 | 154
4 | 186
5 | 162
6 | 188
7 | 136
8 | 274
9 | 177
10 | 196
(省略)
190 | 212
191 | 198
192 | 154
193 | 266
194 | 222
195 | 178
196 | 212
197 | 187
198 | 169
199 | 218
TotalTurn: 33738
Time: 0.041 sec
一気に改善しました！サンプルプログラムは本当にひどいプログラムだったことがわかりますね。
ビュアーでも見てみましょう。
まだまだ赤いですが、一部緑が見えてきました。
動きも、縦横無尽に動かないようになりました。大改善ですね。
観察
かなり良くなりましたが、まだ22222には届きません。どこが悪いのでしょう？
少しビュアーを見ると、大UFOが遅いのが問題なように思えます。さらに、大UFOは配達完了時に30個ほど箱を持て余しています。この特性を活かせば、もっと良い動きが作れるに違いありません。
改善2 : 街に大UFOを飛ばす
「街」は家が密集しているので、同じ軒数の家を回る場合でも、「街」を回ったほうが総移動距離が短くなります。
よって大UFOは「街」に飛ばすようにするとより良い働きをするのではないでしょうか。
ということで、大UFOは「街」の内10軒を回るようにしてみましょう。
void init(const Stage& aStage)
{
int ufoCount = aStage.ufos().count();
mTargetHouseIndices.clear();
for(int i=0; i<ufoCount; i++){
mTargetHouseIdList[i].clear();
}
// 割当ているかいないかの配列
// true なら割り当てていない
int houseCount = aStage.houses().count();
Array<bool, Parameter::MaxHouseCount> available;
for(int i=0; i<houseCount; i++){
available.add(true);
}
// 大UFOを「街」に飛ばす
for(int largeUfo=0; largeUfo<2; largeUfo++){
// 街の中心となる家を探す
// 「半径100にある家の数」が最大となるような家を街の中心とする
int centerHouse = -1;
int bestHouseCount = -1;
for(int i=0; i<houseCount; i++){
if(!available[i])continue;
Vector2 hpos = aStage.houses()[i].pos();
int temp = 0;
for(int j=0; j<houseCount; j++){
if(!available[j])continue;
if(hpos.dist(aStage.houses()[j].pos()) <= 100.0f){
temp++;
}
}
if(bestHouseCount < temp){
centerHouse = i;
bestHouseCount = temp;
}
}
// 街の中心を大UFOに割り当てる
mTargetHouseIndices.add(0);
mTargetHouseIdList[largeUfo].add(centerHouse);
available[centerHouse] = false;
// 近いところを9個割り当てる
Vector2 currentPos = aStage.houses()[centerHouse].pos();
for(int _=0; _<9; _++){
int nextHouse = -1;
float bestDistance = 252521.0f;
for(int i=0; i<houseCount; i++){
if(!available[i])continue;
float dist = currentPos.dist(aStage.houses()[i].pos());
if(dist < bestDistance){
nextHouse = i;
bestDistance = dist;
}
}
mTargetHouseIdList[largeUfo].add(nextHouse);
available[nextHouse] = false;
currentPos = aStage.houses()[nextHouse].pos();
}
}
// 家を、農場中心の角度でソートする
Array<int, Parameter::MaxHouseCount> houseIds;
for(int i=0; i<houseCount; i++){
if(available[i])houseIds.add(i);
}
Vector2 basePoint = Vector2(100.0f, 0.0f);
// #include <algorithm>
std::sort(houseIds.begin(), houseIds.end(), [&](int a, int b){
Vector2 to_a = aStage.houses()[a].pos() - aStage.office().pos();
Vector2 to_b = aStage.houses()[b].pos() - aStage.office().pos();
return basePoint.rotSign(to_a) < basePoint.rotSign(to_b);
});
int head = 0;
int houseNum = houseIds.count();
// 残りの家を小UFOに割り当てる
for (int smallUfo = 0; smallUfo < ufoCount-2; smallUfo++) {
int num = houseNum / (ufoCount-2);
if(smallUfo < houseNum % (ufoCount-2)){
num++;
}
mTargetHouseIndices.add(0);
// num個の家を割り振る
for(int i=0; i<num; i++){
mTargetHouseIdList[smallUfo+2].add(houseIds[head]);
head++;
}
}
}
アルゴリズムとしては、まず街の中心を探します。この探し方にはいろいろあると思いますが、今回は「ある家で、その家を中心とした半径100の円の中にある家の数が最大となるような家」を街の中心としました。これはStage.cppを見ると分かるのですが、街は半径100の中に家を20軒配置するため、このようにするとおよそ街の中心が取り出せます。
街の中心を大UFOに割り振って、さらにそこから9軒ほど一番近い家を辿るようにして割り振ります。割り振った時、他のUFOに重複して割り振らないように配列を使って管理します。
すると、
stage | turn
0 | 144
1 | 157
2 | 133
3 | 101
4 | 149
5 | 154
6 | 140
7 | 136
8 | 163
9 | 113
10 | 131
(省略)
190 | 128
191 | 124
192 | 115
193 | 164
194 | 135
195 | 99
196 | 174
197 | 96
198 | 119
199 | 131
TotalTurn: 24739
Time: 0.046 sec
またもや一気に一万も改善しました！
大UFOのボトルネックが消えたためでしょう。
ビュアーの方も見てみましょう。
少しずつですが、赤いセルが減ってきています。
大UFOが最後まで動くようなステージがほぼ無くなったのがわかります。
観察
大UFOの移動ターン数が減ったのは良いのですが、今度は小UFOの移動ターン数がボトルネックとなってしまいました。
また、やはりまだ大UFOは積んでいる箱を持て余しています。
改善3 : 大UFOから補給
そこで、「UFOからUFOへ箱を受け渡す」という行動が出来ることを思い出し、小UFOの箱が無くなったら大UFOから箱をもらう、という行動が取れるように変えてみましょう。
Action.hpp を見ると、Action::Pass(from, to)とするとUFO同士で箱を受け渡すことが出来ます。この時、受け渡せる限界まで箱が受け渡されます。
void moveItems(const Stage& aStage, Actions& aActions)
{
int ufoCount = aStage.ufos().count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = aStage.ufos()[ufoIndex];
// 農場の上にいたら箱を積み込む
if (Util::IsIntersect(ufo, aStage.office())) {
aActions.add(Action::PickUp(ufoIndex));
}
// 大UFOから小UFOへ箱を受け渡す
if(ufoIndex >= 2 && ufo.itemCount() == 0){
for(int largeUFO=0; largeUFO<2; largeUFO++){
if(Util::IsIntersect(ufo, aStage.ufos()[largeUFO])){
aActions.add(Action::Pass(largeUFO, ufoIndex));
}
}
}
// 担当の家の上にいたら配達する
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex == TARGET_HOUSE_NONE) {
continue;
}
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
if (ufo.itemCount() == 0 || !Util::IsIntersect(ufo, aStage.houses()[houseIndex])) {
continue;
}
aActions.add(Action::Deliver(ufoIndex, houseIndex));
// 目標の家を更新
mTargetHouseIndices[ufoIndex]++;
if (mTargetHouseIndices[ufoIndex] >= mTargetHouseIdList[ufoIndex].count()) {
// 担当の家はすべて配達終了
mTargetHouseIndices[ufoIndex] = TARGET_HOUSE_NONE;
}
}
}
void moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions)
{
int ufoCount = aStage.ufos().count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = aStage.ufos()[ufoIndex];
if (ufo.itemCount() == 0) {
// 箱がなければ農場に向かう
Vector2 target = aStage.office().pos();
// 小UFOなら近い大UFOも候補にする
if(ufoIndex >= 2){
for(int largeUFO=0; largeUFO<2; largeUFO++){
Vector2 lpos = aStage.ufos()[largeUFO].pos();
if(ufo.pos().dist(lpos) < ufo.pos().dist(target)){
target = lpos;
}
}
}
aTargetPositions.add(target);
} else {
// 箱を積んでいれば担当の家に向かう
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex != TARGET_HOUSE_NONE) {
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
aTargetPositions.add(aStage.houses()[houseIndex].pos());
} else {
aTargetPositions.add(ufo.pos());
}
}
}
}
農場の代わりに大UFOからの受け渡しが出来るようにmoveItemsを書き換え、農場の代わりに大UFOに向かえるようにmoveUFOsを書き換えました。
stage | turn
0 | 124
1 | 130
2 | 113
3 | 101
4 | 151
5 | 154
6 | 113
7 | 136
8 | 163
9 | 106
10 | 131
(省略)
190 | 123
191 | 117
192 | 115
193 | 160
194 | 104
195 | 99
196 | 147
197 | 96
198 | 100
199 | 120
TotalTurn: 23921
Time: 0.046 sec
1000ぐらい改善しました。さすがにここまで来ると1万の改善は簡単に出ませんね……ただ22222が見えてきました。
毎度おなじみ、ビュアーをチェックしましょう。
ちょっと赤色が薄くなってきました。
うまく行ってるパターンだとかなり大UFOを活用できていますが、やはりまだ小UFOが遠くまで配達しに行くパターンが目立ちます。
観察
街の近くの家は大UFOが居座っているのですぐに運べますが、そうでないような場所の点々とした家にはやはり運びづらいように見えます。小UFO同士では速度は変わらないので、総移動距離が出来るだけ均等になるように割り振れるとよいのですが……
改善4 小UFOの割り振りを探索する
大UFOの動きはそのままに、小UFOの総移動距離が均等になるように割り当てていきます。そのために、改善4では少し難易度が高いですが探索を実装したいと思います。
まず、どの小UFOが一番遅いかを調べる必要があります。このためには実際に動きをシミュレートするしかありません。移動経路を辿って計算するのもいいですが、その場合大UFOを使って補給するという動きまで考慮できません。シミュレートして各UFOが運び終えるまでのターン数を返す関数を書いてしまいましょう。
シミュレートするにあたって、SolverクラスのmoveItems/moveUFOsメソッドがそのまま使えると便利なのですが、今のmoveItems/moveUFOsは aStage のUFO情報に基づいて計算します。実際の aStage の値はシミュレートでは書き換えられないので、UFO情報だけシミュレート用に別で作って、moveItems/moveUFOsに渡せるように書き換えておくと便利です。
void moveItems(const Stage& aStage, Actions& aActions, const UFOs& ufos)
{
int ufoCount = ufos.count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = ufos[ufoIndex];
// 農場の上にいたら箱を積み込む
if (Util::IsIntersect(ufo, aStage.office())) {
aActions.add(Action::PickUp(ufoIndex));
}
// 大UFOから小UFOへ箱を受け渡す
if(ufoIndex >= 2 && ufo.itemCount() == 0){
for(int largeUFO=0; largeUFO<2; largeUFO++){
if(Util::IsIntersect(ufo, ufos[largeUFO])){
aActions.add(Action::Pass(largeUFO, ufoIndex));
}
}
}
// 担当の家の上にいたら配達する
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex == TARGET_HOUSE_NONE) {
continue;
}
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
if (ufo.itemCount() == 0 || !Util::IsIntersect(ufo, aStage.houses()[houseIndex])) {
continue;
}
aActions.add(Action::Deliver(ufoIndex, houseIndex));
// 目標の家を更新
mTargetHouseIndices[ufoIndex]++;
if (mTargetHouseIndices[ufoIndex] >= mTargetHouseIdList[ufoIndex].count()) {
// 担当の家はすべて配達終了
mTargetHouseIndices[ufoIndex] = TARGET_HOUSE_NONE;
}
}
}
void moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions, const UFOs &ufos)
{
int ufoCount = ufos.count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = ufos[ufoIndex];
if (ufo.itemCount() == 0) {
// 箱がなければ農場に向かう
Vector2 target = aStage.office().pos();
// 小UFOなら近い大UFOも候補にする
if(ufoIndex >= 2){
for(int largeUFO=0; largeUFO<2; largeUFO++){
Vector2 lpos = ufos[largeUFO].pos();
if(ufo.pos().dist(lpos) < ufo.pos().dist(target)){
target = lpos;
}
}
}
aTargetPositions.add(target);
} else {
// 箱を積んでいれば担当の家に向かう
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex != TARGET_HOUSE_NONE) {
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
aTargetPositions.add(aStage.houses()[houseIndex].pos());
} else {
aTargetPositions.add(ufo.pos());
}
}
}
}
変更したのは aStage.ufos() を ufos にしただけです。
これを利用して、シミュレート関数を作ります。
void initIndices(){
// mTargetHouseIndices を初期化するだけ
while(mTargetHouseIndices.count() < Parameter::UFOCount){
mTargetHouseIndices.add(0);
}
for(int i=0; i<mTargetHouseIndices.count(); i++){
mTargetHouseIndices[i] = 0;
if(mTargetHouseIdList[i].count() == 0){
// 割り当てがない場合は最初から配達完了している
mTargetHouseIndices[i] = TARGET_HOUSE_NONE;
}
}
}
Array<int, Parameter::UFOCount> simulateResult;
void simulate(const Stage& aStage){
// simulateResult を初期化
for(int i=0; i<simulateResult.count(); i++){
simulateResult[i] = 2000;
}
while(simulateResult.count() < Parameter::UFOCount){
simulateResult.add(2000);
}
initIndices();
// シミュレート用の ufo を作る
int ufoCount = aStage.ufos().count();
UFOs sufos;
for(int i=0; i<ufoCount; i++){
if(i < 2){
// large ufo
sufos.add(UFO(UFOType_Large, aStage.office().pos(),
(float)Parameter::LargeUFORadius, (float)Parameter::LargeUFOMaxSpeed,
Parameter::LargeUFOCapacity));
}else{
// small ufo
sufos.add(UFO(UFOType_Small, aStage.office().pos(),
(float)Parameter::SmallUFORadius, (float)Parameter::SmallUFOMaxSpeed,
Parameter::SmallUFOCapacity));
}
}
int finishedUfos = 0; // 配達が終わったUFOの数
for(int i=0; i<ufoCount; i++){
if(mTargetHouseIdList[i].count() == 0){
finishedUfos++;
simulateResult[i] = 0;
}
}
// 200ターンシミュレートする(200ターンしてシミュレートが終わらない場合は強制終了)
for(int turn = 0; turn < 200 && finishedUfos < ufoCount; turn++){
// moveItems のシミュレート
Actions actions;
moveItems(aStage, actions, sufos);
// action の正当性チェックはせず、プログラムを信用する(プログラムの簡略化のため)
for(Action a : actions){
if(a.type() == ActionType_PickUp){
auto& ufo = sufos[a.ufoIndex()];
ufo.incItem(ufo.capacity() - ufo.itemCount());
}else if(a.type() == ActionType_Pass){
auto& src = sufos[a.srcUFOIndex()];
auto& dst = sufos[a.dstUFOIndex()];
int largeUfoNum = src.itemCount();
int smallSpace = dst.capacity() - dst.itemCount();
int passNum = largeUfoNum < smallSpace ? largeUfoNum : smallSpace;
dst.incItem(passNum);
src.decItem(passNum);
}else if(a.type() == ActionType_Deliver){
auto& ufo = sufos[a.ufoIndex()];
ufo.decItem(1);
}
}
// moveUFOs のシミュレート
TargetPositions targets;
moveUFOs(aStage, targets, sufos);
for(int i=0;i<10;i++){
sufos[i].move(targets[i]);
}
// 配達完了したUFOのチェック
for(int i=0; i<ufoCount; i++){
if(simulateResult[i] == 2000 && mTargetHouseIndices[i] == TARGET_HOUSE_NONE){
finishedUfos++;
simulateResult[i] = turn;
}
}
}
// 後始末
initIndices();
}
シミュレート用にUFOを用意して(UFOの使い方はStage.cppとかUFO.hppを見るとわかります)、後はmoveItems/moveUFOsをシミュレート用UFOで呼んでシミュレートします。シミュレート結果はsimulateResultという配列に入ります。
さて、シミュレート関数が出来たので、これを使って小UFOの割り当てをできるだけ均等になるようにしましょう。
まずハル研究所製Arrayを少しだけ扱いやすくするために、次の補助関数を作っておきます。
template <typename T, int C>
Array<T,C> copy(Array<T,C> &a){
Array<T,C> ret;
for(T x : a){
ret.add(x);
}
return ret;
}
template <typename T, int C>
void push_back(Array<T,C> &a, T v){
a.add(v);
}
template <typename T, int C>
void push_front(Array<T,C> &a, T v){
a.add(0);
for(int i=a.count()-2;i>=0;i--){
a[i+1] = a[i];
}
a[0] = v;
}
template <typename T, int C>
T pop_back(Array<T,C> &a){
Array<T,C> temp;
for(T x : a){
temp.add(x);
}
a.clear();
for(int i=0;i<temp.count()-1;i++){
a.add(temp[i]);
}
return temp[temp.count()-1];
}
template <typename T, int C>
T pop_front(Array<T,C> &a){
Array<T,C> temp;
for(T x : a){
temp.add(x);
}
a.clear();
for(int i=1;i<temp.count();i++){
a.add(temp[i]);
}
return temp[0];
}
copy は配列のディープコピー、他は配列の先頭及び末尾の操作を行う関数です。
準備は以上です。小UFOの割り当ての探索のプログラムを書きます。
// initメソッド内、前略
int head = 0;
int houseNum = houseIds.count();
// 残りの家を小UFOに割り当てる
for (int smallUfo = 0; smallUfo < ufoCount-2; smallUfo++) {
int num = houseNum / (ufoCount-2);
if(smallUfo < houseNum % (ufoCount-2)){
num++;
}
mTargetHouseIndices.add(0);
// num個の家を割り振る
for(int i=0; i<num; i++){
mTargetHouseIdList[smallUfo+2].add(houseIds[head]);
head++;
}
}
// 小UFOの割り当てを探索する
for(int times=0; times<100; times++){
// シミュレートする
simulate(aStage);
// 最悪ターン数を調べる
int worstTurn = 0;
int worstId = 0;
for(int i=0; i<10; i++){
if(worstTurn < simulateResult[i]){
worstTurn = simulateResult[i];
worstId = i;
}
}
// ボトルネックが大UFOだったらどうしようもない
if(worstId < 2){
break;
}
// あるUFOから隣のUFOに割り当てを渡す
// 割り当てを減らすUFO
int fromUFO = worstId;
// 減らせる割り当てが無かったらキャンセル
if(mTargetHouseIdList[fromUFO].count() == 0){
continue;
}
// 前後どちらのUFOに渡すか
bool destIsBefore = times%2==0 ? true : false;
// 割り当てを増やすUFO
int destUFO = fromUFO + (destIsBefore ? -1 : 1);
if(destUFO == 1){
destUFO = 9;
}else if(destUFO == 10){
destUFO = 2;
}
// 変化前の割り当てを覚えておく
auto fromTemp = copy(mTargetHouseIdList[fromUFO]);
auto destTemp = copy(mTargetHouseIdList[destUFO]);
// 割り当てをずらす
if(destIsBefore){
int moved = pop_front(mTargetHouseIdList[fromUFO]);
push_back(mTargetHouseIdList[destUFO], moved);
}else{
int moved = pop_back(mTargetHouseIdList[fromUFO]);
push_front(mTargetHouseIdList[destUFO], moved);
}
// 再度シミュレート
simulate(aStage);
// もう一度最悪ターン数を調べる
int worstTurn2 = 0;
for(int i=0; i<10; i++){
if(worstTurn2 < simulateResult[i]){
worstTurn2 = simulateResult[i];
}
}
// 最悪ターン数が増えてしまったら元に戻す
if(worstTurn2 > worstTurn){
mTargetHouseIdList[fromUFO] = fromTemp;
mTargetHouseIdList[destUFO] = destTemp;
}
}
// 状態を初期化
initIndices();
やっていることは、
- シミュレート
- 最悪ターンとその小UFOを調べる
- 最悪ターンを記録した小UFOの隣のどちらかの小UFOに割り当てを渡す
- もう一回シミュレート
- 最悪ターンが改善したかをチェック、改善してなかったら元に戻す
ということの繰り返しです。なお、両隣のどちらの小UFOに割り当てを渡すかは、ループ回数を記録している times という変数の偶奇で変えています。
さて、実行してみましょう。
stage | turn
0 | 114
1 | 127
2 | 97
3 | 101
4 | 125
5 | 116
6 | 108
7 | 115
8 | 123
9 | 86
10 | 129
(省略)
190 | 87
191 | 95
192 | 115
193 | 160
194 | 84
195 | 99
196 | 129
197 | 96
198 | 100
199 | 117
TotalTurn: 21091
Time: 1.721 sec
3000弱改善して、目標だった22222を切ることができました！
最後に
ここまでお付き合い頂きありがとうございました。いかがだったでしょうか。
少しずつ工夫を積み重ねてスコアをどんどん削っていく快感と、このコンテストに没頭してしまう人の気持ちがお分かりいただけたでしょうか。
プログラムも読み書きする量こそ多いものの、やってることは意外と単純で、(プログラムのプロの会社だからか)良いプログラムが提供されるので、初心者でも試行錯誤しながら取り組めると思います。ぜひこの機会に過去問を解いてみたり、来年のコンテストに参加してみたりしてはいかがでしょうか。
さて、ハルコン2017については上記で十分解説したように見えますが、これはあくまでチャレンジスコアで、上位陣はこれ以上に熾烈な戦いを繰り広げています。具体的に言うと、コンテスト終了時点での上位陣は14000を切るスコアで抜きつ抜かれつの攻防を行っていました。今回紹介した手法以上にいろいろな工夫をすることで、ここからさらに8000弱のスコアが削れるわけです。奥が深いですね。
これ以上の手法の一例として、動的計画法(Dynamic Programming)、ビームサーチ、山登り法、などがあります。気になる方は調べてみて下さい。11月21日のハルコン2017結果発表時には、上位陣のプログラムと解説が読めるようになるはずなので、それを参考にするのもいいかもしれません。
というわけで、最終的なSolverクラスと、最後に作ったプログラムによるビュアーの結果と、私nariがコンテストで最終提出したプログラムのビュアーの結果を乗せてこの記事を締めさせていただきます。何か改善できると思った点があれば、ぜひ自分の手でプログラムを書いてみてください。楽しいプロコンライフを。
明日のAdvent Calendar記事はkriwさんです。
改善4を加えた後のSolverクラス
class Solver
{
private:
/// 各UFOが次に向かう家のIDリストのインデックス。
Array<int, Parameter::UFOCount> mTargetHouseIndices;
/// 各UFOの担当している家のIDリスト
Array<int, Parameter::MaxHouseCount> mTargetHouseIdList[10];
public:
void initIndices(){
// mTargetHouseIndices を初期化するだけ
while(mTargetHouseIndices.count() < Parameter::UFOCount){
mTargetHouseIndices.add(0);
}
for(int i=0; i<mTargetHouseIndices.count(); i++){
mTargetHouseIndices[i] = 0;
if(mTargetHouseIdList[i].count() == 0){
mTargetHouseIndices[i] = TARGET_HOUSE_NONE;
}
}
}
Array<int, Parameter::UFOCount> simulateResult;
void simulate(const Stage& aStage){
// simulateResult を初期化
for(int i=0; i<simulateResult.count(); i++){
simulateResult[i] = 2000;
}
while(simulateResult.count() < Parameter::UFOCount){
simulateResult.add(2000);
}
initIndices();
// シミュレート用の ufo を作る
int ufoCount = aStage.ufos().count();
UFOs sufos;
for(int i=0; i<ufoCount; i++){
if(i < 2){
// large ufo
sufos.add(UFO(UFOType_Large, aStage.office().pos(),
(float)Parameter::LargeUFORadius, (float)Parameter::LargeUFOMaxSpeed,
Parameter::LargeUFOCapacity));
}else{
// small ufo
sufos.add(UFO(UFOType_Small, aStage.office().pos(),
(float)Parameter::SmallUFORadius, (float)Parameter::SmallUFOMaxSpeed,
Parameter::SmallUFOCapacity));
}
}
int finishedUfos = 0; // 配達が終わったUFOの数
for(int i=0; i<ufoCount; i++){
if(mTargetHouseIdList[i].count() == 0){
finishedUfos++;
simulateResult[i] = 0;
}
}
// 200ターンシミュレートする(200ターンしてシミュレートが終わらない場合は強制終了)
for(int turn = 0; turn < 200 && finishedUfos < ufoCount; turn++){
// moveItems のシミュレート
Actions actions;
moveItems(aStage, actions, sufos);
// action の正当性チェックはせず、プログラムを信用する(プログラムの簡略化のため)
for(Action a : actions){
if(a.type() == ActionType_PickUp){
auto& ufo = sufos[a.ufoIndex()];
ufo.incItem(ufo.capacity() - ufo.itemCount());
}else if(a.type() == ActionType_Pass){
auto& src = sufos[a.srcUFOIndex()];
auto& dst = sufos[a.dstUFOIndex()];
int largeUfoNum = src.itemCount();
int smallSpace = dst.capacity() - dst.itemCount();
int passNum = largeUfoNum < smallSpace ? largeUfoNum : smallSpace;
dst.incItem(passNum);
src.decItem(passNum);
}else if(a.type() == ActionType_Deliver){
auto& ufo = sufos[a.ufoIndex()];
ufo.decItem(1);
}
}
// moveUFOs のシミュレート
TargetPositions targets;
moveUFOs(aStage, targets, sufos);
for(int i=0;i<10;i++){
sufos[i].move(targets[i]);
}
for(int i=0; i<ufoCount; i++){
if(simulateResult[i] == 2000 && mTargetHouseIndices[i] == TARGET_HOUSE_NONE){
finishedUfos++;
simulateResult[i] = turn;
}
}
}
// 後始末
initIndices();
}
template <typename T, int C>
Array<T,C> copy(Array<T,C> &a){
Array<T,C> ret;
for(T x : a){
ret.add(x);
}
return ret;
}
template <typename T, int C>
void push_back(Array<T,C> &a, T v){
a.add(v);
}
template <typename T, int C>
void push_front(Array<T,C> &a, T v){
a.add(0);
for(int i=a.count()-2;i>=0;i--){
a[i+1] = a[i];
}
a[0] = v;
}
template <typename T, int C>
T pop_back(Array<T,C> &a){
Array<T,C> temp;
for(T x : a){
temp.add(x);
}
a.clear();
for(int i=0;i<temp.count()-1;i++){
a.add(temp[i]);
}
return temp[temp.count()-1];
}
template <typename T, int C>
T pop_front(Array<T,C> &a){
Array<T,C> temp;
for(T x : a){
temp.add(x);
}
a.clear();
for(int i=1;i<temp.count();i++){
a.add(temp[i]);
}
return temp[0];
}
void init(const Stage& aStage)
{
int ufoCount = aStage.ufos().count();
mTargetHouseIndices.clear();
for(int i=0; i<ufoCount; i++){
mTargetHouseIdList[i].clear();
}
// 割当ているかいないかの配列
// true なら割り当てていない
int houseCount = aStage.houses().count();
Array<bool, Parameter::MaxHouseCount> available;
for(int i=0; i<houseCount; i++){
available.add(true);
}
// 大UFOを「街」に飛ばす
for(int largeUfo=0; largeUfo<2; largeUfo++){
// 街の中心となる家を探す
// 「半径100にある家の数」が最大となるような家を街の中心とする
int centerHouse = -1;
int bestHouseCount = -1;
for(int i=0; i<houseCount; i++){
if(!available[i])continue;
Vector2 hpos = aStage.houses()[i].pos();
int temp = 0;
for(int j=0; j<houseCount; j++){
if(!available[j])continue;
if(hpos.dist(aStage.houses()[j].pos()) <= 100.0f){
temp++;
}
}
if(bestHouseCount < temp){
centerHouse = i;
bestHouseCount = temp;
}
}
// 街の中心を大UFOに割り当てる
mTargetHouseIndices.add(0);
mTargetHouseIdList[largeUfo].add(centerHouse);
available[centerHouse] = false;
// 近いところを9個割り当てる
Vector2 currentPos = aStage.houses()[centerHouse].pos();
for(int _=0; _<9; _++){
int nextHouse = -1;
float bestDistance = 252521.0f;
for(int i=0; i<houseCount; i++){
if(!available[i])continue;
float dist = currentPos.dist(aStage.houses()[i].pos());
if(dist < bestDistance){
nextHouse = i;
bestDistance = dist;
}
}
mTargetHouseIdList[largeUfo].add(nextHouse);
available[nextHouse] = false;
currentPos = aStage.houses()[nextHouse].pos();
}
}
// 家を、農場中心の角度でソートする
Array<int, Parameter::MaxHouseCount> houseIds;
for(int i=0; i<houseCount; i++){
if(available[i])houseIds.add(i);
}
Vector2 basePoint = Vector2(100.0f, 0.0f);
// #include <algorithm>
std::sort(houseIds.begin(), houseIds.end(), [&](int a, int b){
Vector2 to_a = aStage.houses()[a].pos() - aStage.office().pos();
Vector2 to_b = aStage.houses()[b].pos() - aStage.office().pos();
return basePoint.rotSign(to_a) < basePoint.rotSign(to_b);
});
int head = 0;
int houseNum = houseIds.count();
// 残りの家を小UFOに割り当てる
for (int smallUfo = 0; smallUfo < ufoCount-2; smallUfo++) {
int num = houseNum / (ufoCount-2);
if(smallUfo < houseNum % (ufoCount-2)){
num++;
}
mTargetHouseIndices.add(0);
// num個の家を割り振る
for(int i=0; i<num; i++){
mTargetHouseIdList[smallUfo+2].add(houseIds[head]);
head++;
}
}
// 小UFOの割り当てを探索する
for(int times=0; times<100; times++){
// シミュレートする
simulate(aStage);
// 最悪ターン数を調べる
int worstTurn = 0;
int worstId = 0;
for(int i=0; i<10; i++){
if(worstTurn < simulateResult[i]){
worstTurn = simulateResult[i];
worstId = i;
}
}
// ボトルネックが大UFOだったらどうしようもない
if(worstId < 2){
break;
}
// あるUFOから隣のUFOに割り当てを渡す
// 割り当てを減らすUFO
int fromUFO = worstId;
// 減らせる割り当てが無かったらキャンセル
if(mTargetHouseIdList[fromUFO].count() == 0){
continue;
}
// 前後どちらのUFOに渡すか
bool destIsBefore = times%2==0 ? true : false;
// 割り当てを増やすUFO
int destUFO = fromUFO + (destIsBefore ? -1 : 1);
if(destUFO == 1){
destUFO = 9;
}else if(destUFO == 10){
destUFO = 2;
}
// 変化前の割り当てを覚えておく
auto fromTemp = copy(mTargetHouseIdList[fromUFO]);
auto destTemp = copy(mTargetHouseIdList[destUFO]);
// 割り当てをずらす
if(destIsBefore){
int moved = pop_front(mTargetHouseIdList[fromUFO]);
push_back(mTargetHouseIdList[destUFO], moved);
}else{
int moved = pop_back(mTargetHouseIdList[fromUFO]);
push_front(mTargetHouseIdList[destUFO], moved);
}
// 再度シミュレート
simulate(aStage);
// もう一度最悪ターン数を調べる
int worstTurn2 = 0;
for(int i=0; i<10; i++){
if(worstTurn2 < simulateResult[i]){
worstTurn2 = simulateResult[i];
}
}
// 最悪ターン数が増えてしまったら元に戻す
if(worstTurn2 > worstTurn){
mTargetHouseIdList[fromUFO] = fromTemp;
mTargetHouseIdList[destUFO] = destTemp;
}
}
initIndices();
}
void moveItems(const Stage& aStage, Actions& aActions, const UFOs& ufos)
{
int ufoCount = ufos.count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = ufos[ufoIndex];
// 農場の上にいたら箱を積み込む
if (Util::IsIntersect(ufo, aStage.office())) {
aActions.add(Action::PickUp(ufoIndex));
}
// 大UFOから小UFOへ箱を受け渡す
if(ufoIndex >= 2 && ufo.itemCount() == 0){
for(int largeUFO=0; largeUFO<2; largeUFO++){
if(Util::IsIntersect(ufo, ufos[largeUFO])){
aActions.add(Action::Pass(largeUFO, ufoIndex));
}
}
}
// 担当の家の上にいたら配達する
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex == TARGET_HOUSE_NONE) {
continue;
}
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
if (ufo.itemCount() == 0 || !Util::IsIntersect(ufo, aStage.houses()[houseIndex])) {
continue;
}
aActions.add(Action::Deliver(ufoIndex, houseIndex));
// 目標の家を更新
mTargetHouseIndices[ufoIndex]++;
if (mTargetHouseIndices[ufoIndex] >= mTargetHouseIdList[ufoIndex].count()) {
// 担当の家はすべて配達終了
mTargetHouseIndices[ufoIndex] = TARGET_HOUSE_NONE;
}
}
}
void moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions, const UFOs &ufos)
{
int ufoCount = ufos.count();
for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
const auto& ufo = ufos[ufoIndex];
if (ufo.itemCount() == 0) {
// 箱がなければ農場に向かう
Vector2 target = aStage.office().pos();
// 小UFOなら近い大UFOも候補にする
if(ufoIndex >= 2){
for(int largeUFO=0; largeUFO<2; largeUFO++){
Vector2 lpos = ufos[largeUFO].pos();
if(ufo.pos().dist(lpos) < ufo.pos().dist(target)){
target = lpos;
}
}
}
aTargetPositions.add(target);
} else {
// 箱を積んでいれば担当の家に向かう
int houseListIndex = mTargetHouseIndices[ufoIndex];
if (houseListIndex != TARGET_HOUSE_NONE) {
int houseIndex = mTargetHouseIdList[ufoIndex][houseListIndex];
aTargetPositions.add(aStage.houses()[houseIndex].pos());
} else {
aTargetPositions.add(ufo.pos());
}
}
}
}
};
改善4を加えたSolverのビュアー
nariのコンテストベストスコアのSolverのビュアー
