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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 347

A問題：Divisible

A – Divisible

問題文(要約)

正整数 N,K 及び長さ N の数列 A=(A1​,A2​,…,AN​) が与えられます。

A に含まれる要素のうち、K の倍数であるもののみを全て取り出し、それらを K で割って出力してください。

解答

# 入力値を受け取る
n,k=map(int,input().split())  # nとkを入力から受け取る
A=list(map(int,input().split()))  # 数列Aを入力から受け取る

ans=[]  # 答えを格納するリスト

# 数列Aの各要素についてループ
for a in A:
    if a % k == 0:  # 要素がKで割り切れるかチェック
        ans.append(a//k)  # 割り切れる場合、Kで割った結果をansに追加

print(*ans)  # 結果を出力

考え方）

数列Aの中を一つづつkで割り切れるかを確認し、割り切れた場合はkで割った数をansの配列に追加していきます。

コード詳細

  1. 最初に、入力された N と K、そして数列 A を受け取ります。
  2. 結果を格納するための空のリスト ans を用意します。
  3. 次に、数列 A の各要素に対して、K で割り切れるかどうかを確認します。
  4. もし K で割り切れるなら、その要素を K で割った結果を ans リストに追加します。
  5. 最後に、ans リストに格納された全ての要素を出力します。

B問題：Piano

B – Piano

問題

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

解答

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

words = set()  # 重複を避けるため、部分文字列を格納するセット

# 文字列Sの全ての可能な部分文字列を探索
for i in range(len(S)+1):
    for j in range(i+1,len(S)+1):
        words.add(S[i:j])  # 部分文字列をセットに追加

print(len(words))  # 部分文字列の総数を出力

ポイント）

スライスの機能を用いて部分文字列を作り、集合に格納することにより重複を避けていきます。

コード詳細

  1. 入力された文字列 S を受け取ります。
    • 例えば、S = "abc" とします。
  2. 重複しない部分文字列を保持するために、セット words を初期化します。
    • Pythonのセットは、重複する要素を自動的に取り除いてくれる特性があります。
  3. 文字列 S の全範囲を走査するために二重ループを使用します。
    • 外側のループ（i のループ）では、部分文字列の開始位置を選びます。i は0から文字列の長さまでを指します。
      • 例: S = "abc" の場合、i は0 (文字列の最初) から3 (文字列の長さ) までを取ります。
    • 内側のループ（j のループ）では、i の位置から文字列の終わりまでを走査し、部分文字列の終了位置を選びます。
      • j は i+1 から始まります。これは、少なくとも1文字を含む部分文字列を保証するためです（空ではない部分文字列）。
      • j は文字列の長さ (len(S)+1) までを取ります。これにより、文字列の最後までの部分文字列をすべて含めることができます。
  4. S[i:j] を使用して、開始位置 i と終了位置 j の間の部分文字列を取り出し、セット words に追加します。
    • このステップで、文字列の全ての可能な部分文字列がセットに追加されます。例えば、S = "abc" の場合、"a", "ab", "abc", "b", "bc", "c" のようになります。
  5. セット words に含まれる要素の数、つまり部分文字列の総数を出力します。
    • この数が、与えられた文字列 S の空ではない部分文字列がいくつあるかの答えです。

C問題：Ideal Holidays

C – Ideal Holidays

問題(要約)

AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。

高橋くんは N 個の予定があり、i 番目の予定は今日から Di​ 日後です。

高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。

解答

n,a,b = map(int,input().split())  # 入力：予定の数、休日の日数、平日の日数
D = list(map(int,input().split()))  # 各予定が何日後かのリスト

NumWeek = set()  # 週のうちの日数を表すセット

# 予定の日を週の周期で計算し、結果をセットに追加
for d in D:
    NumWeek.add(d%(a+b))

# 予定が全て休日に収まるかどうかの判断
if max(NumWeek) - min(NumWeek) < a:
    print("Yes")
else:
    maxGap = 0
    sortedNumWeek = sorted(NumWeek)  # セットをソート
    # ソートされたリストの隣接する要素間の最大のギャップを計算
    for i in range(len(NumWeek)-1):
        gap = sortedNumWeek[i+1] - sortedNumWeek[i]
        maxGap = max(maxGap, gap)
    
    # 最大ギャップが平日の日数より大きいか判定
    if maxGap > b:
        print("Yes")
    else:
        print("No")

ポイント）

基本的な考え方：通常の1週間（月曜から日曜で土日が休み、つまりA=2, B=5のパターン）で考えて、各予定が週の何日目にあたるかを(A+B)で割った余りで求めます。

  1. 1日目が土曜日の場合：
    • 週の番号が1, 2の範囲内になれば、全ての予定が休日です。
    • このチェックは、週番号の最大値 - 週番号の最小値 < Aで可能です。
  2. 1日目が水曜日の場合：
    • 週の番号が4, 5の範囲内になれば、全ての予定が休日です。
    • 同じく、週番号の最大値 - 週番号の最小値 < Aで確認できます。
  3. 1日目が日曜日の場合：
    • 週の番号が0, 6の範囲内になれば、全ての予定が休日です。
    • ただし、週番号の最大値 - 週番号の最小値 < Aはここでは直接的な意味を持ちません。
    • この場合、平日区間に数字がないことで休日であることを判断します。つまり、週番号をソートして、隣り合う数字間のギャップが5日より大きければ、そのギャップは休日を含むことを意味します。

解き方(詳細)：

  1. 入力された N, A, B と各予定 D_i を受け取ります。
    • ここで、A=2 (休日の日数)、B=5 (平日の日数) とします。
  2. 週の中での日付を表すセット NumWeek を初期化します。
    • このセットは、予定の日付が週の中でどの位置にあるかを追跡します。
  3. 各予定 D に対して、A+B の周期でその日が何日目にあたるか計算し、NumWeek に追加します。
    • これにより、予定が週のどの日にあたるか（例: 月曜から始まると仮定した場合の日数）を特定します。
  4. NumWeek の中で最大値と最小値の差が A 未満であれば、すべての予定が休日に収まるため Yes を出力します。
    • つまり、予定が連続した2日間の休日内に収まる場合、全て休日になり得ます。
  5. それ以外の場合、NumWeek をソートし、ソートされたリストで隣接する要素間の最大ギャップを求めます。
    • このステップは、予定間に平日が挟まれていないかをチェックします。
  6. もし最大ギャップが B より大きければ、すべての予定が連続する休日に収まる可能性があるため Yes、そうでなければ No を出力します。
    • これは、予定間のギャップが5日間の平日よりも長ければ、少なくとも1つの休日がギャップ内に含まれることを意味します。

感想

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

A問題は、for文とif文とリストを組み合わせた基本的な問題でしたので、すぐに解くことができました。

B問題では、文字列操作のスライスと集合を上手く利用することで解けましたが、スライスの開始位置と終了位置を決定する際に苦労しました。具体的には、リストの範囲をどのように指定するかでつまずきました。スライスの基本をしっかり復習し、次回はスムーズに解けるようになりたいです。

C問題では、特定の予定が休日に当たるかどうかを判断するという課題に直面しました。挑戦の中で最大の難点は、今日が週のうちの何日目にあたるか不明であることでした。初期のアプローチでは、休日が連続する日に限定して考えてしまい、その視野の狭さから解法に至ることができませんでした。時間がなくなるまでこの視点から脱却できず、大きな学びの機会となりました。

B問題までは素早く解け、C問題はみな苦戦していたこともあり、レーティングがほぼ変わらずの517になりました。来週もこのエキサイティングな挑戦を楽しんで続けたいと思います。

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

コメント

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