yukicoder contest 367 C
解き方
※ この問題は中国剰余定理を用いて解く教育的な問題だが、ここに書く解き方では中国剰余定理を使わない
非負整数$ nに対して、以下の命題を$ P(n)とする。
$ M 未満の任意の非負整数$ i について、$ n \equiv C[i] \mod B[i] を満たす
$ N の制約が小さいため、$ N 以下の全ての非負整数$ n について$ P(n) が真であるかを確認することができる。もし$ P(n) が真となるような非負整数$ n が存在する場合は、その中で最小なものを出力し、そうでなければ$ \mathrm{NaN} を出力すれば良い。
ここで、$ N 以下の非負整数$ n について、非負整数$ S_{n} を次のように定める。
$ T_{n} = \{ i \in \mathbb{Z} \mid 0 \le i \lt M \text{ かつ } n \equiv C[i] \mod B[i] \} としたとき、$ S_{n} を$ T_{n} の大きさ（含まれる要素の個数）とする
このとき、$ N 以下の任意の非負整数$ n について、$ P(n) \iff S_{n} = M が成り立つので、$ P(n) の真偽を確認するためには$ S_{n} が計算できれば十分である。よって、これ以降は$ S_{0}, S_{1}, \ldots, S_{N} を計算する方法を記載する。
まず、$ N 以下の任意の非負整数$ n について、$ S^{\prime}_{n} = 0で初期化する。
その後、$ M 未満の非負整数$ i それぞれについて、以下の操作を実施する。
$ N 以下の非負整数$ k であり、$ k \equiv C[i] \mod B[i] を満たす全ての$ k について$ S^{\prime}_{k} に$ 1 だけ加算する
$ M 未満の非負整数$ i 全てに対して上記操作を実行すると、$ N 以下の任意の非負整数$ n について$ S^{\prime}_{n} = S_{n} となるため、これで$ S_{0}, S_{1}, \ldots, S_{N} を計算できた。
ただし、$ M 未満の非負整数$ i それぞれについて、$ k \equiv C[i] \mod B[i] を満たす$ k の個数は最大で$ 1+\frac{N}{B[i]} であるため、上述の方法では最悪の場合は$ NM 回の計算が必要になり、多くのケースで実行時間制限に抵触してしまう。そのため少し工夫が必要である。
ここで、正整数列$ B の中に複数含まれる数があったとする。例えば、$ i \neq j を満たす$ M 未満の非負整数$ i と$ j について、$ B[i] = B[j] が成り立っていたとする。このとき、もし$ C[i] \not \equiv C[j] \mod B[i] が成り立っていると、$ n \equiv c[i] \mod B[i] \text{ かつ } n \equiv c[j] \mod B[j] を満たす整数$ n は存在し得ないため、$ \mathrm{NaN} を出力すれば良い。よって、$ C[i] \equiv C[j] \mod B[i] が成り立つとして良いが、この場合は$ B と$ C から$ B[j] と$ C[j] をそれぞれ除いても、最終的に出力すべきものは変化しない。
以上から、正数列$ B には同じ数は含まれない（含まれていた場合は除外すれば良い）ので、調和級数の部分和が対数関数で抑えられる事実を考慮すると、$ O(M + N \log N) の計算量で$ S_{0}, S_{1}, \ldots, S_{N} を求められる。今回の制約を考えると、この計算量であれば実行時間制限内に計算できると思われる。
解答例
下は上記の方法で解いたときの提出結果である。また、上記の提出の際に提出したソースコードをその下に転記する。
※ ただし、このソースコードは上で書いた解き方を正確に再現できていない。29行目の条件は「等しい」でなく「等しくない」にすべきであり、それによりis_ok フラグが0 になった場合はNaN を出力すべきである。おそらく、$ i \neq j を満たす$ M 未満の非負整数$ i と$ j で$ B[i] = B[j] かつ$ C[i] \not \equiv C[j] \mod B[i] を満たすものがあるようなテストケースが存在しないため、たまたまAC になったと思われる。
code: C
int main () {
int n = 0;
int m = 0;
int res = 0;
int cnt = 0;
int is_ok = 1;
int ans = 0;
res = scanf("%d", &n);
res = scanf("%d", &m);
for (int i = 0; i < m; i++) {
res = scanf("%d", b+i);
res = scanf("%d", c+i);
}
is_ok = 0;
}
} else {
for (int j = ci%bi; j <= n; j += bi) { }
cnt++;
}
}
while (ans <= n) {
printf("%d\n", ans);
return 0;
}
ans++;
}
printf("NaN\n");
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_367_C
提出のURL 提出時刻 結果 備考
感想
法が互いに素な場合の中国剰余定理しか知らなかったので、A問題を見たとき、「互いに素」じゃない場合に中国剰余定理がどうなるか考えないといけないかなと思ったが、結局は特に何も考えずに全探索で解けてしまったため、このC問題も中国剰余定理に関しては何も考えずに解くことを考えてしまった。互いに素じゃない場合は、gcd とかlcm とかを考えれば良さそうなのは想像がつくけれども