AHC019参加記

uetaです。
よろしくお願いいたします。

今回はAHC019に参加しましたのでその時に考えたことを書いていきたいと思います。

自分はヒューリスティックコンテストの経験が少なく、鉄則本で一通りできるようになった程度です。
これまでは大体貪欲でやってきました。

AHC019

このコンテストは
AtCoder社で行われている
Atcoder heuristic Contest 通称AHCの19回目のコンテストです

MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019）

今回の結果

4回目に真面目に取り組んだ長期AHC

50ケース　95位
システムテスト後順位93位
でした(少し上振れ)。

初二桁達成しました。満足です。

問題について

二組のシルエットが入力される。これを成り立たせる立体パズルを作成せよ。少数の大きなブロックのみからなるセットが望ましい。

得点を小さくすることを目標にしたコンテストです。

(問題より引用)

始め、問題は単純明快だが進め方がわからないと思った問題でした。

初めに考えたこと

最初はビームサーチとchokudaiサーチあたりで徐々に高得点が得られるアルゴリズムが最も有効かなと考えていました。
しかし、ブロックが一致するかどうかを判定するのが難しいという点があり、どのようにするのがいいのかわかりませんでした。

そのため、一つ一つ得点を下げてみようかなと思いました。

第一,二回提出(3/18-19)

まずはpythonのサンプルコードを提出。
これを c++に書き換えました。

無事全く同一の得点であったためうまくいっていることが確認できました。

第3回提出(3/19)

無駄なブロックがたくさんあることがわかります。
シルエットで重なってしまう、いらないブロックが消せそうだなと思いました。
よって、消せるブロックを消すアルゴリズムを考えました。

上図のブロックすべてをTrueにする。
それぞれの番号を配列に入れてランダムにシャッフルする
前から一つずつ消せるブロックをfalseにする
最後に残すブロックに対して番号を振る

これにより得点を1/4ほどにすることができました。

第4回提出まで(-3/29)

ここから、暗黒期に入ります。
理由の一つは日常生活が忙しくなり取り組めなくなったことです。
もう一つはアルゴリズムを全く思い浮かばず、悩んでいたからです。
寝る前や時間があるときにずっとアルゴリズムを考えていたが全く思い浮かびませんでした。

例えば、
特徴的な共通点を探してそこをブロックとする。（うーん、プログラムが思いつかない）
ビームサーチする（ビームサーチの得点算出は何にすればいい？初期値は100個ぐらい？固定化されそう...、パズルの一致判定は？）
焼きなまし？（なんか問題的にあってる？どうやけばいいんだ）

色々と堂々巡りしていました。
そんなことを考えているうちに3/28日でした。
なら、ひとまず手を動かすのが正解でした....

第5回提出(-3/30未明)

ひとまず、近くの点をくっつけようと考えた。

ブロックが置くことが可能な番号を配列に入れてランダムにシャッフル
一つずつ「必要なブロックの隣が必要なブロック」であれば番号に振る
一つずつ「必要なブロックの隣がブロックを成形可能」であれば続きから番号に振る
二つのシルエットのうち、番号が小さいほうに合わせて消す
残りの必須ブロックを1で埋める

無駄に複雑なものにしてしまいました。。。
(この時気付かなかったのですが、なぜか横方向しかブロックが接続されていないんです...あーやらかし）

これを提出すると当時200位程度になることができました。

第6,7回提出（3/30夕方）

これを出す前、chokudai サーチについて調べていました。
しかし、どれを調べても実装例が出てこない。
うーんどうしようか？
「おっ、これは！！！」

thunderさん神!!!!!

よく読むとGithubにつながっていてそこを引用しました。

ここで感謝申し上げます。
ありがとうございました。

実際にはサーチ系のアルゴリズムを使うのに至りませんでしたが、その中での「State」を利用したことで簡潔に書くことができました。
凄いこれ...

何をやったかというと

これの試行回数を多くして、最も点数が低いものを採用すればいいのではないかと考えました。
6回目は終了時間を間違えていたため、7回目で修正しました。

第8-12回提出（3/30夜-3/31夕方）

次に1のブロックが邪魔だなと思いました。
では1のブロックをどうにかして2のブロックにくっつければいいのではないかと考えました。
なぜなら、3のブロックは形が2通りしかないからです。
これなら、二つのmapを管理すればいいと考えました。

くっつけることが可能ならくっつけるようにして、1のブロックを消します。

あまり点が上がりませんでした。

第13-14回提出（4/1未明）

ビジュアライザを見たとき、ブロックの上限が3個だと限界がありそうだなと思いました。（遅い気がする...)

