📘

【競技プログラミング】AtCoder Beginner Contest 032_B問題

2025/01/01に公開

 問題https://atcoder.jp/contests/abc032/tasks/abc032_b

 要約高橋君はパスワードを忘れましたが、ヒントがある：
パスワードは、ある文字列sの長さkの部分文字列のどれか。
高橋君は、可能性のあるパスワードを全て試そうとしている。
ただし、同じパスワードを重複して試す必要はない。
与えられた文字列sに対して、試す必要がある異なるパスワードの数を計算する。
「部分文字列」の定義：
文字列sの連続した一部分を取り出したもの
例：「abc」の部分文字列は「a」,「b」,「c」,「ab」,「bc」,「abc」
「ac」や「ba」のような不連続なものは部分文字列ではない
s: パスワードのヒントとなる文字列
k: パスワードの長さ

 既存投稿一覧ページへのリンク一覧ページ

 アプローチ文字列sから長さkの全ての部分文字列を抽出し、重複を排除してカウントする。

重複排除には辞書（ハッシュテーブル）を使用する。

 解法手順文字列sと整数kを入力として受け取る。
空の辞書Dを作成する。これは異なる部分文字列を格納するために使用する。
文字列sの先頭から順に、長さkの部分文字列を全て抽出する：
インデックスiを0からlen(s)-k+1まで動かす。
各iに対して、s[i]からs[i+k-1]までの文字を連結して部分文字列を作る。
抽出した各部分文字列を辞書Dのキーとして追加する。
値はTrueとするが、実際の値は重要ではない。
辞書を使用することで、自動的に重複が排除される。
最後に、辞書Dの長さ（キーの数）を出力する。
これが、異なるパスワードの可能性の数となる。

 ACコードac.py
def io_func():
    # 文字列sを入力として受け取る
    s = input()
    # 整数kを入力として受け取る
    k = int(input())
    return s, k

def solve(s, k):
    # 空の辞書Dを作成する
    D = dict()

    # 文字列sの先頭から順に、長さkの部分文字列を全て抽出する
    for i in range(len(s) - k + 1):
        # 長さkの部分文字列を作成
        substring = s[i:i+k]
        # 部分文字列を辞書Dのキーとして追加
        D[substring] = True

    # 辞書Dの長さ（キーの数）を出力
    print(len(D))

if __name__=="__main__":
    # メイン処理
    s, k = io_func()
    solve(s, k)

###
# s: 入力された文字列
# k: 部分文字列の長さ
# D: 異なる部分文字列を格納する辞書
# i: 部分文字列の開始位置を示すインデックス
# substring: 抽出された長さkの部分文字列

# 1. io_func関数:
#    - 標準入力から文字列sと整数kを受け取る
#    - 受け取った値を返す
# 2. solve関数:
#    - 空の辞書Dを作成
#    - 文字列sの先頭から順に長さkの部分文字列を抽出
#    - 抽出した部分文字列を辞書Dのキーとして追加
#    - 辞書Dの長さ（異なる部分文字列の数）を出力
# 3. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く

問題

要約

既存投稿一覧ページへのリンク

アプローチ

解法手順

ACコード

Discussion