ABC228 (トヨタシステムズプログラミングコンテスト2021 AtCoder Beginner Contest 228) に参加して ABCDE5完 265位でした．

問題

問題へのリンク

A - On and Off

最近，A問題が難しいです． S < T, S < X のときには T, X に24を加えておいて比較すれば良いです．

B - Takahashi’s Secret

問題文を斜め読みして，DFS を書き始めてしまいました． まあとくに問題無いですけれども．

C - Final Day

4日目に満点を取ったときに， 3日目までの合計点の第K位に追いつけるかどうかを判定すれば良いです．

D - Linear Probing

vector<ll> A(N) の他に，set<ll> unused を用意します． unused には，A[i] = -1 である i たちを格納しておきます． 初期状態では，unused は，[0..N-1] です．

タイプ2 のクエリでは，単に A[x mod N] を出力します．

タイプ1 のクエリでは，h = x mod N として， unused.lower_bound(h) を実行して， [h..N-1] に空いている場所があるかどうか調べ， あればそこに x を代入します． 無ければ unused.lower_bound(0) を実行して， 返ってきた場所に x を代入します． その後，unused を更新します．

E - Integer Sequence Fair

$p = 998244353$ とします． $M^{K^N}$ を mod $p$ で求めればよいわけです．

おそらく，$M \equiv 0$ (mod $p$) をコーナーケースだろうと想定している のだろう，と思って，いの一番に

if (M % p == 0) {
  cout << 0 << endl;
}

と書きました．書いたのに，return 0; を書き忘れて1ペナルティ． 馬鹿みたい．

さて，$M \not\equiv 0$ (mod $p$) のときには，Fermat の小定理で $M^{p-1} \equiv 1$ (mod $p$) ですから， $N^K \equiv s$ (mod $p-1$) なる $s$ を求めれば， $M^s$ が求める答です．どちらも，普通の，$O(\log n)$ で $a^n$ を求めるアルゴリズムを使います．

F - Stamp Game

10分くらい足りなくて，デバッグしきれませんでした． Eで return 0; を忘れなければ解けたかなあ．微妙かなあ．

まず，$h_2 := \min(h_1, h_2)$, $w_2 := \min(w_1, w_2)$ としてしまっても良いです．

次に，

  • $B[i][j] :=$ 左上隅を $(i,j)$ とする黒いスタンプが覆う長方形に 書かれている数値の和
  • $C[i][j] :=$ 左上隅を $(i,j)$ とする白いスタンプが覆う長方形に 書かれている数値の和

とします．これらは，2次元累積和を用いて，全体として $O(HW)$ で求められます．

高橋君が左上隅として $(i,j)$ を選んだ時のスコアは， $ s[i][j] := B[i][j] - \max \{C[i + di][j + dj] \mid di \in [0, h_2 - h_1], dj \in [0, w_2 - w_1] \} $ です．この $s[i][j]$ を，順に計算していきます．

まず，priority queue を $W$ 個 (正確には $W - w_2 + 1$ 個かな) 用意して， $pqC[j]$ には，$i = 0, \ldots, h_1 - h_2$ について， $(C[i][j], j)$ を挿入しておきます．

次に，もうひとつ priority queue $pqR$ を用意し， $pqC[0]$ から $pqC[w1 - w2]$ までから最大値を得て，$pqR$ に 挿入します．$pqR$ から最大値を得て，$s[0][0]$ が決定できます．

この後，横に動いていく時には，あらたに適当な $j$ について， $pqC[j]$ の最大値を $pqR$ に挿入します．また，$pqR$ から最大値を 得る時には，ペアになっている $j$ の値を見て，もう無効になっていれば そのペアを pop して，その後の最大値を得ます．

縦に動いていく時も同様に $pqC$ たちを管理します．

計算量は，全体として $O(HW(\log H + \log W))$ だと思います．

翌日後記

これは，スライド最大値を中途半端に覚えていたんですね． priority queue ではなくて，dequeue を使えばよい． 挿入する時に，今挿入しようとするものよりも小さな値が見えている間は， それを捨てるようにすれば良いのでした．取り出す方は同じです． 計算量は $O(HW)$ になります．