【paiza問題集解説】メニュー

paiza2025

text = 'paiza2025'
print(text)

ABCカウント

例１

_ = input()
c = input().split()

cnt_a = 0
cnt_b = 0
cnt_c = 0
for char in c:
    if char == 'A':
        cnt_a += 1
    elif char == 'B':
        cnt_b += 1
    elif char == 'C':
        cnt_c += 1

print(cnt_a)
print(cnt_b)
print(cnt_c)

例２

_ = input()
c = input().split()

abc = [0, 0, 0]
for char in c:
    if char == 'A':
        abc[0] += 1
    elif char == 'B':
        abc[1] += 1
    elif char == 'C':
        abc[2] += 1

for result in abc:
    print(result)

例３

_ = input()
c = input().split()

cnt = {'A': 0, 'B': 0, 'C': 0}
for char in c:
    if char in cnt.keys():
        cnt[char] += 1

print(*cnt.values(), sep='\n')

カウンターの保存方法が異なるだけで、どれも出現した文字ごとにただカウントしているだけです。Ｄランク問題なので例１でも十分胸張れます。😁

円卓のk番目

n, k = map(int, input().split())
print((k-1) % n + 1)

k を n で割った余りを計算すると、n 番目の席が０番目になってしまいます。その為に１番目から数える円卓を０番目から数えるようにしておきます。

k → k - 1

この状態で n で割った余りは、1 を引いて円卓を０番目から数えているものなので、今度は 1 を足して１番目から数えるものに戻します。

(k-1) % n → (k-1) % n + 1

n = 5, k = 8 の時

１２３４５６７８
↓ (k-1)
０１２３４５６７
↓ (k-1) % n
０１２３４０１２
↓ (k-1) % n + 1
１２３４５１２３

3

実際は末尾の数である k だけ使って処理していますので、

８
↓ (8-1)
７
↓ (7) % 5
２
↓ 2 + 1
３

となっています。

素数

この問題の解説は【paizaの森練習問題コンテスト過去問題セット11】の素数判定を参照してください。

視界の広さ

def dfs(y, x):
    if (0 <= y < H and 0 <= x < W) and s[y][x] == '.':
        s[y][x] = 'V'        
        dfs(y + ny, x + nx)
    return


H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

any((loc:=(h, w)) for h in range(H) for w in range(W) if s[h][w] == 'A')
NSEW = ((-1, 0), (1, 0), (0, 1), (0, -1))

y, x = loc
for ny, nx in NSEW:
    dfs(y + ny, x + nx)

for line in s:
    print(*line, sep='')

深さ優先探索(DFS)を使って解いたものです。

マップは後に一部を書き換える予定ですので、文字列からリストに変換しておきます。

any() 関数では A さんがいる座標を取得しています。DFS の見通しを良くする為、そして重要度が低いので、今回は一行にまとめてしまいました。

NSEW といういい加減でふざけた名前の変数は、探索方向の移動マスを表しています。北南東西の順に動いていきます。私がよく使うこの変数の命名はいつもこんなテキトーで、順番も NESW になったり NEWS になったりと定まっていません。😅 一応移動順通りに合わせて並べてはいます。

それではいよいよ DFS に参りましょう。

y, x = loc
for ny, nx in NSEW:
    dfs(y + ny, x + nx)

初めは北方向、次に南、東、西の順で向いていきます。引数には移動済みの値を渡しています。

　が現在地。

TTTTTTTTTT TTTTTT...T T......... TT....A..T T....T...T T...T....T T........T T........T T..T.....T T........T

def dfs(y, x):
    if (0 <= y < H and 0 <= x < W) and s[y][x] == '.':
        s[y][x] = 'V'        
        dfs(y + ny, x + nx)
    return

現在地がマップの範囲内であり、現在地が '.' の時は、現在地を 'V' に書き換えます。

TTTTTTTTTT TTTTTT...T T.....V... TT....A..T T....T...T T...T....T T........T T........T T..T.....T T........T

