ABC 331, PAST 17 / 累積和

競技プログラミング

Keyball 44 で寿司打に取り組み、 15,000 円以上のスコアを安定して出せるようになった。

第 17 回アルゴリズム実技検定を受験した。 11 / 15 問を解き、中級認定だった。

ABC 331 に参加した。 5 完 (A ~ E) だった。

A 問題では繰り上がりが 1 桁の場合、 2 桁の場合、無い場合で分岐した。

B 問題は全探索で解いた。 \(N \le 100\) と小さく枝刈りは必要無かった。

C 問題では制約 \(A_i \le 10^6\) を突いてセグメント木を使ってしまった。 \(A_i \le 10^9\) のように変域が大きな場合も、座標圧縮してセグメント木を使ったと思う。

累積和と比べてセグメント木を簡単に感じる理由は、 1. 可変配列を使用するため構築が用意、2. 添字アクセスが素直の 2 点にあった。

改めて座標圧縮と累積和で解いてみた。 1 次元累積和にアクセスするための +! 演算子を追加したため、添字アクセスも単純になった……かも。

D 問題では 2 次元累積和を書いた。自作ライブラリに 2 次元累積和を計算する csum2D と、 2 次元累積和の取得演算子 @+! を追加した。

デバッグ時には、グリッドを stderr に表示するユーティリティが役立った。

Listing 1: 入力のグリッドはこういうもの

001
110
010

Listing 2: デバッグ用関数呼び出し

  let !csum = csum2D $ mapIV (bool 0 (1 :: Int)) gr
  let !_ = dbgGridN 3 csum

Listing 3: 2 次元累積和のデバッグ表示

  0   0   0   0
  0   0   0   1
  0   1   2   3
  0   1   3   4

E 問題では主菜を全探索し、副菜は降順ソートして有効な組み合わせが出るまで線型探索した。たかだか L 回しか無効な組み合わせは現れないため、最大 \(N + K\) 回の探索で済む。いわゆる『鳩の巣原理』だった。

F 問題では回文の判定にローリングハッシュを使う過去問を思い出した。ローリングハッシュの実装を見る限りセグメント木に載りそうで良問の雰囲気だったが、もう実装する気力が無かった。

最近 ST モナド関連でコンパイルエラーが取れず青ざめた。この辺をすべてカバーするのは難しい。大して書けることは無いと諦めの気持ちになってきた。

dired に vidir 的な一括リネーム機能があることを知った。大活躍している。