AtCoder Beginner Contest 453 参加記録と解答例 (A〜C問題)

本記事は、AtCoder Beginner Contest 453 (ABC453) に参加した際の、A〜C問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Trimo

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 100 点

問題文

長さ N の文字列 S が与えられます。

S のうち先頭に連続する o をすべて取り除いた文字列を出力してください。
なお、 S 中のすべての文字が o である場合は空文字列を出力してください。

制約

• N は 1 ≤ N ≤ 50 を満たす整数
• S は英小文字からなる長さ N の文字列

自分の解答の方針

先頭からo出ない文字が初めに出てくる場所を調べ、それ以降の文字列を出力する。

提出したコード

N = int(input())
S = list(input())
i = 0
while i <= N-1 and S[i] == "o":
    i += 1
print("".join(S[i:]))

---

B - Sensor Data Logging

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 200 点

問題文

ある測定では、時刻 0,1,…,T におけるセンサーの測定値を以下の規則で記録します。

• 時刻 0 では、測定値を保存する。
• 時刻 1,2,…,T では、「現時刻の測定値」と「直前に保存された測定値」との差の絶対値が X 以上であるとき、またその時に限り値を保存する。

時刻 i=0,1,…,T におけるセンサーの測定値は Ai でした。
測定値が保存された時刻と保存された値とを、時刻の昇順に出力してください。

制約

• 1 ≤ T ≤ 100
• 1 ≤ X ≤ 100
• 0 ≤ Ai ≤ 100
• 入力はすべて整数

自分の解答の方針

問題の通りに実装する。

提出したコード

T,X = map(int,input().split())
A = list(map(int,input().split()))
sensor = 0
for i in range(T+1):
    if i == 0:
        sensor = A[i]
        print(i,sensor)
    elif abs(A[i] - sensor) >= X:
        sensor = A[i]
        print(i,sensor)

---

C - Sneaking Glances

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 300 点

問題文

数直線上の座標 0.5 に高橋君がいます。
高橋君はこれから N 回の移動を行います。

i 回目の移動では、「正の方向」「負の方向」のいずれかを選び、その方向に Li 進みます。
高橋君は座標 0 を最大で何回通り過ぎることが出来るでしょうか？
なお、この問題の制約上、座標 0 で完了する移動が生じることはありません。

制約

• 1 ≤ N ≤ 20
• 1 ≤ Li ≤ 10^9
• 入力はすべて整数

自分の解答の方針

Nが最大でも20なので、すべての選択を全探索しても2^20で10^6程度
2進数に変換して各桁の数字で正か負かを選択することで全探索できる。

提出したコード

N = int(input())
L = list(map(int,input().split()))
# 全探索
ans = 0
for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    count = 0
    current = 0.5
    for j in range(N):
        if bit[j] == "1":
            # 正の方向
            if current < 0 and current + L[j] > 0:
                count += 1
            current += L[j]
        else:
            # 負の方向
            if current > 0 and current - L[j] < 0:
                count += 1
            current -= L[j]
    ans = max(ans,count)
print(ans)