メモ書きをそのまま貼り付けているので、日本語がヤバいところがあるかもしれません。

8/9

21:06 osu!をやっていたらいつの間にか始まっていました。問題を見ます。とりあえずよくわからない

AHCスタート時に一番多いツイート「分からない」
— 🇿 🅰️ 🇹 (@zat_is_a_cat) 2022年8月10日

のでAHC013というディレクトリを作ってsampleプログラムをダウンロード。提出したらACが出ました。初AC（26047点）。

main.cppというファイルを作って入出力を書きながら問題分を読みます。ライブラリからいろいろ持ってきてコピペして準備が整いました。

入力を書いて、「移動」と「接続」の意味がわかりました。まだ全然どういう方法で解けばいいのかわからないです…

とりあえずgrid[i][j]みたいなのをgrid[i * n + j]に直す関数を書くとQOLが上がる気がします。それを書きます。サンプルのプログラムはstd::map<std::pair<int, int>, std::pair<int, int>>みたいなのでUnionFindを実装してるみたいですが、遅そうなので1から書き直します。

sampleのC++コードを自分の言葉で写し終わりました。でも動かない… 時計を見るといつの間にか日付が変わりそうになっています。

バグが治らないので明日また原因を探ることにします。おやすみなさい。

8/10

今日はバグを直して、簡単な愚直解を提出したいです。

バグが治りました！何か簡単にスコアが上がる方法はないかな〜

sampleのrand()を自作のrandintに変えて、2900msまで良いスコアを取り続けるものを書きました。

int main()
{
    using namespace m9;

    // input
    INT(N, K);
    assert(15 <= N and N <= 48);
    assert(2 <= K and K <= 5);

    VVC(Grid, N, N);

    auto[bestResult, bestScore] = AHC013::Solver(N, K, Grid).solve();
    while(timer.get_time() <= 2900)
    {
        AHC013::Solver solver(N, K, Grid);
        auto[curR, curS] = solver.solve();
        if(chmax(bestScore, curS))
        {
            bestResult = curR;
        }
    }
    AHC013::outputCase(bestResult);
    dbg(bestScore);
}

そんなに伸びないだろうな〜と思っていたらかなり上がりました。50184点で38位です。この方針を続けるわけにもいかないので、いい感じの方針を立てないとです。今、connectはうまく動いているけどmoveはランダムな動きで全然最適な動きになっていないので、moveを改善する方向で方針を立てます。

あと、テストケースを自動で試すスクリプトを書かないとです。AHC011のときに書いたものが残っていると思います（たぶん…）。

コンピューターをいくつかピボットとして指定して、他のコンピューターは同じ種類のピボットに集まる、みたいなことをするといいのかな？実装してみます。

8/11

ピボットとx座標が同じかy座標が同じところまで動かす、という作業を何回かするというコードを書きました。提出してみます。（多分あまり点数は上がらないです）→下がりました…（42440点）

+αでランダムで一箇所動かして点数が上がるものを採用します。REに悩まされましたがやっと提出ができそう。（エラーコード139が出たときには配列外参照を疑うといいです…）

atcoder.jp

→84599点でした！100000点行きたいな〜

手元でランダムテストケースを回せるようにしました。100ケースぐらいが時間的に良いかな？（3000ms * 100ケースで300秒 = 5分）

8/12

ランダムで動かすところを決定的にしました。100087点！10万点を超えて嬉しいです。 connectする部分の実装をコンピューターの種類ごとに接続するようにしました（ex: com1すべて → com2すべて → ...。 132095点！どんどん増えていって嬉しい〜多出発山登り法の出発点が2個になっていたので、4個にします。142587点！

明日は15万点行きたいです。おやすみなさい〜

8/13

特に何もできませんでした… ABC264に出ました！久々に5完できてうれしいです！！

8/14

分からない〜が続きます。2000byteぐらい書いて、改善がなし。

ちょっと変更して提出。145760点。

8/15

だめでした

8/16

ランダムより決定的な方法を考えて実装してみたのですが、時間が足りませんでした（リアルな時間+実行時間）知ったこと：ランダムに動かすところを決める方法は試行回数が多くなるからか意外と点数が高い

まとめ

うれしかったところ

・だいたい15万点ぐらいまで到達して実は結構嬉しいです・最初にコードを書くときに、後のことまで考えてコードがかけました

かなしかったところ

・最後の4日間は何もできませんでした… ・最後の方になるとどの関数がなにをするやつなのかわからなくなってきました（ただ今回はコードを結構きれいにかけたのでこれまでよりは読みやすかったです）・青パフォを出したかったのですが、出せませんでした…

記

まぐげんがーです。

AHC013 参加記

8/9