これをマップの端からはみ出るか、もしくは '.' ではない所、つまり 'T' の位置になるまで繰り返します。繰り返しは再帰を使います。最初に dfs() 関数を呼び出した時のように、１つ移動後の座標を引数として与えます。

　が現在地。

TTTTTTTTTT TTTTTTV..T T.....V... TT....A..T T....T...T T...T....T T........T T........T T..T.....T T........T

北は 'T' に当たったので、北向きを探索していた関数を全て終了し、 dfs() 関数を一番最初に呼び出した所まで戻ります。

def dfs(y, x):
    if (0 <= y < H and 0 <= x < W) and s[y][x] == '.':
        s[y][x] = 'V'        
        dfs(y + ny, x + nx)
    return


H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

any((loc:=(h, w)) for h in range(H) for w in range(W) if s[h][w] == 'A')
NSEW = ((-1, 0), (1, 0), (0, 1), (0, -1))

y, x = loc
for ny, nx in NSEW:
    None  # ←←←←←←← ココに戻る

for line in s:
    print(*line, sep='')

次は南向きです。

TTTTTTTTTT TTTTTTV..T T.....V... TT....A..T T....T...T T...T....T T........T T........T T..T.....T T........T

同じ様に '.' を 'V' に書き換えていきます。

TTTTTTTTTT TTTTTTV..T T.....V... TT....A..T T....TV..T T...T.V..T T.....V..T T.....V..T T..T..V..T T.....V..T

マップからはみ出たので、南向きの探索は終了します。

東と西も同じ様に探索をし、全４方向の探索を済ませると、求めるマップが完成します。

TTTTTTTTTT TTTTTTV..T T.....V... TTVVVVAVVT T....TV..T T...T.V..T T.....V..T T.....V..T T..T..V..T T.....V..T

　は書き換えた所。

paiza 解答コード例のように、DFSを使わなくても余裕でクリアできてしまいます。Ｂランク上がりたてレベルなら構いませんが、Ａランク以上を目指すなら再帰関数、深さ優先探索(DFS)は余裕で書けるようにたくさん書いて慣らしておきましょう。😉

いきなり完璧を目指すより、うまく動かなくて試行錯誤している時が一番理解しやすいので、悩むより手を動かしてたくさん書きまくりましょう！

集合体の数

例１

def bfs(h, w, group):
    locates = {(h, w)}
    while locates:
        y, x = locates.pop()
        s[y][x] = '*'
        for ny, nx in NSEW:
            yy = y + ny
            xx = x + nx
            if s[yy][xx] == group:
                locates.add((yy, xx))
    return 1
    

