(初心者必見)ABC297 Python参加：A〜E

初めに

AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。
コメントなどいただけると嬉しいです！！

成績

ABC297 4冠。
久々にDまで解けて嬉しかったけど、これ灰diffなのかよ...

目次

A - Double Click
B - chess960
C - PC on the Table
D - Count Subtractions
E - Kth Takoyaki Set

A - Double Click

問題ページ
自然数の単調増加数列Aに対して、隣り合う二つの要素の差が自然数D以下のものがあるかを判定する問題。

コンテスト中の考察

愚直に先頭から比較していってD以下のものがあればそれを出力、なければ-1を出力。

コンテスト中のコード

a.py

N, D = map(int, input().split())
T = list(map(int, input().split()))

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

改善点

着想面

特になし。

コード面

これも特にないかな？

B - chess960

問題ページ
入力される文字列Sがとある条件を満たすかを判定する問題。正しくif文を書けるかどうかの問題。

コンテスト中の考察

そのまま条件をif文で書けばOK。
条件は、下記の2つです。

1. S において左から x,y (x<y) 文字目が B であるとする。このとき x と y の偶奇が異なる
2. K は 2 つの R の間にある。
   より形式的には、S において左から x,y (x<y) 文字目が R であり、 z 文字目が K であるとする。
   このとき、 x<z<y が成り立つ。

少し冗長かもしれないですが、文字が出現した場所を辞書で管理しています。
1つ目の条件である偶奇が異なるかの判定は、2で割った余りのXORを取ることでシンプルに判定できます。
2つ目条件は辞書の値をソートして判定すれば良いです。

コンテスト中のコード

b.py

S = input()
dict = {}
for i in range(len(S)):
    if S[i] in dict:
        dict[S[i]].append(i+1)
    else:
       dict[S[i]] = [i+1]

if dict['B'][0]%2 ^ dict['B'][1]%2:
    if min(dict['R']) < dict['K'][0] < max(dict['R']):
        print('Yes')
        exit()
print('No')

改善点

着想面

特になし。

コード面

解説にめちゃめちゃ短いコードあってびっくり。
条件1、偶奇が異なるかは確かに差に対してmod2取れば十分ですね。
条件2、rfind()便利ですね〜〜。
Yes/Noの出力も最後に判定すれば綺麗に収まりますね。

b_fix.py

S = input()
c1 = (S.rfind('B') - S.find('B')) % 2 == 1
c2 = S.find('R') < S.find('K') < S.rfind('R')
print('Yes' if c1 and c2 else 'No')

C - PC on the Table

問題ページ
特定の条件を満たす文字列を置換する問題。

コンテスト中の考察

左から貪欲に置き換えていけば良いので、愚直に先頭から見ていって‘TT’があったら‘PC’で置き換え。

コンテスト中のコード

c.py

H, W = map(int, input().split())

for _ in range(H):
    S = list(input())
    j = 0
    while j < W-1:
        if S[j] != 'T':
            j += 1
        else:
            if S[j+1] == "T":
                S[j] = 'P'
                S[j+1] = 'C'
                j += 2
            else:
                j += 1
    print(''.join(S))

改善点

着想面

特になし。

コード面

いやぁ、とっても綺麗ですね...。
確かに'TT'を'PC'で置き換えるだけなら文字列置換で十分ですね。
少し冗長なコードを書いて、地味に頭使ってしまいました。

c_fix.py

H, W = map(int, input().split())
for _ in range(H):
print(input().replace('TT', 'PC'))

D - Count Subtractions

問題ページ
正整数A, Bに対して、A=B になるまでに所定の操作が何回必要かを求める問題。

コンテスト中の考察

A, B <= 10^18であるので、愚直に操作しようとするとA=1, B=10^18 のようなケースでTLEになってしまいます。ここで、 A と B の大小関係が入れ替わるタイミングがmod以下になった時であることに気づくことができれば高速化の目処が立ちます。具体的には、 A>Bの場合、AがB以下になるまで A= A-B が単調に繰り返されることになります。つまり、大小関係が入れ替わるまでに行われる操作は（A>Bとすると）、A//B 回であり、大小関係が入れ替わるタイミングの最終的なAの値はA%B となります。ここで、A%B == 0の場合に注意が必要です。 A%B == 0のケースでは割り切れる、すなわち最後の１回は A == Bとなっているわけです。なので操作回数を１回減らして考える必要があります。

コンテスト中のコード

d.py

A, B = map(int, input().split())
ans = 0
while 1:
    if A == B:
        print(ans)
        exit()
    elif A > B:
        ans += A // B 
        if A%B == 0:
            ans -= 1
            print(ans)
            exit()
        else:
            esc = A
            A = B
            B = esc%B
    else:
        ans += B // A 
        if B%A == 0:
            ans -= 1
            print(ans)
            exit()
        else:
            esc = B
            B = A
            A = esc%A

改善点

着想面

特になし。

コード面

swapすればこんなにif文いらなかったっぽい。確かに(笑)。
あと　swapするのにescのような変数を使う必要はないらしい（知らなかった）。

d_fix.py

A, B = map(int, input().split())
ans = 0
while 1:
    if A == B:
        print(ans)
        exit()
    elif B > A:
        A, B = B, A
        
    ans += A // B 
    if A%B == 0:
        ans -= 1
        print(ans)
        exit()
    else:
        A, B = B, A%B

E - Kth Takoyaki Set

問題ページ
自然数の数列Aを1つ以上選んで実現可能な部分和のK番目の値を求める問題。

コンテスト中の考察

え？簡単じゃね？bit全探索するだけじゃん？って思ってたのですが、同じ数字を複数使っても良いという部分を読み飛ばしていました。上限がなくなって、大小関係なく無条件に全部列挙！みたいな考えが使えなくなってしまったので、数列Aをソートして小さい方から効率的に部分和を求めようとしてのですが、一般的で高速な方法が思い浮かばず断念…。

改善点

着想面

なんと無く建てた方針である「小さい方から効率的に部分和を求める」という着想自体は概ね正しかったようです。
コンテスト中はどうやってそれを実現するかが全く思い浮かばなかったのですが、優先度付きキューを使えば良かったようです。
確かに言われてみればそうですよね。優先度付きキュー（以下heapqueue）とは、入力順序に関係なく、いい感じの計算量で数値の小さいもの（もしくは大きいもの）から順に出してくれるデータ構造です。木の深さをなるべきく均等に保つ平衡二分木というものを効率的に管理することによって高速に最小値を出力可能にしていた気がします（二分木なのでO(logN)とかなんですかね？）。
具体的な実装方法としては、i番目に小さい解を見つけるためには i-1番目までの解候補の最小値をheapqueueから1個持ってきて、それが今までの解の中の最大値と一緒で無ければその値がi番目に小さい値となる。その後、heapqueueに先ほど見つけたi番目の解に、Aのそれぞれの要素を足した値を入れていきます。i+1番目に小さい値は、またその中の最小値をheapqueueが出してくれて…という操作をK回繰り返せば「小さい方から効率的に部分和を求める」が達成できます。heapqueueの初期値には0を入れておくと良いでしょう。

コード面

e_fix.py

import heapq

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

pre = -1
cnt = 0
q = [0]
heapq.heapify(q)
while cnt <= K:
    while 1:
        price = heapq.heappop(q)
        if price != pre:
            pre = price
            break
    for a in A:
        heapq.heappush(q, price+a)
    cnt += 1
print(pre)

終わりに

書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、　今後ともよろしくお願いいたします！いいねやコメントいただけると嬉しいです！！