はじめに

こんにちは、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が使える。

参考文献

https://note.nkmk.me/python-list-flatten/

所要時間: 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

ポイント

O(\sqrt{n})の素数判定法がアルゴ式にある。

参考文献

https://algo-method.com/descriptions/93

所要時間：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

ポイント

解説にもあるが8!は40320なので全探索しても間に合う。

https://blog.hamayanhamayan.com/entry/2020/01/11/144924

所要時間：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

ポイント

PythonではcollectionsのCounterクラスが使える。

https://note.nkmk.me/python-collections-counter/

所要時間：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()を使う。

https://hibiki-press.tech/python/join/582

所要時間：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は多倍長整数に対応しているのでこういう問題は楽。

https://qiita.com/square1001/items/1aa12e04934b6e749962#2-1-%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%A7%E3%82%82%E5%A4%A7%E3%81%8D%E3%81%AA%E6%95%B0%E3%82%92%E6%89%B1%E3%81%84%E3%81%9F%E3%81%84

所要時間：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()という要素と出現回数をソートして返してくれるメソッドが。

https://qiita.com/ell/items/259388b511e24625c0d7

所要時間：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

ポイント

多次元リストでの用いてのソートはoperatorのitemgetterが便利。

https://qiita.com/t_kanno/items/13dd226e70d080159d97

所要時間：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

ポイント

DPか工夫した貪欲で解けるらしい。1つだけ難易度違いすぎない？

https://drken1215.hatenablog.com/entry/2020/11/11/164900

https://betrue12.hateblo.jp/entry/2020/05/01/201510

コード

追記
貪欲で書いたが嘘解法っぽいのでまた検討する。


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

ポイント

アルゴ式に約数列挙のアルゴリズムが載っています。

https://algo-method.com/descriptions/84

所要時間：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

ポイント

累積和を使うと便利。

https://qiita.com/drken/items/56a6b68edef8fc605821

所要時間：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()