こんにちは、こんぶちゃ(茶コーダー)です!
初心者視点から競プロAtCoderのABC342のA問題〜C問題の自身の解答と解答説明をしていきます。
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援&ご助言頂けば嬉しいです。
では早速行ってみましょう!
今回の参加コンテスト(ABC342)
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文字目で置換を行う
- 違う文字を抽出できたら、その文字のインデックス番号を取得(0始まりは注意が必要)
コード詳細
- 入力から文字列Sを受け取ります。
- 文字列Sの最初の2文字について、それぞれの文字をSから全て削除した新しい文字列を作成します。
- その新しい文字列の長さが1であれば、それは唯一異なる文字が残ったことを意味します。
- 唯一異なる文字の位置を1始まりで出力します。
- プログラムを終了します。
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[...]
から、その人の番号を取得し出力します。
コード詳細
- 入力から並んでいる人の数Nを受け取ります。
- 並んでいる人々の番号をスペース区切りで入力し、リストPに格納します。
- クエリの数Qを入力から受け取ります。
- Q回のクエリについて繰り返します。
- 各クエリでは、2つの番号AとBを入力から受け取ります。
- AとBのうち、リストPでより前にある番号(つまり、リストPにおけるインデックスが小さい方)を出力します。
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を置換
変換用のアルファベットの一覧表に対して、今回のクエリを適用していきます。
- 文字列の長さNを入力から受け取ります。
- 文字列Sを入力から受け取ります。
- 操作の回数Qを入力から受け取ります。
- 英小文字のリストを
az_from
(置き換え元)とaz_to
(置き換え先)で用意します。 - Q回の操作について、各操作で指定された文字の組
(c, d)
を受け取ります。 - 操作に応じて、
az_to
リスト内の文字c
をd
で置き換えます。これにより、置き換え先のリストaz_to
が最終的な置き換えパターンを反映します。 str.maketrans(az_from, az_to)
で置き換え元と置き換え先のリストを基に変換表を作成し、S.translate(...)
で文字列Sに対して一括で置き換えを行います。- 置き換えが完了した文字列Sを出力します。
感想
今回は、B問題までしか解けました。
A問題は、通常よりも難易度が高めの問題でした。この問題では、文字列内の1文字だけが異なる文字を見つけ出し、その位置を特定する必要がありました。1文字の違いに注目し、文字の置換と文字列の長さを基に判断しました。最初は、異なる1文字を出力する問題だと誤解してしまい、不正解となりました。問題文をしっかり読むことの重要性を再認識しました。
B問題に関しては、インデックス番号を利用することで解決することができました。与えられた2つの値からインデックス番号を求め、その後、再び値に戻して出力するというステップを踏みました。この問題では、問題文の意図を理解し、求められた値を正確に出力することができました。
C問題は、文字列操作がテーマの問題でした。直接的な解答方法だと文字数が多く、処理時間が制限を超えてしまい不正解になりました。そこで、高速化のために辞書型を用いてクエリを先に処理し、変換の手順を短縮するアプローチを試みました。しかし、文字の順序を変えてしまったため、変換後の前後関係が狂い、正解にたどり着くことができませんでした。
C問題の正解は、アルファベットの一覧表を用いた変換テーブルで置換を行う方法でした。このアプローチは私にとって新しく、他の問題にも応用できると感じたため、大変有意義な学びとなりました。
今回はオンタイムでの参加が叶わず、レーティングの変動はありませんでしたが、来週に向けて頑張りたいと思います。
それでは、皆さんも競プロライフを楽しんでくださいね!(*^▽^)/
コメント