JOI2022本選参加記(?)

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 が出ました。

Submission #29236844 - 第7回日本情報オリンピック 本選(過去問)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

追記:最速記録は square1001 さんの AtCoder 13 ms です

タイトルとURLをコピーしました