ある一点と一点が同一にみなせるとこれでできる上限まで上下左右前後を接続し続ける。
その後、これまで行っていたアルゴリズムをくっつけました。
これの試行回数を多くして、最も点数が低いものを採用しました。

第15-回（4/2終了直前まで）

ビジュアライザを見ると、各ブロックが方向通りで一致しているなと思いました。
これだと、うまくはまらないときがあるので、小さいブロックが多くなってしまうなと思いました。
なので、最後は回転を実装しました。

図の回転はいろいろ考えたが、組み合わせや全探索でうまくいかなそうなので手実装しました。

図の回転

enum class dice
{
    x,y,z,x_,y_,z_
};
 
vector<vector<dice>> DICES{
    {dice::x, dice::y, dice::z},
    {dice::y, dice::x_, dice::z},
    {dice::x_, dice::y_, dice::z},
    {dice::y_, dice::x, dice::z},
 
    {dice::y, dice::x, dice::z_},
    {dice::x, dice::y_, dice::z_},
    {dice::y_, dice::x_, dice::z_},
    {dice::x_, dice::y, dice::z_},
 
    {dice::x, dice::z_, dice::y},
    {dice::z_, dice::x_, dice::y},
    {dice::x_, dice::z, dice::y},
    {dice::z, dice::x, dice::y},
 
    {dice::x, dice::z, dice::y_},
    {dice::z, dice::x_, dice::y_},
    {dice::x_, dice::z_, dice::y_},
    {dice::z_, dice::x, dice::y_},
 
    {dice::y, dice::z, dice::x},
    {dice::z, dice::y_, dice::x},
    {dice::y_, dice::z_, dice::x},
    {dice::z_, dice::y, dice::x},
 
    {dice::z, dice::y, dice::x_},
    {dice::y, dice::z_, dice::x_},
    {dice::z_, dice::y_, dice::x_},
    {dice::y_, dice::z, dice::x_},
};

回転の計算結果は以下のようにして手に入れるようにしました。

縦横

tuple<int, int, int> get_rotation(int dx, int dy, int dz)
{
    vector<int> v{dx, dy, dz};
    tuple<int, int, int> r{0, 0, 0};
    for (int i = 0; i < 3; i++)
    {
        switch (rotation[i])
        {
        case dice::x:
            get<0>(r) = v[i];
            break;
        case dice::y:
            get<1>(r) = v[i];
            break;
        case dice::z:
            get<2>(r) = v[i];
            break;
        case dice::x_:
            get<0>(r) = -v[i];
            break;
        case dice::y_:
            get<1>(r) = -v[i];
            break;
        case dice::z_:
            get<2>(r) = -v[i];
            break;
        default:
            cout << "error" << endl;
            break;
        }
    }
    return r;
}

このアルゴリズムを6個以上だとブロックの決定を繰り返す
必要なブロックであれば2個以上で繰り返す
この後にこれまでのアルゴリズムをつなげる

これの試行回数を多くして、最も点数が低いものを採用しました。

という仕組みにすると点が高くなったため、そのように実装しました。
計算能力と時間が足りなかったためパラメータが設定されていません。
パラメータを設定できるとよかったです。

後、2個くっつけるものが横方向だけであると気づいたため、縦方向も実装し直しました。

これが最終提出です。
しかし、このコードでは乱数が重要すぎて点がかなり上下します。

0000.txtを複数回、回した結果

#ローカル
Score = 1320634921
Score = 1031746032
Score = 919047619
Score = 922222222
#コードテスト
Score = 669444444
Score = 566666667
Score = 490079365
Score = 811111111

なので、運がよかった結果かなと思います。（2000ケースを回したら収束してるのかな？）

できればよかったこと

ビームサーチやchokudaiサーチをと入れてみたかったです。
乱択だといい結果が出るときと出ないときの差が大きいので問題かなと思います。

最後に

ここまで読んでいただきありがとうございました。