概要
Python の時間だぜ!
久しぶりにプログラミング問題です。今回はこれ。
No.2021 Not A but B - yukicoder
- インプットとして、
AとBからなる文字列が与えられます (S とする) - あとついでに S の長さも (N とする)
- S の中の2文字を
BBに置き換えてみる - さて、置き換え後の文字列は何パターンになるかな? それを計算するプログラムをつくれ!
- たとえば S が
BBBBBBだったら、どこをBBに換えても何も変わらんので答えは1パターン - たとえば S が
AAAAAAだったら、どこをBBに換えても新しい文字列になるので5パターン
- たとえば S が
どう解くか考える
- S から2文字抜き出したとき、4通りありうる。
"AA""AB""BA""BB" - この4通りをそれぞれ
"BB"へ変更したとき、変更後の文字列パターンは次のように増える。- AA: 絶対1パターン増える
- AB: この AB の直前の文字が “ない (つまり S の先頭ってこと)” か “A” なら1パターン増える
- BA: 絶対1パターン増える
- BB: 最初に登場したときだけ1パターン増える
これで Python を書こう!
書く
まず組み込み関数 input で N, S を取得しよう。
# 長さ N の文字列 S.
N, S = int(input()), input()
余談だけど、インプットをコマンドラインからではなくファイルから取得するならこう↓かな。なんでこんなもんを紹介するかってーと、長すぎるインプットをコマンドライン上からうまく入力することができないからだ。今回の問題なんて、インプットが最大20万文字だからな。ファイルから readlines すれば、スッと入力できるぞ。あくまで自分のぱそこでテストするための施策ね。 yukicoder へ提出するときは input でないとダメだぜ。
with open('./input') as f:
lines = f.readlines()
N, S = int(lines[0]), lines[1]
最終的に提出する数値を初期化しておこう。
answer = 0
“BB: 最初に登場したときだけ1パターン増える” を算出しよう。 Python は list にも str にも in を使える。わかりやすいよね。
if "BB" in S:
answer += 1
ここからは S の中の2文字を先頭から順番に見ていく。で、直前の1文字も算出に使うので、初期化しておく。
previous = None
では、 S の中身を先頭から見ていこう。 “AA, BA: 絶対増える” “AB: 直前の文字次第” を for の中で算出する。
for i in range(N - 1):
# NOTE: ようやく、 Python 3.10 の match を使えるときがきた!
match S[i:i + 2]:
case "AA" | "BA":
answer += 1
case "AB":
if previous in (None, "A"):
answer += 1
case _:
pass
previous = S[i]
以上で計算終了だ。
print(answer)
所感
や〜、今回は大満足! なんといっても、 Python 3.10 で追加された match をようやく使うことができたのが嬉しい。 match を使わず if で書くなら、次のようになる。
letters = S[i:i + 2]
if letters in ("AA", "BA"):
answer += 1
elif letters == "AB" and previous in (None, "A"):
answer += 1
まあ正直コレも好き。でもせっかくある要素だから、使えるところでは積極的に match を使っていこう!
ところで、プログラミング問題に興味のあるみろりHP愛読者諸兄には、 yukicoder をオススメする。このプログラミング問題掲載サイトは、全テストケースと、他の人の回答をを見ることができるのが良い。そん代わり、実績作りにはならないけれどね。緑さんみたいに、プログラミングはただの遊び、っていう連中にオススメだ。
