はじめに
こんにちは、Pittaです。
Boot Camp for Beginners Easy の問題をPythonで解きました。(１週間で全部解ききりました…がんばった！)
Boot Camp for Beginners には AtCoder Problems の Traning ページからアクセスできます。
解くのにかかった時間に加え、何か調べたことや特筆しておきたい点があった場合はその旨ポイントに記載しています。
また、全てのコードはGitHub上に公開されています。（先見の明の無さにより100番の問題が10番の後に来ています。）
Boot Camp for Beginners
1. Power Socket
ポイント
A個口の電源タップの数-電源タップに使われている差し込み口の数。
B=1の場合は電源タップの必要がないことに注意。
所要時間: 4分45秒
解答コード
def main():
A, B = map(int, input().split())
if B == 1:
return 0
for i in range(1, 20):
if A*i-(i-1) >= B:
return i
print(main())
2. Rally
ポイント
座標のリストはソートされて与えられているわけではないことに注意して全探索。
所要時間: 4分37秒
解答コード
def main():
N = int(input())
X = list(map(int, input().split()))
ans = 10**18
for meeting_place in range(max(X)+1):
power_needed = 0
for person in range(N):
power_needed += (X[person] - meeting_place)**2
ans = min(ans, power_needed)
print(ans)
main()
3. Qualification Simulator
ポイント
予選通過確定者と海外学生順位の二つの変数を保持しておいて上から都度確認。
所要時間: 5分15秒
解答コード
def main():
N, A, B = map(int, input().split())
S = list(input())
confirmed = 0
foreign_rank = 0
for participant in S:
if participant == "a":
if confirmed < A+B:
print("Yes")
confirmed += 1
else:
print("No")
elif participant == "b":
if confirmed < A+B and foreign_rank < B:
print("Yes")
confirmed += 1
foreign_rank += 1
else:
print("No")
foreign_rank += 1
else:
print("No")
return
main()
4. Tax Rate
ポイント
Pythonで小数を用いた掛け算、割り算をすると型がfloat型になってしまうことに注意する。念のため予想価格周り20円くらいも走査しておいた。
所要時間: 3分02秒
解答コード
def main():
N = int(input())
possible_price = int(N // 1.08)
for price in range(possible_price-20, possible_price+21):
if int(price * 1.08) == N:
print(price)
return
print(":(")
return
main()
5. Can you solve this?
ポイント
書いてあることに忠実に実装するとAC。
所要時間: 3分07秒
解答コード
def main():
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
ans = 0
for _ in range(N):
a = list(map(int, input().split()))
score = C
for i in range(M):
score += a[i]*B[i]
if score > 0:
ans += 1
print(ans)
main()
6. Bishop
ポイント
H==1やW==1のコーナーケースに注意。
所要時間: 7分10秒
解答コード
def main():
H, W = map(int, input().split())
if H==1 or W==1:
return 1
ans = 0
# odd * odd
if H%2 and W%2:
ans = (H//2+1)*(W//2+1) + (H//2)*(W//2)
# even * odd
elif not H%2 and W%2:
ans = (H//2)*(W//2+1) + (H//2)*(W//2)
# odd * even
elif H%2 and not W%2:
ans = (H//2+1)*(W//2) + (H//2)*(W//2)
# even * even
else:
ans = (H//2)*W
return ans
print(main())
7. Bingo
ポイント
ビンゴになったかどうかを確認するための関数を用意しておくと便利。
二次元配列の平坦化にはitertoolsのchain.from_iterableが使える。
参考文献
所要時間: 11分
解答コード
from itertools import chain
def check(li: list) -> bool:
for row in range(3):
flag = True
for col in range(3):
if not li[row][col]:
flag = False
if flag: return flag
for col in range(3):
flag = True
for row in range(3):
if not li[row][col]:
flag = False
if flag: return flag
if li[0][0] and li[1][1] and li[2][2]:
return True
if li[0][2] and li[1][1] and li[2][0]:
return True
return False
def main():
A = []
for _ in range(3):
a = list(map(int, input().split()))
A.append(a)
set_A = set(chain.from_iterable(A))
N = int(input())
turned = [[False, False, False] for _ in range(3)]
for _ in range(N):
b = int(input())
if b in set_A:
for row in range(3):
for col in range(3):
if A[row][col] == b:
turned[row][col] = True
else: continue
if check(turned):
print("Yes")
else:
print("No")
main()
8. 1 21
ポイント
最初からstr型で取ると楽。
所要時間: 1分12秒
解答コード
def main():
a, b = map(str, input().split())
num = int(a+b)
if (num**0.5//1)**2 == num:
print("Yes")
else:
print("No")
main()
9. Collecting Balls (Easy Version)
所要時間: 2分12秒
解答コード
def main():
N = int(input())
K = int(input())
x = list(map(int, input().split()))
ans = 0
for i in range(N):
ans += min(x[i], abs(x[i]-K))*2
print(ans)
main()
10. Card Game For Two
所要時間: 3分7秒
解答コード
def main():
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
Alice = 0
Bob = 0
for i in range(N):
if not i%2:
Alice += A[i]
else:
Bob += A[i]
print(Alice-Bob)
main()
11. Break Number
ポイント
二分探索。
所要時間：3分51秒
解答コード
from bisect import bisect_right
multiple_of_two = [2**i for i in range(8)]
def main():
N = int(input())
idx = bisect_right(multiple_of_two, N)
print(multiple_of_two[idx-1])
main()
12. Travelling Salesman Around Lake
ポイント
円を繋げる。
所要時間: 4分14秒
解答コード
def main():
K, N = map(int, input().split())
A = list(map(int, input().split()))
dist = []
for i in range(N):
if i == 0:
dist.append(A[i]+(K-A[-1]))
else:
dist.append(A[i]-A[i-1])
print(K-max(dist))
main()
13. Cookie Exchanges
所要時間: 5分13秒
解答コード
def main():
A, B, C = map(int, input().split())
for i in range(10**6):
if not A%2 and not B%2 and not C%2:
A, B, C = B//2+C//2, A//2+C//2, A//2+B//2
else:
return i
return -1
print(main())
14. Replacing Integers
所要時間: 2分46秒
解答コード
def main():
N, K = map(int, input().split())
if N%K==0:
return 0
else:
return min(abs(N%K-K), N%K)
print(main())
15. Divide Problems
所要時間：3分19秒
解答コード
def main():
N = int(input())
d = sorted(list(map(int, input().split())))
left_bound = d[N//2-1]
right_bound = d[N//2]
print(right_bound-left_bound)
main()
16. Go To School
ポイント
添え字に注意。
所要時間：1分47秒
解答コード
def main():
N = int(input())
A = list(map(int, input().split()))
ans = [0 for _ in range(N)]
for i in range(N):
ans[A[i]-1] = i+1
print(*ans)
main()
17. Alchemist
ポイント
float型で。
所要時間：2分5秒
解答コード
def main():
N = int(input())
V = sorted(list(map(int, input().split())))
ans = V[0]
for i in range(1, N):
ans = (ans+V[i])/2
print(ans)
main()
18. ATCoder
所要時間：４分
解答コード
def main():
target = set(["A", "C", "G", "T"])
ans = 0
S = list(input())
for i in range(len(S)):
if S[i] in target:
length = 0
for j in range(i, len(S)):
if S[j] in target:
length += 1
else:
break
ans = max(ans, length)
print(ans)
main()
19. Toll Games
ポイント
0地点でもゴールになることに注意。
所要時間：4分13秒
解答コード
from bisect import bisect_right
def main():
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
idx = bisect_right(A, X)
print(min(M-idx, idx))
main()
20. Collatz Problem
ポイント
x in setの判定はO(1)。
所要時間：3分24秒
解答コード
def main():
s = int(input())
numbers = set()
numbers.add(s)
cnt = 1
n = s
while True:
if n%2: n=3*n+1
else: n//=2
cnt += 1
if n in numbers:
break
else:
numbers.add(n)
print(cnt)
main()
21. Next Prime
所要時間：1分43秒
解答コード
from math import sqrt, ceil
def isprime(N):
flag = True
if N == 1: return False
if N == 2: return True
for i in range(ceil(sqrt(N))+1):
if i <= 1: continue
elif N%i == 0:
flag = False
return flag
def main():
X = int(input())
ans = X
while True:
if isprime(ans):
break
else:
ans += 1
print(ans)
main()
22. Candy Distribution Again
ポイント
場合分け。
所要時間：5分57秒
解答コード
def main():
N, x = map(int, input().split())
a = sorted(list(map(int, input().split())))
ans = 0
if x > sum(a):
return N-1
for i in range(N):
if x >= a[i]:
x -= a[i]
ans += 1
else:
break
return ans
print(main())
23. Chocolate
所要時間」：1分59秒
解答コード
from math import ceil
def main():
N = int(input())
D, X = map(int, input().split())
ans = X
for _ in range(N):
a = int(input())
ans += ceil(D/a)
print(ans)
main()
24. Nice Shopping
所要時間：3分36秒
解答コード
def main():
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
price = min(a) + min(b)
for _ in range(M):
x,y,c = map(int, input().split())
price = min(price, a[x-1]+b[y-1]-c)
print(price)
main()
25. Count Order
所要時間：4分20秒
解答コード
from itertools import permutations
from bisect import bisect_right
def main():
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
N_perm = sorted(permutations(P))
P_idx = bisect_right(N_perm, tuple(P))
Q_idx = bisect_right(N_perm, tuple(Q))
print(abs(P_idx-Q_idx))
main()
26. Caracal vs Monster
ポイント
モンスターの個体も管理しておいて一気に片を付ける。同じ操作でモンスターの数は2倍。
所要時間：2分31秒
解答コード
def main():
H = int(input())
cnt = 0
num = 1
while True:
if H==1:
cnt += 1
break
H //= 2
num *= 2
cnt += num
print(cnt)
main()
27. Count Balls
所要時間：2分25秒
解答コード
def main():
N, A, B = map(int, input().split())
ans = (N // (A+B)) * A
ans += min(N%(A+B), A)
print(ans)
main()
28. Shift Only
所要時間：3分49秒
解答コード
def main():
N = int(input())
A = list(map(int, input().split()))
ans = 10**18
for i in range(N):
num = A[i]
cnt = 0
while True:
if num%2:
break
num //= 2
cnt += 1
ans = min(ans, cnt)
print(ans)
main()
29. 754
所要時間：1分45秒
解答コード
def main():
S = list(input())
diff = 753
for i in range(len(S)-2):
num = S[i] + S[i+1] + S[i+2]
diff = min(diff, abs(753-int(num)))
print(diff)
main()
30. Ruined Square
ポイント
回転行列を知っていると解きやすいらしい。
https://blog.hamayanhamayan.com/entry/2018/09/02/223200
私はお絵かきをしながら色々考えて解答。
所要時間：14分49秒
解答コード
def main():
x1, y1, x2, y2 = map(int, input().split())
x3 = x2+y1-y2
y3 = y2-x1+x2
x4 = x1+y1-y2
y4 = y1-x1+x2
print(x3, y3, x4, y4)
main()
31. Varied
所要時間：1分16秒
解答コード
def main():
S =list(input())
S_set = set(S)
if len(S) == len(S_set):
print("yes")
else:
print("no")
main()
32. Increment Decrement
所要時間：1分53秒
解答コード
def main():
N = int(input())
S = list(input())
x = 0
max_x = 0
for i in range(N):
if S[i] == "I":
x+=1
else:
x-=1
max_x = max(max_x, x)
print(max_x)
main()
33. Postal Code
所要時間：3分6秒
解答コード
def main():
A, B = map(int, input().split())
S = list(input())
ans = True
for i in range(len(S)):
if i == A:
if S[i] != "-":
ans = False
else:
continue
else:
if S[i].isdigit():
continue
else:
ans = False
if ans:
print("Yes")
else:
print("No")
main()
34. Coins
所要時間：2分
解答コード
def main():
A = int(input())
B = int(input())
C = int(input())
X = int(input())
cnt = 0
for five_hundred in range(A+1):
for hundred in range(B+1):
for fifty in range(C+1):
if five_hundred*500+hundred*100+fifty*50==X:
cnt += 1
print(cnt)
main()
35. Not Found
ポイント
アルファベット小文字のリストを持っておく。
lowercase_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
所要時間：5分41秒
解答コード
lowercase_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
def main():
S = set(list(input()))
lowercase_list_bool = [(False) for _ in range(26)]
for i in range(26):
if lowercase_list[i] in S:
lowercase_list_bool[i] = True
ans = None
for j in range(26):
if not lowercase_list_bool[j]:
ans = lowercase_list[j]
return ans
return ans
print(main())
36 Prison
所要時間：6分23秒
解答コード
def main():
N, M = map(int, input().split())
max_l = 0
min_r = 10**18
for _ in range(M):
l, r = map(int, input().split())
max_l = max(max_l, l)
min_r = min(min_r, r)
if max_l > min_r:
print(0)
else:
print(min_r-max_l+1)
main()
37. Attack Survival
ポイント
全員から1点引くのではなく正答者に1点を与える。
所要時間：7分6秒
解答コード
def main():
N, K, Q = map(int, input().split())
players_point = [(K) for _ in range(N)]
for _ in range(Q):
a = int(input())
players_point[a-1] += 1
for player in range(N):
if players_point[player] <= Q:
print("No")
else:
print("Yes")
main()
38. Five Dishes
所要時間：10分25秒
解答コード
from math import ceil
def main():
dish_list = []
for _ in range(5):
dish_list.append(int(input()))
mod_last_dish = min([(i-1)%10 for i in dish_list])
cnt = 0
had_last_meal = False
for i in range(5):
if (dish_list[i]-1)%10 == mod_last_dish and not had_last_meal:
cnt += dish_list[i]
had_last_meal = True
else:
cnt += ceil(dish_list[i]/10)*10
print(cnt)
main()
39. Exception Handling
所要時間：4分6秒
解答コード
def main():
N = int(input())
A = []
for _ in range(N):
a = int(input())
A.append(a)
A_sorted = sorted(A, reverse = True)
for item in range(N):
if A[item] == A_sorted[0]:
print(A_sorted[1])
else:
print(A_sorted[0])
main()
40. Range Product
所要時間：2分59秒
解答コード
def main():
a, b = map(int, input().split())
if a <= 0 <= b:
print("Zero")
elif a < 0:
cnt = 0
if b > 0:
cnt = abs(a)
else:
cnt = abs(a-b)+1
if cnt%2:
print("Negative")
else:
print("Positive")
else:
print("Positive")
main()
41. Low Elements
所要時間：5分8秒
解答コード
def main():
N = int(input())
P = list(map(int, input().split()))
min_p = P[0]
cnt = 0
for i in range(N):
if P[i] <= min_p:
cnt += 1
min_p = P[i]
print(cnt)
main()
42. Foods Loved by Everyone
所要時間：3分35秒
解答コード
def main():
N, M = map(int, input().split())
foods_list = [(0) for _ in range(M+1)]
for _ in range(N):
a = list(map(int, input().split()))
for item in range(1, len(a)):
foods_list[a[item]] += 1
cnt = 0
for food in range(M+1):
if foods_list[food] == N:
cnt += 1
print(cnt)
main()
43. Beautiful Strings
所要時間：3分19秒
解答コード
from collections import Counter
def main():
w = list(input())
c = Counter(w)
ans = True
for item in c.values():
if item%2:
ans = False
if ans:
print("Yes")
else:
print("No")
main()
44. Coloring Colorfully
所要時間：4分1秒
解答コード
def main():
S = [int(i) for i in list(input())]
odd = []
even = []
for idx in range(len(S)):
if idx%2:
odd.append(S[idx])
else:
even.append(S[idx])
# if all even are to be black
even_black = sum(even) + (len(odd)-sum(odd))
# if all odd are to be black
odd_black = sum(odd) + (len(even)-sum(even))
print(min(even_black, odd_black))
main()
45. Palindromic Numbers
所要時間：3分20秒
解答コード
def main():
A, B = map(int, input().split())
cnt = 0
for i in range(A, B+1):
sentence = list(str(i))
if sentence == sentence[::-1]:
cnt += 1
print(cnt)
main()
46. Fairness
所要時間：4分35秒
解答コード
def main():
A, B, C, K = map(int, input().split())
if K%2:
return (A-B)*(-1)
else:
return A-B
print(main())
47. Lucas Number
所要時間：4分53秒
解答コード
def check_lucas_number(n: int) -> int:
lucas_number = [(0) for _ in range(87)]
for i in range(87):
if i == 0:
lucas_number[i] = 2
elif i == 1:
lucas_number[i] = 1
else:
lucas_number[i] = lucas_number[i-2]+lucas_number[i-1]
return lucas_number[n]
def main():
N = int(input())
print(check_lucas_number(N))
main()
48. Lower
ポイント
N=1のコーナーケースに注意。
所要時間：7分53秒
解答コード
def main():
N = int(input())
H = list(map(int, input().split()))
ans_length = []
# Corner Case
if N == 1:
return 0
cnt = 0
left = 0
right = 1
while True:
if H[left] >= H[right]:
cnt += 1
left += 1
right += 1
else:
ans_length.append(cnt)
cnt = 0
left +=1
right += 1
if right == N:
ans_length.append(cnt)
break
return max(ans_length)
print(main())
49. Picture Frame
ポイント
list型の前に#を挿入するのはinsert()メソッドで可能だが、リスト内全要素をずらす（O(N)）ので制約には注意が必要。
https://note.nkmk.me/python-list-append-extend-insert/#insert
計算量を削減したい場合はcollectionsモジュールのdequeクラスからappendleft()がO(1)で使える。
https://note.nkmk.me/python-collections-deque/
文字列の結合にはjoin()を使う。
所要時間：3分35秒
解答コード
def main():
H, W = map(int, input().split())
ans = []
ans.append("#" for _ in range(W+2))
for _ in range(H):
a = list(input())
a.insert(0, "#")
a.append("#")
ans.append(a)
ans.append("#" for _ in range(W+2))
for i in range(len(ans)):
to_print = "".join(ans[i])
print(to_print)
main()
50. Comparison
ポイント
Pythonは多倍長整数に対応しているのでこういう問題は楽。
所要時間：46秒
解答コード
def main():
A = int(input())
B = int(input())
if A > B:
print("GREATER")
elif A < B:
print("LESS")
else:
print("EQUAL")
main()
51. Some Sums
所要時間：2分5秒
解答コード
def main():
N, A, B = map(int, input().split())
ans = 0
for i in range(1, N+1):
str_num = str(i)
str_num_sum = sum([int(z) for z in list(str_num)])
if A <= str_num_sum <= B:
ans += i
print(ans)
main()
52. Maximal Value
所要時間：5分46秒
解答コード
def main():
N = int(input())
B = list(map(int, input().split()))
A = [(0) for _ in range(N)]
for i in range(N):
if i == 0:
A[i] = B[0]
elif i == N-1:
A[i] = B[-1]
else:
A[i] = min(B[i], B[i-1])
print(sum(A))
main()
53. Counting Roads
所要時間：2分10秒
解答コード
def main():
N, M = map(int, input().split())
roads = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
roads[a-1].append(b-1)
roads[b-1].append(a-1)
for city in range(N):
print(len(roads[city]))
main()
54. Shiritori
所要時間：4分16秒
解答コード
def main():
N = int(input())
last_letter = 0
said_word = set()
for i in range(N):
w = str(input())
if i == 0:
last_letter = w[-1]
said_word.add(w)
else:
if last_letter == w[0] and w not in said_word:
last_letter = w[-1]
said_word.add(w)
continue
else:
return False
return True
if main():
print("Yes")
else:
print("No")
55. Good Distance
所要時間：5分49秒
解答コード
squared_number_set = set([n*n for n in range(1000)])
def main():
N, D = map(int, input().split())
points = []
for _ in range(N):
x = list(map(int, input().split()))
points.append(x)
cnt = 0
for y in range(N):
for z in range(y+1, N):
distance = 0
for d in range(D):
distance += (points[y][d] - points[z][d])**2
if distance in squared_number_set:
cnt += 1
print(cnt)
main()
56. Small and Large Integers
所要時間：1分59秒
解答コード
def main():
A, B, K = map(int, input().split())
for i in range(A, B+1):
if i <= A+K-1:
print(i)
elif i >= B-K+1:
print(i)
main()
57. Tax Increase
所要時間：5分50秒
解答コード
def original_price(price :int, tax: int) -> list:
p = int(price // (tax/100))
price_list = []
for possible_price in range(p-100, p+100):
if possible_price * tax // 100 == price:
price_list.append(possible_price)
return price_list
def main():
A, B = map(int, input().split())
A_list= original_price(A, 8)
B_list = original_price(B, 10)
for price in A_list:
if price in set(B_list):
return price
return "-1"
print(main())
58. Palace
所要時間：8分4秒
解答コード
def main():
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
H_temp = [T-x*0.006 for x in H]
diff = -10**18
idx = 0
for i in range(N):
if abs(H_temp[i]-A) < abs(diff-A):
diff = H_temp[i]
idx = i
print(idx+1)
main()
59. AcCepted
所要時間：5分32秒
解答コード
def main():
def main():
S = list(input())
# first letter being "A"
if S[0] != "A":
return False
# having one "C"
if S[2:-1].count("C") != 1:
return False
for i in range(1, len(S)):
if S[i] == "C" and 2 <= i <= len(S)-2:
continue
elif S[i].islower():
continue
else:
return False
return True
if main():
print("AC")
else:
print("WA")
60. Contest with Drinks Easy
所要時間：3分30秒
解答コード
def main():
N = int(input())
T = list(map(int, input().split()))
M = int(input())
save = 10**18
for _ in range(M):
p, x = map(int, input().split())
print(sum(T)-(T[p-1]-x))
main()
61. String Rotation
所要時間：3分2秒
解答コード
def main():
S = list(input())
T = list(input()) * 2
ans = False
for i in range(len(S)):
if T[i:i+len(S)] == S:
ans = True
if ans:
print("Yes")
else:
print("No")
main()
62. Thin
所要時間：1分36秒
解答コード
def main():
H, W = map(int, input().split())
for _ in range(H):
c=input()
print(c)
print(c)
main()
63. Brick Break
所要時間：3分8秒
解答コード
def main():
N = int(input())
a = list(map(int, input().split()))
idx = 1
cnt = 0
for i in range(N):
if a[i] == idx:
cnt += 1
idx += 1
if cnt == 0:
print(-1)
else:
print(N-cnt)
main()
64. ∵∴∵
所要時間：4分18秒
解答コード
def main():
O = list(input())
E = list(input())
ans = ""
for i in range(len(O)+len(E)):
if i%2:
ans += E[i//2]
else:
ans += O[i//2]
print(ans)
main()
65. A to Z String
解答コード
def main():
s = list(input())
start = 0
end = 0
for i in range(len(s)):
if s[i] == "A":
start = i
break
for j in reversed(range(len(s))):
if s[j] == "Z":
end = j
break
print(end-start+1)
main()
66. Wanna go back home
所要時間：3分26秒
解答コード
def main():
S = list(input())
north = S.count("N")
south = S.count("S")
east = S.count("E")
west = S.count("W")
if not ((north>0 and south>0) or (north == south == 0)):
print("No")
return
if not ((west>0 and east>0) or (west==east==0)):
print("No")
return
print("Yes")
return
main()
67. Poll
ポイント
collectionsモジュールのCounterクラスにはmost_common()という要素と出現回数をソートして返してくれるメソッドが。
所要時間：6分31秒
解答コード
from collections import Counter
def main():
N = int(input())
S = []
for _ in range(N):
s = input()
S.append(s)
S_counted = Counter(S)
S_counted_sorted = S_counted.most_common()
max_num = S_counted_sorted[0][1]
ans = sorted([i[0] for i in S_counted.items() if i[1] == max_num])
for i in ans:
print(i)
main()
68. Guidebook
所要時間：9分40秒
ポイント
from operator import itemgetter
def main():
N = int(input())
restaurant = []
for i in range(N):
s, p = map(str, input().split())
restaurant.append([i+1, s, int(p)])
sorted_by_point = sorted(restaurant, key=itemgetter(2), reverse=True)
sorted_by_name = sorted(sorted_by_point, key=itemgetter(1))
for j in range(N):
print(sorted_by_name[j][0])
main()
69. Dividing a String
コード
追記
貪欲で書いたが嘘解法っぽいのでまた検討する。
def main():
S = input()
cnt = 0
curr = ""
prev = ""
for i in range(len(S)):
curr += S[i]
if prev != curr:
cnt += 1
prev = curr
curr = ""
print(cnt)
main()
70. 100 to 105
解答コード
def main():
X = int(input())
dp = [(0) for _ in range(X+1)]
dp[0] = 1
for i in range(X+1):
if dp[i]:
for j in range(100, 106):
if i+j <= X:
dp[i+j] = 1
print(dp[X])
main()
71. Iroha Loves Strings (ABC Edition)
所要時間：3分16秒
解答コード
def main():
N, L = map(int, input().split())
li = []
for _ in range(N):
s = input()
li.append(s)
li_sorted = sorted(li)
ans = "".join(li_sorted)
print(ans)
main()
72. Exponential
ポイント
pは2以上の整数なのでpが1である素数は答えにならないことに注意。
所要時間：7分17秒
解答コード
def main():
X = int(input())
max_num = 1
if X <= 3:
print(max_num)
return
cnt = 0
for i in range(2, X):
n = i
while True:
n *= i
cnt += 1
if n <= X:
max_num = max(max_num, n)
else:
break
if cnt > 100:
break
print(max_num)
main()
73. Digit Sum
ポイント
入力例２は別解があるのでそれを考えると見通しが良くなる。
解説AC
解答コード
def main():
N = list(str(input()))
all_nine = True
for i in range(1, len(N)):
if N[i] != "9":
all_nine = False
if all_nine:
ans = int(N[0])+9*(len(N)-1)
else:
ans = int(N[0])-1+9*(len(N)-1)
print(ans)
main()
74. Half and Half
所要時間：8分6秒
解答コード
def main():
A, B, C, X, Y = map(int, input().split())
ans = 10**18
for ab_pizza in range(0, max(X,Y)*2+1, 2):
price = ab_pizza * C
a_pizza = X - ab_pizza//2
b_pizza = Y - ab_pizza//2
price += a_pizza * A if a_pizza >= 0 else 0
price += b_pizza * B if b_pizza >= 0 else 0
ans = min(ans, price)
print(ans)
main()
75. Christmas Eve
所要時間：7分44秒
解答コード
def main():
N, K = map(int, input().split())
h = []
for _ in range(N):
h.append(int(input()))
h = sorted(h)
ans = 10**19
for min_h in range(N-K+1):
ans = min(ans, h[min_h+K-1]-h[min_h])
print(ans)
main()
76. Welcome to AtCoder
所要時間：7分59秒
解答コード
from collections import defaultdict
def main():
N, M = map(int, input().split())
d = defaultdict(list)
for _ in range(M):
p, s = map(str, input().split())
d[int(p)].append(s)
AC_num = 0
WA_num = 0
for result in d.values():
if "AC" in set(result):
AC_num += 1
for submission in result:
if submission == "WA":
WA_num += 1
else:
break
print(AC_num, WA_num)
main()
77. AtCoder Group Contest
解答コード
def main():
N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse = True)
num_teams = 0
strength = 0
for player in range(3*N):
if num_teams < N:
if player%2:
num_teams += 1
strength += a[player]
else:
continue
else:
break
print(strength)
main()
78. Build Stars
所要時間：5分46秒
解答コード
def main():
N = int(input())
H = list(map(int, input().split()))
ans = True
for i in reversed(range(1, N)):
if H[i] - H[i-1] >= 0:
continue
elif H[i] - H[i-1] == -1:
H[i-1] -= 1
else:
ans = False
break
if ans:
print("Yes")
else:
print("No")
main()
79. Table Tennis Training
所要時間：8分39秒
解答コード
def main():
N, A, B = map(int, input().split())
if abs(A-B)%2==0:
return abs(A-B)//2
dist_to_top = (A+B) // 2
dist_to_bottom = ((N-B)+(N-A)) // 2 + 1
return min(dist_to_top, dist_to_bottom)
print(main())
80. Walk on Multiplication Table
所要時間：3分55秒
解答コード
def calc_divisors(N) -> list:
res = []
for i in range(1, N+1):
if i * i > N:
break
if N % i != 0:
continue
res.append(i)
if N // i != i:
res.append(N // i)
res.sort()
return res
def main():
N = int(input())
li = calc_divisors(N)
ans = 10**18
for i in li:
up = N // i
ans = min(ans, up+i-2)
print(ans)
main()
81. *3 or /2
所要時間：4分15秒
解答コード
def main():
N = int(input())
a = list(map(int, input().split()))
ans = 0
for num in a:
while True:
if num%2==0:
num //= 2
ans += 1
else:
break
print(ans)
main()
82. Ice Tea Store
所要時間：12分38秒
解答コード
def main():
Q, H, S, D = map(int, input().split())
N = int(input())
min_for_two_litters = min(Q*8, H*4, S*2, D)
min_for_one_litters = min(Q*4, H*2, S)
if N%2:
print(N//2*min_for_two_litters+min_for_one_litters)
else:
print(N//2*min_for_two_litters)
return
main()
83. Candies
所要時間：6分55秒
解答コード
def main():
N = int(input())
first_row = list(map(int, input().split()))
second_row = list(map(int, input().split()))
for i in range(1, N):
first_row[i] += first_row[i-1]
second_row[i] += second_row[i-1]
first_row.insert(0,0)
second_row.insert(0,0)
ans = 0
for col in range(1, N+1):
candies = first_row[col] + second_row[-1] - second_row[col-1]
ans = max(ans, candies)
print(ans)
main()
84. City Savers
解答コード
所要時間：15分27秒
def main():
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
monster = 0
for yusha in range(N):
# この街すべて制圧可能
if B[yusha] > A[yusha]:
B[yusha] -= A[yusha]
monster += A[yusha]
# 次の街全て制圧はできない
if B[yusha] <= A[yusha+1]:
monster += B[yusha]
A[yusha+1] -= B[yusha]
# 次の街も全て制圧可能
else:
monster += A[yusha+1]
A[yusha+1] = 0
# この街ちょいと厳しい
else:
monster += B[yusha]
print(monster)
main()
85. Ringo's Favorite Numbers
ポイント
N=100の時がコーナーケース。
所要時間：5分30秒
解答コード
def main():
D, N = map(int, input().split())
if D == 0:
ans = 0
cnt = 0
while True:
if cnt == N:
break
else:
ans += 1
if ans%100 != 0:
cnt += 1
return ans
elif D == 1:
if N == 100:
return (N+1) * 100
else:
return N * 100
else:
if N == 100:
return (N+1) * 100 *100
else:
return N * 100 * 100
print(main())
86. To Infinity
ポイント
Sの最初に複数個の1が連なっている可能性があることに注意。
所要時間：6分44秒
解答コード
def main():
S = list(input())
K = int(input())
one_num = 0
for i in range(len(S)):
if S[i] == "1":
one_num += 1
else:
break
if K <= one_num:
print(1)
else:
print(S[one_num])
main()
87. Modulo Summation
所要時間：5分43秒
解答コード
def main():
N = int(input())
a = list(map(int, input().split()))
print(sum(a)-N)
main()
88. Two Colors Card Game
所要時間：4分31秒
解答コード
from collections import defaultdict
def main():
N = int(input())
blue = defaultdict(int)
for _ in range(N):
s = str(input())
blue[s] += 1
M = int(input())
red = defaultdict(int)
for _ in range(M):
s = str(input())
red[s] += 1
ans = 0
for k in blue.keys():
point = blue[k] - red[k]
ans = max(ans, point)
print(ans)
main()
89. Multiple Gift
所要時間：4分43秒
解答コード
def main():
X, Y = map(int,input().split())
ans = 1
num = X
while True:
num *= 2
if num > Y:
break
ans += 1
print(ans)
main()
90. Training Camp
所要時間：1分35秒
解答コード
def main():
mod = 10**9 + 7
power = 1
for i in range(int(input())):
power = power * (i+1) % mod
print(power)
main()
91. Average Length
所要時間：15分34秒
解答コード
from itertools import permutations
from math import factorial
def calc_distance(x1,y1,x2,y2):
return (abs(x1-x2)**2 + abs(y1-y2)**2)**(0.5)
def main():
N = int(input())
cities = []
for _ in range(N):
x, y = map(int, input().split())
cities.append([x,y])
visiting_list = list(permutations(range(N)))
distance = 0
for i in range(len(visiting_list)):
dist = 0
route = list(visiting_list[i])
for cur in range(N-1):
dist += calc_distance(cities[route[cur]][0], cities[route[cur]][1], cities[route[cur+1]][0], cities[route[cur+1]][1])
distance += dist
return distance / factorial(N)
print(main())
92. Unification
所要時間：6分26秒
解答コード
def main():
S = list(input())
one = S.count("1")
zero = S.count("0")
print(min(one, zero)*2)
main()
93. Iron Bar Cutting
所要時間：9分
解答コード
def main():
N = int(input())
A = list(map(int, input().split()))
A_accum = [0]
for i in range(N):
A_accum.append(A[i]+A_accum[-1])
ans = 10**18
for j in range(len(A_accum)):
diff = abs(A_accum[j] - (A_accum[-1] - A_accum[j]))
ans = min(ans, diff)
print(ans)
main()
94. Train Ticket
所要時間：13分29秒
解答コード
from itertools import product
def main():
N = [int(z) for z in list(input())]
li = list(product([-1,1], repeat=3))
li_symbol = list(product(["-", "+"], repeat=3))
for i in range(len(li)):
op = list(li[i])
symbol = list(li_symbol[i])
cnt = N[0]
for n in range(1,4):
cnt += N[n]*op[n-1]
if cnt == 7:
ans = str(N[0])
for k in range(3):
ans += symbol[k]
ans += str(N[k+1])
break
ans += "=7"
print(ans)
main()
95. Same Integers
所要時間：4分55秒
解答コード
def main():
li = sorted(list(map(int, input().split())))
cnt = li[2] - li[1]
li[0] = li[0] + li[2] - li[1]
diff = li[2] - li[0]
cnt += diff // 2
diff %= 2
if diff == 1:
cnt += 2
print(cnt)
main()
96. Similar Arrays
ポイント
余事象。
「全ての項の積が偶数となる。」即ち「少なくとも1つの項が偶数である。」即ち「全体 - 全ての項が奇数である。」
所要時間：5分20秒
解答コード
def main():
N = int(input())
A = list(map(int, input().split()))
cnt = 1
for i in range(N):
if not A[i]%2:
cnt *= 2
print(3**N-cnt)
main()
97. Energy Drink Collector
所要時間：6分40秒
解答コード
def main():
N, M = map(int, input().split())
store = []
for _ in range(N):
store.append(list(map(int, input().split())))
store = sorted(store)
price = 0
for i in range(N):
if M >= store[i][1]:
price += store[i][0] * store[i][1]
M -= store[i][1]
else:
price += store[i][0] * M
break
print(price)
main()
98. Divide a Cuboid
所要時間：2分50秒
解答コード
def main():
L = sorted(list(map(int, input().split())))
all_odd = True
for item in L:
if not item%2:
all_odd = False
if all_odd:
print(L[0]*L[1])
else:
print(0)
main()
99. Painting Balls with AtCoDeer
所要時間：1分52秒
解答コード
def main():
N, K = map(int, input().split())
ans = K
for i in range(1, N):
ans *= (K-1)
print(ans)
main()
100. Friendly Rabbits
所要時間：2分38秒
解答コード
def main():
N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
if A[A[i]-1] == i+1:
cnt += 1
print(cnt//2)
main()