初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC324_A-C問題】

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC324のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回の参加コンテスト(ABC324)
感想

今回の参加コンテスト(ABC324)

AtCoder Beginner Contest 324

A問題：Same

A – Same

問題(要約)

与えられたN個の整数A₁, A₂, …, A_Nがすべて等しい場合には”Yes”、そうでなければ”No”を出力する。

解答

公式回答とは別解でCounterモジュールを使っています。

# Counterモジュールを使ってリストAの各要素の出現回数を数える
from collections import Counter

# 整数nを入力として受け取る
n = int(input())

# スペース区切りの整数をリストAとして入力として受け取る
A = list(map(int, input().split()))

# リストAの要素の種類の数を数えて、種類が1つならば"Yes"、そうでなければ"No"を出力する
if len(Counter(A)) == 1:
    print('Yes')
else:
    print('No')

最初に、整数 n を入力として受け取ります。これは整数リスト A の長さです。
次に、スペースで区切られた整数をリスト A として入力として受け取ります。これは map(int, input().split()) を使って整数のリストに変換されます。
Counter(A) を使用して、リスト A 内の各要素の出現回数を数えます。Counter オブジェクトは辞書のような形式で、各要素がキー、その出現回数が値として保存されます。
len(Counter(A)) を計算して、リスト A 内の異なる要素の数（つまり、出現回数が1以上の要素の種類の数）を取得します。
もし異なる要素の数が1つだけ（つまり、すべての要素が同じ値）ならば、”Yes” を出力します。それ以外の場合は、つまり異なる要素が複数ある場合は、”No” を出力します。

B問題：3-smooth Numbers

B – 3-smooth Numbers

問題(要約)

与えられた正の整数Nが N=2^x3^y の形に表される整数xとyが存在する場合に”Yes”、存在しない場合に”No”を出力する。

解答

Nが2と3の乗数で成り立つ必要があるため、Nを2と3で割り続けnが1になるかを調べていきます。

# 正の整数nを入力として受け取る
n = int(input())

# nが2で割り切れる場合、2で割り続ける
while n % 2 == 0:
    n = n // 2

# nが3で割り切れる場合、3で割り続ける
while n % 3 == 0:
    n = n // 3

# nが最終的に1になった場合"Yes"を出力、それ以外の場合"No"を出力
if n == 1:
    print('Yes')
else:
    print('No')

以下詳細

最初に、正の整数 n を入力として受け取ります。
n が2で割り切れる場合、n を2で割り続けます。この操作により、n の因数に2が残らなくなり、最終的には2で割り切れない（つまり奇数になる）場合か、1になる場合が考えられます。
n が3で割り切れる場合、n を3で割り続けます。同様に、n の因数に3が残らなくなり、最終的には3で割り切れない場合か、1になる場合が考えられます。
最終的に、n が1になった場合、与えられた整数 N は N=2^x3^y の形に表される整数 x と y が存在することになります。したがって、”Yes” を出力します。それ以外の場合、n は1ではなく、与えられた条件を満たす整数 x と y が存在しないことを意味するので、”No” を出力します。

C問題：Error Correction

C – Error Correction

問題(要約)

高橋君が青木君に送った英小文字からなる文字列Tと、青木君が受信した文字列T’が与えられます。T’はTから一部が変更された可能性があり、具体的には以下の4つのうちのいずれか1つの条件が成り立ちます：

T’はTと等しい。
T’はTのどれか1つの位置（先頭と末尾を含む）に英小文字を1つ挿入して得られる文字列である。
T’はTから1文字を削除して得られる文字列である。
T’はTのある1文字を別の英小文字に変更して得られる文字列である。

青木君が受信した文字列T’と、英小文字からなるN個の文字列S1, S2, …, SNが与えられるので、S1, S2, …, SNの中で、高橋君が送った文字列Tと等しい可能性があるものをすべて求めてください。

解答

文字の長さを前判断として、可能性のある条件確認に進みます。文字が異なる部分を見つけ、それ以外の部分の違いがないかを判断していきます。

