2022/2/13 9:00 – 13:00
成績
問題番号 / 問題名 / 得点 / 最終得点時刻(開始-origin) / (提出回数)
$$\begin{aligned} \text{問題1} && \text{インターカステラー} && 100/100 && 00:05:47 && \color{red}{(1)} \newline \text{問題2} && \text{自習} && 100/100 && 00:17:15 && \color{red}{(2)} \newline \text{問題3} && \text{選挙で勝とう} && 77/100 && 02:46:34 && \color{red}{(9)} \newline \text{問題4} && \text{鉄道旅行 2} && 100/100 && 03:33:31 && \color{red}{(2)} \newline \text{問題5} && \text{砂の城 2} && 19/100 && 01:58:53 && \color{red}{(3)} \end{aligned}$$
感想
(成績を見れば)例年通りの雰囲気
ギャグ
問題 5 を解説 AC しました。
解説で 81 通り場合分け(正確には、 81 個のテーブルを作る)と言われたので面白そうでした。
解説
理解/実装のおおまかな難点は $2$ 箇所、テーブルを作るところとテーブルを参照するところです。
テーブルの設計
$81$ 通りの場合分けは、上下左右のゆとり各 $3$ 通り( $0$ マス、 $1$ マス、 $2$ マス以上)で $3\times 3 \times 3 \times 3 = 81$ により生じます。向きによって意味は変わらないので、向きを外側のループに出すと場合分けの作業が 1/4 になると考えられます。これに従って、配列の添え字は
$$A[l][t][r][b][y][x]$$
のようにします。( $l$ は左、 $t$ は上、 $r$ は右、 $b$ は下です)
テーブルを作るところ
周囲 $4$ 方向のマスを見て $1$ つ選び、その向きを向いて $1$ マス進み、その位置で周囲 $4$ 方向を見る、という処理を各マスでしなければなりません。
$4$ 方向場合分けするのが嫌なので、向きに従って座標軸を動かしてしまってから $2$ 段階目を処理します。入力の盤面が $4$ 方向について欲しくなるので作っておきます。
テーブルを参照するところ
解説にあるように、累積和が必要な部分は限られます。具体的には、上下両方向に $2$ マス以上のゆとりがある場合のみです。
クエリの添え字は各軸独立に計算できます。軸 $1$ 個分を計算して返す関数を作って $2$ 回呼び、得られたクエリを $2$ 重ループで処理します。
累積和が絡むのは各軸 $1$ 回なので、その分は場合分けします。
競技以外
ダーツを高速化する遊びをしました。 CMS で 18 ms が出ました。
追記:最速記録は square1001 さんの AtCoder 13 ms です