【ABC345】競プロのA-C問題を40代サラリーマンがPython解説！初心者にもわかりやすく

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 345

A問題：Leftrightarrow

A – Leftrightarrow

問題文(要約)

与えられた文字列Sが、「1つの”<“、複数の”=”、1つの”>”」の順に連なった形（双方向矢印型）かどうか判定する問題です。

解答

import re  # 正規表現モジュールをインポート

# 入力された文字列が双方向矢印型かどうか判定し、結果を出力
print("Yes" if re.match('^<=+>$', input()) else "No")

考え方）

自身の勉強のために、正規表現を用いて説いています。

コード詳細

  1. import re: Pythonの正規表現モジュールをインポートします。このモジュールは文字列処理において非常に強力で、特定のパターンが文字列内に存在するかどうかをチェックするのに使用されます。
  2. re.match('^<=+>$', input())について:
    • この関数は、入力された文字列が特定のパターンに一致するかどうかを判定します。
    • 正規表現'^<=+>$'は、具体的には次の条件を指定しています:
      • ^は文字列の開始を意味します。この記号があることで、パターンが文字列の最初から始まる必要があることを示しています。
      • <は文字列が”<“記号で始まることを要求します。
      • =は”=”記号が少なくとも1回以上続くことを要求します。+は直前の文字（この場合は”=”）が1回以上繰り返されることを意味しています。
      • >は文字列が”>”記号で終わることを要求します。
      • $は文字列の終了を意味します。この記号があることで、パターンが文字列の最後で終わる必要があることを示しています。
    • 結果として、このパターンは文字列が正確に”<“で始まり、1つ以上の”=”が続き、最後に”>”で終わる形式に一致するかどうかを判定します。
  3. print("Yes" if ... else "No"): re.match関数による判定結果に基づいて、条件式を使って結果を出力します。条件がTrue（つまりパターンに一致する場合）であれば”Yes”を、False（一致しない場合）であれば”No”を出力します。

B問題：Integer Division Returns

B – Integer Division Returns

問題

−1018 以上 1018 以下の整数 X が与えられるので、⌈X/10​⌉ を出力してください。
ここで、⌈a⌉ は a 以上の整数のうち最小のものを意味します。

解答

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

