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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 342

A問題：Yay!

A – Yay!

問題文

英小文字からなる文字列 S が与えられます。ここで S の長さは 3 以上 100 以下です。

S はある 1 文字を除いて全て同じ文字で構成されています。

他のどの文字とも異なる文字は前から何文字目でしょうか。

解答

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

for i in range(2):  # 最初の2文字についてループ
    replaceS = S.replace(S[i], "")  # 文字列Sからi番目の文字を削除
    if len(replaceS)==1:  # 削除後の文字列の長さが1ならば（唯一異なる文字が見つかった）
        print(S.index(replaceS)+1)  # その異なる文字の位置（1始まり）を出力
        exit()  # プログラムを終了

考え方）

下記の考え方を用いて解いています。

  • 一文字だけ違うところに着目 -> 共通文字を空白に置換を行えば一文字だけ残る
  • 先頭が違う文字の可能性もあるため、置換後の文字列長さを確認
  • 上記で長さが2以上だったら、2文字目で置換を行う
  • 違う文字を抽出できたら、その文字のインデックス番号を取得（０始まりは注意が必要）

コード詳細

  1. 入力から文字列Sを受け取ります。
  2. 文字列Sの最初の2文字について、それぞれの文字をSから全て削除した新しい文字列を作成します。
  3. その新しい文字列の長さが1であれば、それは唯一異なる文字が残ったことを意味します。
  4. 唯一異なる文字の位置を1始まりで出力します。
  5. プログラムを終了します。

B問題：Which is ahead?

B – Which is ahead?

問題

N 人が 1 列に並んでおり、前から i 番目に並んでいる人は人 Pi​ です。

Q 個のクエリを処理して下さい。i 番目のクエリは以下のものです。

  • 整数 Ai​,Bi​ が与えられる。人 Ai​ と人 Bi​ のうち、より前に並んでいる人の番号を出力せよ。

解答

n=int(input())  # 並んでいる人の数Nを入力から受け取る
P=list(map(int,input().split()))  # 並んでいる人々の番号をリストPに格納
q=int(input())  # クエリの数Qを入力から受け取る

for _ in range(q):  # Q個のクエリについてループ
    a,b=map(int,input().split())  # クエリに含まれる2つの番号AとBを受け取る
    print(P[min(P.index(a),P.index(b))])  # AとBのうち、より前に並んでいる人の番号を出力

解き方）

N≦100と制限が小さいため、素直に解いています。

print文の中にまとめていますが、下記の動作を行うことにより答えを導いています。

  • P.index(a) と P.index(b) で、a と b がリスト P の中で最初に現れるインデックスをそれぞれ取得します。
  • min(P.index(a), P.index(b)) で、これら二つのインデックスのうち小さい方、つまり列において前にいる人のインデックスを取得します。
  • そのインデックスを使用して P[...] から、その人の番号を取得し出力します。

コード詳細

  1. 入力から並んでいる人の数Nを受け取ります。
  2. 並んでいる人々の番号をスペース区切りで入力し、リストPに格納します。
  3. クエリの数Qを入力から受け取ります。
  4. Q回のクエリについて繰り返します。
  5. 各クエリでは、2つの番号AとBを入力から受け取ります。
  6. AとBのうち、リストPでより前にある番号（つまり、リストPにおけるインデックスが小さい方）を出力します。

C問題：Many Replacement

C – Many Replacement

問題

英小文字からなる長さ N の文字列 S が与えられます。

文字列 S に対して操作を Q 回行います。 i 回目 (1≤i≤Q) の操作は文字の組 (ci​,di​) で表され、次のような操作に対応します。

  • S に含まれる文字 ci​ をすべて文字 di​ で置き換える。

すべての操作が終わったあとの文字列 S を出力してください。

解答

n=int(input())  # 文字列の長さNを入力から受け取る
S=input()  # 文字列Sを入力から受け取る
q=int(input())  # 操作の回数Qを入力から受け取る

az_from="abcdefghijklnmopqrstuvwxyz"  # 置き換え元の英小文字リスト
az_to  ="abcdefghijklnmopqrstuvwxyz"  # 置き換え先の英小文字リスト（初期状態）

for _ in range(q):  # Q回の操作についてループ
    c,d=input().split()  # 操作で置き換える文字の組を入力から受け取る
    az_to = az_to.replace(c,d)  # 置き換え先のリストを更新

print(S.translate(str.maketrans(az_from,az_to)))  # 最終的な置き換えを行い、結果を出力


解き方）

与えられる文字列Sの長さが N ≦ 2 x 105 と非常に長いため、この文字列を毎回置換すると制限時間超過になってしまいます。そのため、下記の手順で解いています。

  • 変換用のアルファベットの一覧表を作成
  • 作成したアルファベット一覧表にクエリを適用
  • 変換前後のアルファベットテーブルを作成
  • 変換テーブルを用いて、文字列Sを置換

変換用のアルファベットの一覧表に対して、今回のクエリを適用していきます。

  1. 文字列の長さNを入力から受け取ります。
  2. 文字列Sを入力から受け取ります。
  3. 操作の回数Qを入力から受け取ります。
  4. 英小文字のリストをaz_from（置き換え元）とaz_to（置き換え先）で用意します。
  5. Q回の操作について、各操作で指定された文字の組(c, d)を受け取ります。
  6. 操作に応じて、az_toリスト内の文字cをdで置き換えます。これにより、置き換え先のリストaz_toが最終的な置き換えパターンを反映します。
  7. str.maketrans(az_from, az_to)で置き換え元と置き換え先のリストを基に変換表を作成し、S.translate(...)で文字列Sに対して一括で置き換えを行います。
  8. 置き換えが完了した文字列Sを出力します。

感想

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

A問題は、通常よりも難易度が高めの問題でした。この問題では、文字列内の1文字だけが異なる文字を見つけ出し、その位置を特定する必要がありました。1文字の違いに注目し、文字の置換と文字列の長さを基に判断しました。最初は、異なる1文字を出力する問題だと誤解してしまい、不正解となりました。問題文をしっかり読むことの重要性を再認識しました。

B問題に関しては、インデックス番号を利用することで解決することができました。与えられた2つの値からインデックス番号を求め、その後、再び値に戻して出力するというステップを踏みました。この問題では、問題文の意図を理解し、求められた値を正確に出力することができました。

C問題は、文字列操作がテーマの問題でした。直接的な解答方法だと文字数が多く、処理時間が制限を超えてしまい不正解になりました。そこで、高速化のために辞書型を用いてクエリを先に処理し、変換の手順を短縮するアプローチを試みました。しかし、文字の順序を変えてしまったため、変換後の前後関係が狂い、正解にたどり着くことができませんでした。

C問題の正解は、アルファベットの一覧表を用いた変換テーブルで置換を行う方法でした。このアプローチは私にとって新しく、他の問題にも応用できると感じたため、大変有意義な学びとなりました。

今回はオンタイムでの参加が叶わず、レーティングの変動はありませんでしたが、来週に向けて頑張りたいと思います。

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

コメント

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