AtCoder Beginner Contest 367 - ABC367振り返り(PythonでA問題〜D問題まで)

AtCoder Beginner Contest 367 - AtCoder

リアルタイム参加ができなかったので、翌日にバーチャル参加しました。ABC問題まで 3問正解でした。

もしもレーティング参加していたら 710パフォくらいなので、レーティングは微減でしょうか。D問題は Difficulty1037 なので今の実力的に難しいけど、できれば解きたかった...。

A - Shout Everyday

夜に起きて翌日に寝る人の場合わけが面倒だった。昼夜逆転は良くないですね...。
問題文中の「たこ焼きへの愛を叫ぶ」に何か元ネタがあるのかと思っていたが、特に無い模様。

A,B,C = map(int, input().split())
if B < C:
    if A >= C or B >= A:
        print("Yes")
    else:
        print("No")
else:
    if A >= C and B >= A:
        print("Yes")
    else:
        print("No")

B - Cut .0

小数点関連の問題。小数点をfloatとして処理すると誤差で失敗することが多いので、入力を文字列とみなして、末尾の 0 と . を削除する。

X = input()
X = X.rstrip("0")
X = X.rstrip(".")
print(X)

C - Enumerate Sequences

組み合わせの数が ５^8=390625 なので、全探索で解決できそう。
for文で８重ループを書くのは大変そう → 深さ優先探索でいけるのでは...ということでやってみたらいけた。

import sys
import copy
sys.setrecursionlimit(10 ** 8)

N, K = map(int, input().split())
R = list(map(int, input().split()))

# 深さ優先探索
current = []
visited = set()
answers = []

# digit桁目以降を探索
def dfs(digit):
    # もし最終桁であれば、Kで割り切れるか判定
    if len(current) == N:
        if sum(current) % K == 0:
            answers.append(copy.deepcopy(current)) # deepcopyしなくてもいいかも
        return

    # 次の桁を追加して、再探索
    max_r = R[digit-1]
    for i in range(1, max_r+1):
        current.append(i)
        dfs(digit+1)
        current.pop()

dfs(1)

for answer in answers: 
    print(*answer)

D - Pedometer (解説を読んで復習)

一時間くらい悩んでいたが、結局TLE止まりで解けず...。累積和を使用するというところまではわかったのだけど。

その後、公式YouTube解説(AtCoder Beginner Contest 367 - YouTube)を見て解答。

• 累積和のmodを求めておく
• 原点からの長さが dist の地点の数を count[dist] に記録しておく

という２点がポイントだったように思う。

N, M = map(int, input().split())
A = list(map(int, input().split()))

L = sum(A) # コース全体の長さ

# 累積和(modで求めておく)
dist_sums = [0] * (N + 1)
for i in range(N):
    dist_sums[i+1] = (dist_sums[i] + A[i]) % M

count = defaultdict(int)

# 2点の組み合わせ
answer = 0
for i in range(N):
    dist = dist_sums[i]     # 地点iの距離
    answer += count[dist]   # 地点0...i-1 までで距離がMの倍数のものの数

    # 地点iから 地点1..i-1の距離をカウント
    dist2 = (dist - L) % M
    answer += count[dist2]

    # 地点iの距離をカウント
    count[dist] += 1

print(answer)