AHC015参加記

490位

問題のリンク

考えたこと

~1:37 (28M)

ローカル版のツールのlib.rsを見ながらキャンディーの移動とスコアを計算する関数をD言語に移植。 キャンディーを受け取る毎に4方向へ傾けた際に1番スコアが高い方向に傾ける。

~2:59 (53M)

上記のコードを乱数を用いて変更を加えたが、得点が上がらなかった。 ビジュアライザを手で操作していると、1つの味を箱の1辺に集めていけば得点が上がりそうだとわかった。 とりあえず、最初に受け取る味のキャンディーの場合下に、それ以外のキャンディーの場合は右に傾ける解法で提出。 得点が53Mまで上がった。

~3:07 (61M)

下に傾けるキャンディーの味を最初に受け取る味から1番数が多い味に変更することで61Mまで上がった。

~4:00

1番数の多い味のキャンディーの場合下に傾けていき、下にキャンディーが溜まった場合に上以外の3方向で1番スコアが高くなる方向に傾けていく方針で実装。 しかし、思ったように得点が上がらない。 最初に提出していたコード内のキャンディーを入れる位置を求める関数が正しい位置を返していないことがわかった。 このミスに気づくのに30分以上費やしてしまった。

Coord findCoordToPut(long[N][] mat, long num) {
    Coord ret;
    long cnt;

    foreach (i; 0 .. N) {
        foreach (j; 0 .. N) {
            if (mat[i][j] == 0) ++cnt;

            if (cnt >= num) ret.x = i, ret.y = j;
        }
    }

    return ret;
}

コンテスト終了1分前に滑り込みで提出できたが、得点が41Mと思うように上がらず終了。

感想

AHCの参加は4回目だが、4時間の短期マラソンは初めてのためとても疲れた。

1番数の多いキャンディーの場合下に傾けるという解法で得点が上がった後、他の方向についても試してみるべきであった。