ABC297 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC297

A – Double Click

問題

A問題

高橋君が最初にダブルクリックをした時刻を求める問題です。クリックとクリックの間隔がD秒以内の時にダブルクリックと定義されています。

解説

高橋君がクリックした各時刻にダブルクリックが成立しているか確かめましょう。

初めのクリックがダブルクリックになることはありませんので、i は 0 始まりではなく 1 始まりです。

コード

# A - Double Click
N, D = map(int, input().split())
T = list(map(int, input().split()))

for i in range(1, N):
    if T[i] - T[i - 1] <= D:
        print(T[i])
        exit()

print(-1)

B – chess960

問題

B問題

K, Q, R, R, B, B, N, N の8文字からなる文字列が以下の条件を満たすかを判定する問題です。

1つめのBの位置と2つ目のBの位置は偶奇が異なる
Kは2つのRの間にある

解説

2つの条件はいずれもインデックスに関する条件のため、まずはインデックスを調べましょう。

Pythonではfindで先頭から検索してヒットしたインデックスを、rfindで末尾から検索してヒットしたインデックスを取得できます。

インデックス取得後は条件式を立てるのみです。1つ目の条件の「偶奇が異なる」は、「和が奇数となる」ことに読み替えています。小さな工夫です。

コード

# B - chess960
S = input()

x, y = S.find('B'), S.rfind('B')
a, b = S.find('R'), S.rfind('R')
c = S.find('K')

if (x + y) % 2 == 1 and a < c < b:
    print("Yes")
else:
    print("No")

C – PC on the Table

問題

C問題

2次元配列において、横2連続で”T”が並んでいる箇所を”P”と”C”に置き換える問題です。

解説

各行は独立していますので、1行ずつ考えることができます。

全探索で、現在の文字と次の文字が”T”であるかどうか調べましょう。条件を満たす場合、2つの”T”を、”P”と”C”に置き換えます。

この方法は、”TTT”のような状況においても問題なく機能します。まず”PCT”に変わりますので、3つめの”T”は”T”のままです。

コード

# C - PC on the Table
from sys import stdin
H, W = map(int, input().split())
S = [list(stdin.readline()[:-1]) for _ in range(H)]

for row in S:
    for i in range(W - 1):
        if row[i] == "T" and row[i + 1] == "T":
            row[i] = "P"
            row[i + 1] = "C"
    print(*row, sep="")

D – Count Subtractions

問題

D問題

2つの数 A, B に対し、A = B になるまで以下の操作を繰り返し、何回操作を行ったかをカウントする問題です。

A > Bならば、A を A – B で置き換える
A < Bならば、B を B – A で置き換える

解説

愚直に A = B になるまで操作を繰り返すアルゴリズムではTLEしてしまうので、工夫が必要です。

このような問題では具体例を考えるのが良いでしょう。

例：A = 14, B = 6の場合
1回目　A = 8, B = 6
2回目　A = 2, B = 6
3回目　A = 2, B = 4
4回目　A = 2, B = 2

上の例において、1回目と2回目はAの数字が減り、3回目と4回目はBの数字が減っています。このように減らす側が連続している箇所について、1回ずつ処理するのではなく、まとめて処理することで高速化することができます。

上の例で計算します。
まずAの数字を減らせる回数は、AをBで割った商と一致します。14 ÷ 6 = 2 余り 2 なので、14から6を2回引けます。カウントを2増やします。
次にBの数字を減らせる回数は、BをAで割った商と一致します。6 ÷ 2 = 3 なので、6から2を3回引けます。カウントを3増やします。
しかしこれでは、行きすぎて A = 0, B = 2 となってしまいました。調整のため、カウントを1減らします。
2 + 3 – 1 = 4で答えは4回となりました。
この考え方でうまく解けそうですね。

下のコードでは、常に A > B となるように適宜 A と B を反転させています。

コード

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

if A < B:
    A, B = B, A

count = 0

while B > 0:
    Q = A // B
    A = A - B * Q
    A, B = B, A
    count += Q

count -= 1

print(count)