H, W = map(int, input().split())
s = [['#'] * (W+2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#'] * (W+2)]

NSEW = ((-1, 0), (1, 0), (0, 1), (0, -1))
cnt = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if 'A' <= s[h][w] <= 'E':
            cnt += bfs(h, w, s[h][w])

print(cnt)

例２

def bfs(h, w, group):
    locates = {(h, w)}
    while locates:
        y, x = locates.pop()
        s[y][x] = '*'
        for ny, nx in NSEW:
            yy = y + ny
            xx = x + nx
            if (0 <= yy < H and 0 <= xx < W) and s[yy][xx] == group:
                locates.add((yy, xx))
    return 1
    

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

NSEW = ((-1, 0), (1, 0), (0, 1), (0, -1))
cnt = 0
for h in range(H):
    for w in range(W):
        if 'A' <= s[h][w] <= 'E':
            cnt += bfs(h, w, s[h][w])

print(cnt)

例１と例２はほぼ同じことをしています。例２は座標がマップの範囲内かどうかを都度チェックしてます。例１はマップの周りを '#' でぐるっと囲むことで、都度座標が範囲内かどうかのチェックを省いています。どちらも幅優先探索(BFS)アルゴリズムを使用しています。

問題には A 〜 E の記号の集合体は各１つずつしか存在しないとはとくに書かれていませんが、１つしかない場合は隣接する１つを見つければ良いだけで超簡単になってしまうので・・・違うな、もっと簡単に A 〜 E の１文字を見つければいいだけになりますので、多分複数あると思います。😅

こんな感じで。

AAA BAB BAB

A が１つ、B が２つで計３つ。

例１を用いて解説します。

def bfs(h, w, group):
    locates = {(h, w)}
    while locates:
        y, x = locates.pop()
        s[y][x] = '*'
        for ny, nx in NSEW:
            yy = y + ny
            xx = x + nx
            if s[yy][xx] == group:
                locates.add((yy, xx))
    return 1
    

H, W = map(int, input().split())
s = [['#'] * (W+2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#'] * (W+2)]

NSEW = ((-1, 0), (1, 0), (0, 1), (0, -1))
cnt = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if 'A' <= s[h][w] <= 'E':
            cnt += bfs(h, w, s[h][w])

print(cnt)

このプログラムでマップを取り込むと、こんな感じになります。

##### #AAA# #BAB# #BAB# #####

'#' の壁でマップを囲います。

cnt = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if 'A' <= s[h][w] <= 'E':
            cnt += bfs(h, w, s[h][w])

の二重ループで、マップ内部の左上から座標を動かしていきます。A 〜 E の文字を見つけたら幅優先探索(BFS)の開始です。

##### #AAA# #BAB# #BAB# #####

いきなり見つけちゃうんだけどね！
bfs() 関数の引数には、現在の座標とその位置の文字を与えます。

bfs(1, 1, 'A')

def bfs(h, w, group):
    locates = {(h, w)}  # ・・・ (※１)
    while locates:  # ・・・ (※２)
        y, x = locates.pop()  # ・・・ (※３)
        s[y][x] = '*'  # ・・・ (※４)
        for ny, nx in NSEW:  # ・・・ (※５)
            yy = y + ny
            xx = x + nx
            if s[yy][xx] == group:  # ・・・ (※６)
                locates.add((yy, xx))
    return 1  # ・・・ (※７)

渡された引数の h と w は、関数内で座標としてタプルにします。そしてさらにそのタプルをセットに収めます。
次のループで BFS を行います。条件の locates は、探索する座標リストが収められています。最初は (1, 1) だけが入っていますが、探索していくとこの中の要素が増減します。そして locates の中身が空になったらループを抜けます。
セットの中からタプルになっている座標を取り出し、y と x にアンパック代入します。
現在の座標をチェック済みとして '*' に置き換えます。
このループで上下左右の文字をチェックします。ここが BFS の心臓部です。
この文では、 group と同じ文字を見つけたら、その座標を locates に格納します。このループを抜けた後、この座標に移動してまた同じ様に周辺の文字を探索していきます。
最初の座標に繋がる文字の全ての座標を探索し終えたら(locates が空)、カウント +1 の意味の 1 を戻り値としてこの関数を終了します。

これらを実際にマップを見ながら流れを見てみましょう。
まずはスタート位置です。

##### #AAA# #BAB# #BAB# #####

bfs(1, 1, 'A') を呼び出し、BFS を開始。

locates から .pop() し、次の探索を始める。

locates = {(1, 1)}
y, x = locates.pop()
↓ pop 後
locates = {}
y, x = 1, 1

A を探索済みの * に置き換え、周辺の４箇所を調べます。(赤字の部分)

##### #*AA# #BAB# #BAB# #####

(1, 2) に A を発見！座標を locates に追加。
locates = {(1, 2)}

↓

locates から .pop() し、次の探索を始める。

locates = {(1, 2)}
y, x = locates.pop()
↓ pop 後
locates = {}
y, x = 1, 2

A を探索済みの * に置き換え、周辺の４箇所を調べます。

##### #**A# #BAB# #BAB# #####

(2, 2) に A を発見！座標を locates に追加。
locates = {(2, 2)}

(1, 3) に A を発見！座標を locates に追加。
locates = {(2, 2), (1, 3)}

↓

locates から .pop() し、次の探索を始める。

locates = {(2, 2), (1, 3)}
y, x = locates.pop()
↓
locates = {(2, 2)}
y, x = 1, 3

A を探索済みの * に置き換え、周辺の４箇所を調べます。

##### #***# #BAB# #BAB# #####

A が見つからなかったので、なにもしない。
locates = {(2, 2)}

↓

locates から .pop() し、次の探索を始める。

locates = {(2, 2)}
y, x = locates.pop()
↓
locates = {}
y, x = 2, 2

A を探索済みの * に置き換え、周辺の４箇所を調べます。

##### #***# #B*B# #BAB# #####

(3, 2) に A を発見！座標を locates に追加。
locates = {(3, 2)}

↓

locates から .pop() し、次の探索を始める。

locates = {(3, 2)}
y, x = locates.pop()
↓
locates = {}
y, x = 3, 2

A を探索済みの * に置き換え、周辺の４箇所を調べます。

##### #***# #B*B# #B*B# #####

A が見つからなかったので、なにもしない。
locates = {}

↓

locates が空になったのでループを終了する。

def bfs(h, w, group):
    locates = {(h, w)}
    while locates:
        y, x = locates.pop()
        s[y][x] = '*'
        for ny, nx in NSEW:
            yy = y + ny
            xx = x + nx
            if s[yy][xx] == group:
                locates.add((yy, xx))
    return 1  # ← 戻り値 1 でこの関数を終了する

ここまで大掛かりな探索作業をしておきながら、このループの座標は未だ (1, 1) です。

cnt = 0
for h in range(1, H+1):  # → h = 1
    for w in range(1, W+1):  # → w = 1
        if 'A' <= s[h][w] <= 'E':
            cnt += 1  # ← ココに戻る

cnt = 1

w のループの続きから進めます。次は (1, 2) です。

現在のマップ

h = 1, w = 2

##### #***# #B*B# #B*B# #####

h = 1, w = 3

##### #***# #B*B# #B*B# #####

h = 2, w = 1

##### #***# #B*B# #B*B# #####

B が見つかったので bfs(2, 1, 'B') を呼び出し、BFS を開始。

早送り 》》》

##### #***# #**B# #B*B# #####

##### #***# #**B# #**B# #####

cnt = 2

h = 2, w = 2

##### #***# #**B# #**B# #####

h = 2, w = 3

##### #***# #**B# #**B# #####

B が見つかったので bfs(2, 3, 'B') を呼び出し、BFS を開始。

早送り 》》》

##### #***# #***# #**B# #####

##### #***# #***# #***# #####

cnt = 3

h = 3, w = 1

##### #***# #***# #***# #####

h = 3, w = 2

##### #***# #***# #***# #####

h = 3, w = 3

##### #***# #***# #***# #####

ここでマップ全体の箇所を巡ったので、の二重ループは終了します。

残りは、

print(cnt)

これだけなので、cnt の中身 3 を画面に出力して完了となります。

セットは順番の保証がありませんので、実際は末尾からポップしても、どの座標が取り出されるかはランダム状態です。なのであっちこっち飛び飛びに探索しますけど、最後は正しい結果となりますのでご安心を。

この壁を作る方法はいちいち範囲内かどうかをチェックする条件文を書かなくて良いので out of range の心配を気にせず組むことができますが、マップを加工する必要があります。例２のやり方と、探索済みの座標をメモ化するやり方を合わせるとマップを一切加工せずに、さらに文字列のまま探索することができるようになります。

def bfs(h, w, group):
    locates = {(h, w)}
    while locates:
        y, x = locates.pop()
        memo.add((y, x))  # 現在の座標を探索済みとしてメモ
        for ny, nx in NSEW:
            yy = y + ny
            xx = x + nx
            if (0 <= yy < H and 0 <= xx < W) \  # マップ範囲内
                and (yy, xx) not in memo \  # 探索済みでない
                and s[yy][xx] == group:
                    locates.add((yy, xx))
    return 1
    

H, W = map(int, input().split())
s = [input() for _ in range(H)]

NSEW = ((-1, 0), (1, 0), (0, 1), (0, -1))
memo = set()
cnt = 0
for h in range(H):
    for w in range(W):
        if ((h, w) not in memo) and ('A' <= s[h][w] <= 'E'):
            cnt += bfs(h, w, s[h][w])

print(cnt)