【ABC440】AtCoder Beginner Contest 440C 自分用解説

ABC440C - Striped Horse

問題リンク : https://atcoder.jp/contests/abc440/tasks/abc440_c
解答リンク : https://atcoder.jp/contests/abc440/editorial/15007

解法メモ

自分は黒く塗る区間を全て管理する実装でACした。
一方で、公式解説のような区間を円環にまとめる発想がなかったため、自分の中でどうやってそれを思いつくか整理した。

結論、とりあえずmodが出てきたら、modが等しいものの和をとってしまうのが大事。

私が最初に考えた解法

まず、私が頭の中で考えていた解法を数式に落とし込む.

この実装の提出リンクはこちら : https://atcoder.jp/contests/abc440/submissions/72459670

黒く塗られる条件は次の通り：

$$(i + x) \bmod (2W) < W$$

この式を整理すると、上記を満たす$i$の範囲はある$k \in \mathbb{Z}$を用いて以下と書ける。

$$\begin{cases} 2 k W - x \le i < (2k + 1) W - x \\ 1 \le i \le N \end{cases}$$

これより, $1 \le i \le N$でない$i$に対し$C_i = 0$とおけば, $x$を与えたときのコスト$S(x)$は以下となる。

$$S(x) = \sum_{k} \sum_{t=0}^{W-1} C_{\,2Wk - x + t}$$

私は、$x$を$1$増やしたときに、内側の和の値を全て更新するプログラムを作成していた。

公式解説の思いつき方

有限和なので、順序を交換してよい：

$$S(x) = \sum_{t=0}^{W-1} \sum_{k} C_{\,2Wk - x + t}$$

ここで 内側の $\sum_k$ に注目する。これは

$$i \bmod 2 W = (-x + t) \bmod 2W$$

を満たす $i$ 全体に対する$C_i$の和である。よって、次を定義する。

$$A_r = \sum_{\substack{1 \le i \le N \\ i \equiv r \, (\mathrm{mod}\ 2W)}} C_i$$

以上より、

$$S(x) = \sum_{t=0}^{W-1} A_{\, (-x+t)\bmod 2W}$$

これより、先に$A_r$を計算しておけば、複数の黒塗りする区間を考えずに実装できる。
提出リンクはこちら : https://atcoder.jp/contests/abc440/submissions/72471916

コメント

自分は数学科出身の人間のため、こんな感じで数式で整理できると嬉しい。
「困ったときは立式」という方針で、Atcoderも解けるようになったら最高。