AtCoder Beginner Contest 156 F - Modularness

問題: F - Modularness

公式解説: 解説 pdf

問題概要

長さ $k$ の数列 $d_0, d_1, \dots, d_{k- 1} $ について，次のクエリを $q$ 回処理せよ。

3つの整数 $ n, x, m $ が与えられる。長さ $n$ の数列 $a_0, a_1, \dots, d_{n- 1}$ を，

$a_0 = x$
$a_j = a_{j - 1} + d_{(j - 1) \mathrm{mod} k}$ ($j \neq 0$)

と定める。このとき $(a_j \mathrm{mod} m) \lt (a_{j+1} \mathrm{mod} m)$ であるような $j$ の数を出力する。

解法概要

あらかじめ $x$ や $d_i$ を $m$ で割った余りに置き換えておいても解は変わらないので，置き換えておく。

すると，$(a_j \mathrm{mod} m) \lt (a_{j+1} \mathrm{mod} m)$ を満たさない場合というのは，次のような場合になる。

$(a_j \mathrm{mod} m) = (a_{j+1} \mathrm{mod} m)$ の場合
$(a_j \mathrm{mod} m) \gt (a_{j+1} \mathrm{mod} m)$ の場合

前者は $d_{(j - 1) \mathrm{mod} k}$ を足しても $ m $ で割った余りが変わらないということなので，$d_{(j - 1) \mathrm{mod} k}$ を $ m $ で割った余りが 0 のときがここに当てはまる。

後者については $d_{(j - 1) \mathrm{mod} k}$ を足して値が減ってしまうということは，一度 $ m $ で割った余りが $ m - 1 $ を超えて $0$ に戻った (または $0$ に戻ってさらに足された) ということになる。したがって，$\lfloor \frac{a_j}{m} \rfloor \lt \lfloor \frac{a_{j+1}}{m} \rfloor $ のときがここに当てはまる。さらに，最初に述べた $ m $ で割った余りを置き換える処理を前提とすると，$\lfloor \frac{a_j}{m} \rfloor +1 = \lfloor \frac{a_{j+1}}{m} \rfloor $ が成り立つ ($d_i \gt m $ の場合，隣同士で $ m $ で割った商が $2$ 以上違いうる)。このとき，$x$ もあらかじめ $ m $ で割った余りに置き換えておけば，$(a_j \mathrm{mod} m) \gt (a_{j+1} \mathrm{mod} m)$ となる回数は $\lfloor \frac{a_{n - 1} - x}{m} \rfloor$ 回といえる。

ここまでで，全体の隣接ペアの数 $ n - 1 $ から $(a_j \mathrm{mod} m) \lt (a_{j+1} \mathrm{mod} m)$ を満たさない場合を引けば良いことがわかる。

そのためには $a_{n - 1}$ を求める必要があるが，$n$ が非常に大きいので，各 $d_i$ がそれぞれ何回足されるかを計算して $O(k)$ で求めなければならない。

これは例えば，

$$ \begin{aligned} f(a, b, c) = &\lfloor \frac{a}{b} \rfloor (c \gt (a \mathrm{mod} b)) \\ &\lceil \frac{a}{b} \rceil(c \le (a \mathrm{mod} b)) \end{aligned} $$

という定義で

$$ \sum_{i=1}^{b} f(a, b, i) = n $$

という性質を持つループ (ループ変数は上記の $i$) を使って数えられる (何か名前がついていたりしますか？ついていたら教えてください) 。これは $\lfloor \frac{a - i + b}{b} \rfloor$ を計算すればよい。ソースコードでは 0-indexed のため $i$ に $1$ を足していることに注意。

ソースコード

#include <iostream>
#include <vector>

using namespace std;

using ll =  long long;

constexpr int K_MAX = 5000;

int k;
vector<ll> d(K_MAX);

void solve() {
    ll n, x, m;
    cin >> n >> x >> m;

    vector<ll> dd(d);
    for(int i=0;i<k;++i) {
        dd[i] %= m;
    }

    ll dd_cnt, x_sum = x % m, zero = 0;
    for(int i=0;i<k;++i) {
        dd_cnt = (n-1 - (i+1) + k) / k;
        if(dd[i]) {
            x_sum += dd[i] * dd_cnt;
        } else {
            zero += dd_cnt;
        }
    }

    cout << n - 1 - x_sum/m - zero << endl;
}

int main() {
    int q;
    cin >> k >> q;
    for(int i=0;i<k;++i) cin >> d[i];
    while(q--) {
        solve();
    }
}

所感

想定解の頭の良さに感動してブログに残しておきたくなった問題。