AtCoder Beginner Contest 133 過去問 (A~C)

Python AtCoder

参照

atcoder.jp

A問題

1分くらい。

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

B問題

制約条件も2≤N≤10,1≤D≤10なので、三重ループして解きます。
5分くらい。

N,D = map(int,input().split())
X = [list(map(int, input().split())) for j in range(N)]
 
count_ = 0
for j in range(0,N):
  for i in range(j+1,N):
    sum_ = 0
    for d in range(D):
      sum_+=(X[i][d]-X[j][d])**2
    if (sum_**0.5)%1==0: count_+=1
print(count_)

C問題

茶色問題。
そろそろ茶色難易度も解けるかと思いきや、
問題を複雑に捉えてしまい、解けません。

(i*j )mod 2019が最小となるmod[iとjは未知]を導き出す問題。
自分は2019の約数 = [1,3,673,2019]から考えてしまい、
複雑になるわ、WAで弾かれるは散々な結果・・・。

東大生の力を借りました。
www.planeta.tokyo

0≤L,R≤10**9なので全探索すればTLEされます。
ただしL=1,R=10**9だとしても、
その途中(L~R)に 2019の倍数は確実に存在します。

よって調べる必要があるのは、L~Rに2019の倍数が存在しない場合。
探索範囲は0≤L,R≤2018です。
ここまでくれば全探索で調べてもTLEにはなりません。

L,R = map(int,input().split())

if R-L>=2018: print(0)
else:
  min_=2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      min_=min(min_, i*j%2019)
  print(min_)

レベルアップして茶色コーダーになりたいので、
茶色問題を重点的に解いてまいります。