# Xに9を加えて10で割り、整数除算により切り上げを行い結果を出力
print((x + 9) // 10)

ポイント）

float型の計算誤差に対応するための問題です。切り上げ(math.ceil)を用いてしまうと計算誤差のため不正解になります。

例）math.ceil(x/10)で計算した場合

　　入力　123456789123456789

　　→ 出力　12345678912345678 　(正解は12345678912345679)

上記を避けるため、自身で切り上げ処理（＋９）を行い商を求めます。

コード詳細

  1. x = int(input()): ユーザーから整数Xを入力として受け取ります。整数型を使うことで、浮動小数点数に関連する誤差を回避します。
  2. (x + 9) // 10: Xに9を加えた後、10で整数除算を行います。これは切り上げ処理に相当します。なぜなら、整数除算では割り切れない場合に小数点以下を切り捨てるため、9を加えることで確実に次の10の倍数に到達し切り捨てられる分を補正します。
  3. print(...): 最終的な結果を出力します。

float型の計算で誤差が発生する理由

  1. コンピュータは数を2進数（0と1のみ）で考えます。10進数の「10」はコンピュータの中では「1010」です。
  2. 10進数の分数（3.14や1/3など）を2進数にすると、きりがなく続くことがよくあります。
  3. コンピュータは無限に続く数字を全部覚えられないので、途中で切ります。これが誤差の始まりです。
  4. float型は、大体の数を覚えるのに使いますが、完璧ではありません。小さい違いが出てくることがあります。
  5. 大きな数や小さな数をたくさん足したり引いたりすると、この小さい違いが大きな差になることがあります。

C問題：One Time Swap

C – One Time Swap

問題(要約)

文字列 S が与えられます。次の操作を ちょうど 1 回 行った後の文字列としてあり得るものがいくつあるか求めてください。

  • S の長さを N とする。 1≤i<j≤N をみたす整数の組 (i,j) を選び、S の i 文字目と j 文字目を入れ替える。

なお、この問題の制約下で操作を必ず行うことができることが証明できます。

解答

from collections import defaultdict

S = input()  # 文字列Sを入力から受け取る

cnt = defaultdict(int)  # 各文字が何回出現したかを数えるための辞書

ans = 0  # 操作後の異なる文字列の総数

# 文字列の各文字についてループ
for j in range(len(S)):
    ans += j - cnt[S[j]]  # 現在の位置jから、その文字がこれまで出現した回数を引く
    cnt[S[j]] += 1  # 出現回数を更新

# 2回以上出現する文字があれば、さらに1を加算
if max(cnt.values()) > 1:
    ans += 1

print(ans)  # 答えを出力


解き方）AtCoderの解説を大いに参考にしました

for文内の ans += j – cnt[S[j]] がポイントになります。この部分は、文字列Sの中で、各文字がそれまでに何回出現したかを数えている操作を行い、さらに詳細に解説すると：

  • 文字列Sを先頭から見ていき、現在の文字の位置をjとします。
  • j番目の文字がこれまでに出現した回数はcnt[S[j]]で確認できます。
  • 初めての文字ならば、cnt[S[j]]は0です。
  • j番目の文字が過去に出現していた場合、その数だけjを減らすと、j番目の文字と入れ替えが可能な異なる文字の数が求まります。

たとえば、”ABACA”という文字列があるとき、3番目の文字Cの位置はj=3です（インデックスは0から数えます）。この時点でAは2回、Bは1回出現していますが、Cはこれが最初の出現なのでcnt['C']は0です。

Cの位置での計算はj - cnt['C']となり、これは3 – 0 = 3です。つまり、Cは自分より前の3つの異なる位置の文字と入れ替えができるため、3つの異なる文字列が生成可能です。

この計算を文字列Sの全ての文字に対して行うことで、1回の操作で作り出せる異なる文字列の総数を数え上げることができます。

解き方(詳細)：

  1. defaultdict(int)を使って、文字が登場した回数を記録する辞書cntを作成します。
  2. 入力された文字列Sの長さだけ繰り返し処理を行います。
  3. forループ内で、j番目の文字について、それまでに同じ文字が出現した回数cnt[S[j]]をjから引き、ansに加算します。これは、それぞれの文字について、自分より前に位置する異なる文字と交換できる回数を数えることに相当します。
  4. cnt[S[j]] += 1で、j番目の文字の出現回数を更新します。
  5. max(cnt.values()) > 1を確認することで、もし2回以上出現する文字があれば（すなわち入れ替えても同じ文字列になる場合）、それを補正してansに1を加えます。これは、同じ文字が複数ある場合には、それらの文字を入れ替えても新しい文字列が生まれないため、1つの新しい組み合わせが可能になることを考慮しています。
  6. 最終的な異なる文字列の総数ansを出力します。

感想

今回は、B問題までしか解けませんでした。

A問題は、文字列がパターンを満たしているかを問う問題でした。最近勉強中の正規表現を使って解くことができました。正規表現の汎用性と強力さをこの問題で実感できました。

B問題は、float型の計算誤差を考慮が必要な問題でした。問題は非常にシンプルでx/10の切り上げた整数を回答するだけです。今回、私は解答例として+9する切り上げ手法を学びました。コンテスト中は、この切り上げ処理を思いつくことができず、文字列として扱いつつ、最後の桁処理を条件分岐で対応しました（力技）。答えに辿り着けたことには満足していますが、もっと効率的な方法を次回は見つけたいと思います。

C問題については、一文字を一回だけ入れ替えて、新しい組み合わせを作り出す方法を見つけるのが難しくて手をつけられませんでした。全ての文字の位置を検索し尽くす方法で挑戦しましたが、制限時間超過で解決には至りませんでした。しかし、答えを見返して、各文字の出現位置と可能な置換回数を効率的に数える方法を学び、このような問題に対する新しいアプローチを得ることができました。

B問題までしか回答できていなかったこともあり、残念ながらレーティングが少し下がり、504まで落ちてしまいました。来週もこのエキサイティングな挑戦を楽しんで続けたいと思います。

それでは、皆さんも競プロライフを楽しんでくださいね！(*＾▽＾)／

コメント

タイトルとURLをコピーしました