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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 344

A問題：Spoiler

A – Spoiler

問題文

英小文字と | のみからなる文字列 S が与えられます。S は | をちょうど 2 個含むことが保証されます。

2 つの | の間にある文字および | を S から削除した文字列を出力してください。

解答

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

# 入力された文字列に対して、2つの "|" とその間にある任意の文字を空文字列で置換し、結果を出力
print(re.sub("\|.*\|", "", input()))

考え方）

自身の勉強のために、正規表現を用いて説いています。
（コンテスト中は、for文を回して二つの | の位置を探していました）

コード詳細

  1. import re はPythonの正規表現モジュールreをインポートするコマンドです。このモジュールを使って文字列の検索や置換を行います。
  2. re.sub(pattern, repl, string) 関数は、string内のpatternにマッチする部分をreplに置換します。ここで"\|.*\|"がパターン、""が置換後の文字列（空文字列）、input()がユーザーから入力された文字列です。
    • \|は正規表現で特別な意味を持つ|文字をエスケープし、文字そのものとして扱うためにバックスラッシュ\を使用します。正規表現内で|は「または」を意味するため、文字|を検索対象とするにはエスケープが必要です。
    • .*は任意の文字が0回以上繰り返すことを意味します。つまり、2つの|の間にあるどんな文字列もマッチします。
    • このコードは、2つの|とその間にある任意の文字列を空文字列で置換（削除）し、残った文字列を出力します。

B問題：Delimiter

B – Delimiter

問題

N 個の整数 A1​,A2​,…,AN​ が、 1 行に 1 つずつ、 N 行にわたって与えられます。但し、 N は入力では与えられません。
さらに、以下が保証されます。 

AN​,AN−1​,…,A1​ をこの順に出力してください。

解答

A = []  # 整数を格納するリストを初期化

while True:  # 無限ループを開始
    a = int(input())  # ユーザーから整数を入力してもらう
    A.append(a)  # 入力された整数をリストに追加
    if a == 0:  # もし入力された整数が0なら
        break  # ループを抜ける

for a in reversed(A):  # リストを逆順にして各要素に対して
    print(a)  # 要素を出力

解き方）

while文で無限ループを作り、取り込んだ値が0かどうかを判断してループを抜けるようにしています。

コード詳細

  1. 最初に空のリスト A を作成します。これは入力された整数を格納するために使用します。
  2. 無限ループ (while True:) を開始します。このループは、0が入力されるまで続きます。
  3. ユーザーから整数 a を入力してもらい、int(input()) を使用して整数に変換します。
  4. 入力された整数 a をリスト A に追加します (A.append(a))。
  5. もし入力された整数 a が0 (if a == 0:) であれば、ループを終了します (break)。これは、問題文における条件 AN​=0 を満たす整数が入力されたサインです。
  6. ループを抜けた後、リスト A を逆順にします (reversed(A)) そして、逆順にしたリストの各要素を1つずつ出力します (print(a))。

別解）

import sys  # システム関連の操作に使われるモジュールをインポート

# 標準入力から読み込んだ各行をリストに格納し、逆順にして1行ずつ出力
for l in reversed([line.strip() for line in sys.stdin]):
    print(l)

Pythonの標準ライブラリであるsysモジュールをインポートすることにより、終わりの行数を気にすることなく取り込むことができます。

.strip() メソッドは、先頭と末尾の空白文字（改行文字を含む）を削除しています

C問題：A+B+C

C – A+B+C

問題(要約)

3 個の数列 A=(A1​,…,AN​),B=(B1​,…,BM​),C=(C1​,…,CL​) が与えられます。

さらに数列 X=(X1​,…,XQ​) が与えられるので、各 i=1,…,Q に対して次の問題を解いてください。

問題：A,B,C からそれぞれ 1 個ずつ要素を選び、和を Xi​ にすることができるか？

解答

n = int(input())  # 数列 A の要素数
A = list(map(int, input().split()))  # 数列 A

m = int(input())  # 数列 B の要素数
B = list(map(int, input().split()))  # 数列 B

l = int(input())  # 数列 C の要素数
C = list(map(int, input().split()))  # 数列 C

q = int(input())  # 数列 X の要素数
X = list(map(int, input().split()))  # 数列 X

numbers = set()  # A, B, C から選んだ要素の和を格納する集合

# A, B, C の各要素から1つずつ選んで和を計算し、その和を numbers 集合に追加
for a in A:
    for b in B:
        for c in C:
            numbers.add(a + b + c)

# 数列 X の各要素が numbers 集合に含まれているかどうかを判断し、結果を出力
for x in X:
    print("Yes" if x in numbers else "No")


解き方）

Xに着目するのではなく、事前に配列A, B, Cの全組み合わせの和を集合に登録することがポイントになります。この集合ができれば、各Xが集合に含まれるかどうかの検索だけで済みます。

Xに着目して計算してしまうと、Xi ≦ 3 x 108 と非常に大きく制限時間超過になります。

  1. 数列 A, B, C の要素数と要素自体を入力から読み込みます。これらの数列は、それぞれの要素を選んで和を計算するために使用されます。
  2. 同様に、数列 X の要素数と要素を読み込みます。この数列は、A, B, C から選んだ要素の和として表せるかどうかを判断するための基準となります。
  3. numbers 集合を初期化します。これは、A, B, C の各要素から1つずつ選んで計算したすべての可能な和を格納するために使用します。
  4. A, B, C の各要素から1つずつ選んで和を計算し、その和を numbers 集合に追加します。これにより、すべての可能な和が numbers 集合に格納されます。
  5. 数列 X の各要素について、その要素が numbers 集合に含まれているかどうかを判断します。含まれていれば、その要素を和として表すことができるため “Yes” を出力し、そうでなければ “No” を出力します。

感想

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

A問題では、文字列から | (パイプ) に囲まれた部分を取り除くという文字操作が問題でした。私はfor文を使ってパイプを2箇所特定し、その間の文字を削除する方法でアプローチしました。解説を見ると、.split(“|”) や正規表現を駆使することで、より簡潔に解けたことを知りました。特に正規表現に関しては、汎用性が高いと思いますので、この解き方を覚えていきたいと思います。

B問題は、入力数が初めに明示されていないところをどのように扱うかの問題でした。whileで無限ループを作って、0 で抜けることにより簡単に解けました。sys.stdin()を使うと入力行数に関係なく使えるので、こちらのやり方も今後のために覚えておきたいと思います。

C問題は、着目点が重要な問題でした。問題の通りに求める解Xiが実現性があるかを確認していくと、制限時間超過になってしまいました。この考えのまま時間削減を検討しましたが、正解に辿り着けませんでした。改めて、制約条件などを確認し、事前にすべてのパターンを準備しておく解に辿り着けました。今後、この考えをすぐに思いつけるようにしていきたいと思います。

C問題に時間を取られた結果、残念ながらレーティングが少し下がり、515まで落ちてしまいました。来週も楽しみながら解いていきたいと思います。

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

コメント

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