AtCoder Beginner Contest 131解いてみた

はじめに

AtCoder Beginner Contest 131をといてみた
https://atcoder.jp/contests/abc131/tasks

自分より成績の良い友人の解答をお借りして自分が何が苦手でわかっていなかったかを考えてみる

A - Security

自分の解答

strings = list(input())
before_number = 100000
flag = False
for number in strings:
  #前の番号と今の番号が一致したら
  if before_number == int(number):
    flag = True
  else:
    before_number = int(number)

if flag == True:
  print("Bad")
else:
  print("Good")

友人の解答

str = input()
p = ""
result = "Good"
for s in str:
    if p == s :
        result = "Bad"
    p = s
print(result)

考えたこと

B - Bite Eating

やたらめったら文章量が多くて圧倒されてしまった
一つずつ解決して完答した

#N個のりんごの数　L:味の基準
N, L = map(int, input().split())

#普通のアップルパイの味
nomal_sum = 0
for number in range(1,N+1):
  nomal_sum = nomal_sum + (L + number -1)
#print("普通のアップルパイ",nomal_sum)

#一つ欠けたアップルパイのパターンを作る
#lost_sum = 0
#for number in range(1,N+1):
#  if number == 1:
#    print("1だよ")
#  else:
#    lost_sum = lost_sum + (L + number -1)
#print(lost_sum)

#一つ欠けたアップルパイのリストをつくる
list = []
lost_sum = 0
for number in range(1,N+1):
  for number2 in range(1,N+1):
    if number != number2:
      lost_sum = lost_sum + (L + number2 -1)
  list.insert(number, lost_sum)
  lost_sum = 0
#print("list",list)

# 差の絶対値を取る
minimal1 = 100000
ans = 0
for list_aji in list:
  #print("list_aji",list_aji)
  #print("minimal1",minimal1)
  #print("abs(list_aji - nomal_sum)",abs(list_aji - nomal_sum))
  if minimal1 >= abs(list_aji - nomal_sum):
    minimal1 = abs(list_aji - nomal_sum)
    ans = list_aji
print(ans)

友人の書いたコード

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

list = [L+(i+1)-1 for i in range(N)]

list.sort(key=lambda x: abs(x))

del list[0]

print(sum(list))

C - Anti-Division

計算量さえ考えなければ正解だっただろうな。。。と思う
というかこれをどうやって計算量を少なくできるのかが全くわからなかった
とてもつらい

自分の解答

A, B, C, D = map(int, input().split())

count = 0
for i in range(A,B+1):
  #print("///////////")
  #print(i)
  if(i % C == 0 and i % D != 0): # 3で割り切れるが５で割り切れない
    #print("2で割り切れるが3で割り切れない")
    pass
  elif(i % D == 0 and i % C != 0): # 5で割り切れるが3で割り切れない
    #print("2で割り切れるが3で割り切れない")
    pass
  elif(i % C == 0 and i % D == 0): # 3で割り切れ、かつ5で割り切れる
    #print("2で割り切れるが3で割り切れる")
    pass
  else:
    #print("どれにもあてはまらない",i)
    count = count + 1
print(count)

友人の解答

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)

A, B, C, D = map(int, input().split())

b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)

print((B-A+1) -(b_num - a_num))

コードを改良した
最小公倍数や最大公約数を使うなんて思いもしなかった
ループで回してがんばるという脳筋プレイはやめたい
参考文献によるとfractionsモジュールにgcd関数があるとのことなので流用した

import fractions
def lcm(a,b):
  return a*b //fractions.gcd(a, b)

A, B,C,D = map(int, input().split())

b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
print((B-(A-1))-(b_num-a_num))

参考文献

D - Megalomania

あり本でやったような問題だなと思った
アルゴリズム的には、一番仕事の締切が短いやつから片付けていくのがよいのだろうか？
全然とけなかった

自分の解答

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
#A[0][0]仕事の時間　A[0][1]締切
print(A[0][0],A[0][1])
#知りたいことはすべての仕事を達成できるかどうか
#終了時間が最も早いものを選ぶ
most_last = 100000
time = 0

for number in range(0,N):
  print("締切",A[number][1])
  if most_last > A[number][1]:
    #一番小さい締切を更新
    most_last = A[number][1]
print(most_last)
for y, row in enumerate(A):
    try:
        pos = (y, row.index(most_last))
        break
    except ValueError:
        pass

print("pos",pos[0],pos[1])
#一番小さい締切の配列はとれる
print(A[pos[0]][pos[1]])

#時間を進めてその配列を削除させる

友人の解答

N = int(input())
jobs = []
for i in range(N):
    jobs.append(list(map(int, input().split())))

time = 0
result = "Yes"
jobs.sort(key=lambda x:x[1])

for job in jobs:
    time += job[0]
    if(time > job[1]):
        result = "No"
        break

print(result)

考えたこと

二重配列をうまいこと使いこなせなかった
sortとラムダ式をうまいこと使う必要があった
Pythonらしい書き方ができていないのが問題

こうやって二重配列にうまいこと入れれるのは学びになった

for i in range(N):
    jobs.append(list(map(int, input().split())))

このソートの仕方が学びになった
二重配列のソートをどうすれば良いのかわからなくて困っていた

jobs.sort(key=lambda x:x[1])