早稲田卒のAI研究者のブログ

データサイエンス、機械学習、競技プログラミング、音楽、勉強

【合同式(mod)】ABC133 C - Remainder Minimization 2019をPythonで解いてみた

atcoder.jp


今日は合同式、つまりmodです。
大学受験でも整数問題として出題され、多くの受験生を苦しめたあいつです。
苦手な方が多いんではないでしょうか。

受験生の頃は、かなり難しかったですが、実は競プロにけるmodの問題はそんなに恐れるような存在ではありません。

modを用いた四則演算の特徴を勉強しておけば、なんとかなるイメージがあります。

そもそもmodってなに?という方は下のワイトにわかりやすい説明が書かれています。
是非参考にしてみてください。

mathtrain.jp


四則演算の特徴については以下のサイトが非常に参考になりました。
ぜひ皆さんも参考にしてください。

qiita.com

では、問題を解いていきます。

思考の過程

問題を見た瞬間、単純にijを二重のfor文で回したくなりますね。

ここで計算量を見てみましょう。
この問題では、iの最小値は0jの最大値はRであり、計算量はR-Lに依存します。
ですが、Rの最大値は10^{9}のオーダーであるため、この方法では、計算量がO(N^{2})となってしまい、時間が間に合いあわない、ということがわかります。

そのため、別の視点で考えていきました。
上記の二重のfor文での探索中に、解が0になったら探索をやめるという方法です。
これは、R-L2019以上の場合、確実に起こります。
したがって、この方法を用いると、計算の候補は2019^{2}となり、十分間に合うことがわかります。

コード実装

プログラムの流れは以下のようにする。
1. 解答の初期値を2019に設定
2. 二重のforで全探索
3. もし解が0になったら探索をやめる

L, R = map(int, input().split())
mod = 2019
ij_mod_min = 2019  # 解答の初期値を2019に設定
for i in range(L, R):  # 二重のforで全探索
    for j in range(i+1, R+1):
        ij_mod = ((i % mod)*(j % mod)) % mod
        if ij_mod_min > ij_mod:
            ij_mod_min = ij_mod
        if ij_mod_min == 0:  # もし解が0になったら探索をやめる
            break
    else:
        continue
    break
print(ij_mod_min)


無事ACでした。
条件付けで探索をやめるというのは常套手段ですね。
解けて安心しました。