スポンサーリンク

【Python】AtCoder Beginner Contest133 A,C問題 解答・解説

スポンサーリンク
スポンサーリンク
この記事は約2分で読めます。

A問題 T or T

C-Remainder Minimization 2019

方針

探索範囲を絞った上で、iとjの組み合わせを全探索する方針で解きます。理由は以下の通りです。

まず、LとRの範囲は0~10**9なので全探索は間に合いません。

2019で割った余りは、どんなに数が大きくなっても0~2018で循環します。(modの性質)

そのため、探索の範囲は最大でもLが2019個、Rが2019個となります。

この時の最大の計算量は2019×2019=4076371→4×10の6乗ほどになります。

pythonでは10の8乗回までの計算量であれば間に合うという話なので、制限時間に事足ります。

探索はL~R範囲内に絞りますが、LとRの差が2019以内であれば上記の最大の計算量よりも小さくなりますし、LとRの差が2019以上であれば、2019で割った時の余りが0となる数が出てくるので、iとjを掛算したときの結果が0となり、最小値として0を解答することになります。

実装としてはL~Rの全組み合わせを探索中に、掛算の結果が0になった時点で判定しても良いですし、LとRの差が2019以上あることを先に判定して起き、差が2018よりも小さい場合のみ短s買うする形でも良いです。今回は前者の実装です。

解答

コード+コメント

コードのみ

 

 

参考

modや合同式についてはこちらの動画が一番だと思います。ヨビノリ、初めて見たのですがとてもわかりやすいですね。

【高校数学(発展)】合同式①(modとは何か)【整数】 – YouTube

 

整数の性質を利用して解く問題がABCのC問題には多いです。

初っ端からABCの過去問でその性質が使われている素晴らしい問題集があります。

コメント