# 与えられた文字列TとT'を比較して正しい変更が行われたか判定する関数
def is_Correct(T, T_prime):
    # TとT'が等しい場合はTrueを返す
    if T == T_prime:
        return True
    
    # T'の長さがTの長さより1大きい場合（1文字挿入の可能性）
    if len(T_prime) - len(T) == 1:
        for i in range(len(T)):
            # 一致しない文字が見つかった場合、挿入された文字以降が一致しているか確認
            if T_prime[i] != T[i]:
                if T_prime[i+1:] == T[i:]:
                    return True
                else:
                    return False
        else:
            return True
    
    # T'の長さがTの長さより1小さい場合（1文字削除の可能性）
    if len(T) - len(T_prime) == 1:
        for i in range(len(T_prime)):
            # 一致しない文字が見つかった場合、削除された文字以降が一致しているか確認
            if T[i] != T_prime[i]:
                if T[i+1:] == T_prime[i:]:
                    return True
                else:
                    return False
        else:
            return True
    
    # TとT'の長さが等しい場合（1文字置換の可能性）
    if len(T) == len(T_prime):
        for i in range(len(T)):
            # 一致しない文字が見つかった場合、それ以降の部分が一致しているか確認
            if T[i] != T_prime[i]:
                if T[i+1:] == T_prime[i+1:]:
                    return True
                else:
                    return False
    return False

# 入力からnとT'を受け取る
n, T_prime = input().split()
n = int(n)

# n個の文字列Sを入力から受け取る
S = [input() for _ in range(n)]

cnt = 0
ans = []

# 各文字列Sに対してis_Correct関数を用いて正しい変更が行われたか判定
# 正しい変更が行われた場合、そのインデックスをansリストに追加し、cntを増やす
for i, s in enumerate(S, start=1):
    if is_Correct(s, T_prime):
        cnt += 1
        ans.append(i)

# 答えを出力
print(cnt)
print(*ans)

以下詳細

is_Correct 関数は、T と T_prime を比較して、特定の条件を満たすかどうかを判定します。
- T と T_prime が等しい場合
  この条件は、最初に T と T_prime が既に等しい場合をチェックしています。つまり、何の変更も加えられておらず、T と T_prime が完全に一致している場合、関数は True を返します。この場合、T と T_prime は同じ文字列です。
- 1文字が挿入された場合
  T_prime が T から1文字挿入された可能性を検証しています。ループを用いて各位置で文字を比較し、異なる文字が見つかった場合、それ以降の文字列が一致しているか確認します。もし一致していれば、True を返します。
- 1文字が削除された場合
  T_prime が T から1文字削除された可能性を検証しています。同様に、各位置で文字を比較し、異なる文字が見つかった場合、それ以降の文字列が一致しているか確認します。もし一致していれば、True を返します。
- 1文字が置換された場合
  T_prime が T から1文字置換された可能性を検証しています。各位置で文字を比較し、異なる文字が見つかった場合、それ以降の文字列が一致しているか確認します。もし一致していれば、True を返します。
- 以上の条件に該当しない場合は、False を返します。これにより、与えられた T と T_prime が、挿入、削除、または置換のいずれかの操作で変換可能な場合に True を返し、それ以外の場合に False を返します。
入力として、最初に整数 n と文字列 T_prime を受け取ります。
次に、n 個の文字列を受け取り、それぞれに対して is_Correct 関数を用いて T と等しい可能性を判定します。条件を満たす場合、その文字列のインデックスを ans リストに追加し、最終的に cnt で条件を満たす文字列の個数を数えます。
最後に、cnt と条件を満たす文字列のインデックスを出力します。

感想

今週もC問題まで解けました！今回のC問題の配点は300点と難易度は先週よりも難しい中で解けたことに非常に満足しています !(^o^)!

B問題は、初めどのように解くか想像ができなかったのですが、問題をよく読み、与えられた数字 N が2と3の乗数から成り立っているところに着目し、Nをそれらで割っていくことで回答を得ることができました。非常にすっきりとした回答ができ、短いコードでも複雑な問題を解くことができるプログラミングの凄さを改めて感じました。

C問題は、まずは問題文通りに実装を行いましたが、TLE(実行時間制限超過)でNGでした。コード実装に間違いがなかったことに小さな喜びを感じつつ、時間節約を検討しました。完全一致で確認を行なっていましたが、1文字以外があっているかを確認することにしました。それでもまだ、TLEでしたので、文字数に着目し、for文を回す前に文字数確認し、適切な条件への振り分けを行いました。それにより、正解まで辿り着くことができました。

Ratingも500点を少し超えることができましたので、この勢いでレベルアップを図っていきたいと思います。

それでは、良い競プロライフを～！(*＾▽＾)／