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

A問題 T or T
C-Remainder Minimization 2019

A問題 T or T

n,a,b = map(int, input().split())
print(min((n*a),b))

1 2	n,a,b = map(int, input().split()) print(min((n*a),b))

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買うする形でも良いです。今回は前者の実装です。

解答

コード＋コメント

#入力
l,r = map(int, input().split())
#modを設定
mod = 2019
#最小値を調べるため、初期化時点では無限大とします
ans = float("inf")
#LとRの全組み合わせを調べる
for i in range(l,r):
　#RはLよりも必ず大きいので探索範囲の下限と上限がLよりも1ずつ大きいです
  for j in range(l+1,r+1):
　　#modの性質(合同式で検索)より、掛算する前に剰余をとっても良いです。
    i%=mod
　　#こちらも同じ。コンピュータが扱いきれないほどに大きな計算結果にならないように細かく剰余を取ります
    j%=mod
　　#掛算
    tmp=i*j%mod
　　#掛算の結果が0である場合(LとRの差が2019以上である場合)
    if tmp==0:
　　　#0を出力して終了
      exit(print(0))
　　#LとRの差が2018以下の場合
    else:
　　　#最小値を更新
      ans=min(ans,tmp)
print(ans)

#入力

l,r = map(int, input().split())

#modを設定

mod = 2019

#最小値を調べるため、初期化時点では無限大とします

ans = float("inf")

#LとRの全組み合わせを調べる

for i in range(l,r):

　#RはLよりも必ず大きいので探索範囲の下限と上限がLよりも1ずつ大きいです

for j in range(l+1,r+1):

　　#modの性質(合同式で検索)より、掛算する前に剰余をとっても良いです。

i%=mod

　　#こちらも同じ。コンピュータが扱いきれないほどに大きな計算結果にならないように細かく剰余を取ります

j%=mod

　　#掛算

tmp=i*j%mod

　　#掛算の結果が0である場合(LとRの差が2019以上である場合)

if tmp==0:

　　　#0を出力して終了

exit(print(0))

　　#LとRの差が2018以下の場合

else:

　　　#最小値を更新

ans=min(ans,tmp)

print(ans)

コードのみ

l,r = map(int, input().split())
mod = 2019
ans = float("inf")

for i in range(l,r):
  for j in range(l+1,r+1):
    i%=mod
    j%=mod
    tmp=i*j%mod
    if tmp==0:
      exit(print(0))
    else:
      ans=min(ans,tmp)
print(ans)