【Python】AtCoder Beginner Contest212 A,B,C問題解答

A問題 Alloy
B問題 Weak Password
C問題

A問題 Alloy

a,b = map(int, input().split())
if a>0 and b>0:
  print('Alloy')
  
elif a>0 and b==0:
  print('Gold')
  
elif b>0 and a==0:
  print('Silver')

a,b = map(int, input().split())

if a>0 and b>0:

print('Alloy')

elif a>0 and b==0:

print('Gold')

elif b>0 and a==0:

print('Silver')

B問題 Weak Password

x = input()

if x[0]==x[1] and x[1]==x[2] and x[2]==x[3]: #[1]
  print('Weak')
elif int(x[1])==int(x[0])+1 and int(x[2])==int(x[1])+1 and int(x[3])==int(x[2])+1: #[2]
  print('Weak')
elif int(x[0])==9 and int(x[1])==0 and int(x[2])==1 and int(x[3])==2: #[3]
  print('Weak')
elif int(x[0])==8 and int(x[1])==9 and int(x[2])==0 and int(x[3])==1: #[3]
  print('Weak')
elif int(x[0])==7 and int(x[1])==8 and int(x[2])==9 and int(x[3])==0: #[3]
  print('Weak')
else: #[4]
  print('Strong')

x = input()

if x[0]==x[1] and x[1]==x[2] and x[2]==x[3]: #[1]

print('Weak')

elif int(x[1])==int(x[0])+1 and int(x[2])==int(x[1])+1 and int(x[3])==int(x[2])+1: #[2]

print('Weak')

elif int(x[0])==9 and int(x[1])==0 and int(x[2])==1 and int(x[3])==2: #[3]

print('Weak')

elif int(x[0])==8 and int(x[1])==9 and int(x[2])==0 and int(x[3])==1: #[3]

print('Weak')

elif int(x[0])==7 and int(x[1])==8 and int(x[2])==9 and int(x[3])==0: #[3]

print('Weak')

else: #[4]

print('Strong')

4桁の数字が入力されるので、全て同じ数字の場合と、数字が1234のように1つずつ増えて連続している場合にWeak、それ以外はStrongと表示させる問題です。いくつかのパターンに分けられると思います。

[1]4桁全てが同じ場合

1桁目=2桁目、2桁目=3桁目、3桁目=4桁を全て同時に満たすにWeakと表示させることにしました。

[2]連続した数字の場合

入力される4桁の値が1ずつ増加する連続した数字だった場合です。

2桁目=1桁目+1 、3桁目=2桁目+1、4桁目=3桁目+1を全て同時に満たす場合にWeakと表示させています。

[3]9と0を含む連続した数字の場合

問題文より9の次は0になりますが、9と0を含む連続した数字は以下のパターンに分けられます。

7890, 8901, 9012

これらのパターンは個別に条件を指定してWeakと表示させることにしました。

[4]以上のどれにも当てはまらない場合

Strongと表示させています。

C問題

方針：一方は線形探索、他方は二分探索

数字の並びが2つあり、それぞれリストにして二重ループで全探索したところTLEになってしまいました。

線形探索の中でさらに線形探索を行う二重ループでは計算量はO(N^2)になり、制限時間内に終了することができずTLEとなります。

そこで、リストを小さい方から順にソートした上で一方は初めから順番に、もう一方は二分探索を使って差の最小値を調べます。

2分探索を使うときはリストがソートされている必要がありますが、初めから順に調べる線形探索よりも処理が早く、計算量はO(logN)であり、制限時間内に間に合います。

解答1：bisectを利用

import bisect

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort
b = list(map(int, input().split()))
b.sort()

ans = 10**9
for i in a:
  c = bisect.bisect(b,i)
  ans = min(ans,abs(i-b[c-1]))
  if c<m:
    ans = min(ans,abs(i-b[c]))
print(ans)

import bisect

n,m = map(int, input().split())

a = list(map(int, input().split()))

a.sort

b = list(map(int, input().split()))

b.sort()

ans = 10**9

for i in a:

c = bisect.bisect(b,i)

ans = min(ans,abs(i-b[c-1]))

if c<m:

ans = min(ans,abs(i-b[c]))

print(ans)

解答2：自身で二分探索を実装

def Binary_search(x,y):
  min=0
  max=len(x)-1
  while min<=max:
    mid=(min+max)//2
    if x[mid]==y:
      return mid
    elif x[mid]<y:
      min=mid+1
    else:
      max=mid-1
  return mid

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort
b = list(map(int, input().split()))
b.sort()

ans = 10**11

for i in a:
  c=Binary_search(b,i)
  ans=min(ans,abs(i-b[c]))
  ans=min(ans,abs(i-b[c-1]))
  if c!=m-1:
    ans=min(ans,abs(i-b[c+1]))
print(ans)

def Binary_search(x,y):

min=0

max=len(x)-1

while min<=max:

mid=(min+max)//2

if x[mid]==y:

return mid

elif x[mid]<y:

min=mid+1

else:

max=mid-1

return mid

n,m = map(int, input().split())

a = list(map(int, input().split()))

a.sort

b = list(map(int, input().split()))

b.sort()

ans = 10**11

for i in a:

c=Binary_search(b,i)

ans=min(ans,abs(i-b[c]))

ans=min(ans,abs(i-b[c-1]))

if c!=m-1:

ans=min(ans,abs(i-b[c+1]))

print(ans)