ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC196 C - Doubled【Python解答例】

f:id:ebisuke33:20210320231655p:plain
AtCoder Beginner Contest196のC - DoubledについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder



AtCoder Beginner Contest196 C - Doubled

C - Doubled

問題文

整数 N が与えられます。以下の条件を満たす 1 以上 N 以下の整数 x は何個あるでしょうか?
・x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。

制約

・N は整数
・1≤N<10^12

解答例

N = input()
n = int(N)

digit = pow(10,len(N)//2)  # 入力Nの半分の桁

ans = 0
for i in range(1,digit):
    tmp = str(i)  # tmpを前半部分とする
    target = int(tmp + tmp)  # 偶数桁で前半と後半文字列が等しい数target
    if target <= n:
        ans += 1

print(ans)

解説

1以上N以下の数字において、偶数桁で前半と後半の文字列が等しい数の個数を答える問題です。

Nの制約が10^12までなので全探索では間に合いません。
したがって、前半部分(後半でもいいですが)にしぼって考えていきます。

入力Nの半分の桁をdigit変数に代入し、1からdigitまでのループを回します。
ループ値のがiのとき、まずiをstring型にしてtmpとします。
調べる値targetはtmp+tmpを再度int型にした値です。
これでtargetは偶数桁で前半と後半が等しい条件を満たす値になります。
targetがN以下ならans変数に1を足していきます。

ループを抜けてansを出力すればOKでした。



D問題はコンテスト中に解けませんでしたが、復習して記事にしたいと思います。


ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC196 A - Difference Max / B - Round Down【Python解答例】

f:id:ebisuke33:20210320230757p:plain
AtCoder Beginner Contest196のA とBについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder



AtCoder Beginner Contest196 A - Difference Max

A - Difference Max

問題文

整数 a,b,c,d が与えられます。
a≤x≤b, c≤y≤d となるように整数 x,y を選ぶとき、 x−y の最大値を求めてください。

制約

・入力は全て整数
・−100≤a≤b≤100
・−100≤c≤d≤100

解答例

a, b = map(int,input().split())
c, d = map(int,input().split())

ans = b - c
print(ans)

解説

問題文のようにa≤x≤b, c≤y≤d となる整数 x,y を選び、 x−y の最大値を答える問題です。

x - yは最も大きいxから最も小さいyを引けば最大値になります。
a≤x≤bから最も大きいxはb、c≤y≤dから最も小さいyはcなのでb - cの値を出力すればACでした。


AtCoder Beginner Contest196 B - Round Down

B - Round Down

問題文

整数または小数 X が与えられるので、小数点以下を切り捨てて整数で出力してください。

制約

・0≤X≤10^100
・X は整数、または小数点以下が 100 桁以下の小数であり、先頭に余計な 0 は付かない

解答例

x = input()

ans = ""

for i in range(len(x)):
    if x[i] == '.':
        break
    else:
        ans += x[i]
print(ans)

解説

与えられたXについて、小数点以下を切り捨てた整数を答える問題です。

Xが10の100乗なので直接Xをint型で受け取っても誤差が大きすぎてWAになります。
したがって、入力はstringで受け取って、小数点が来るまでの値を出力しました。
for文で一文字目から調べていき、小数点でなければansに追加、小数点が来たら探索を終了します。

ループを抜けたあとでansを出力すればACでした。



続いてABC196のC問題も記事にしていきたいと思います。



ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

【AtCoder版!蟻本】AGC 033 A - Darker and Darker【幅優先探索】

f:id:ebisuke33:20210318232423p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているAGC 033 AをPythonで解いていきます。

A - Darker and Darker

AtCoder Grand Contest 033 A - Darker and Darker

問題文

縦 H 行、横 W 列の白黒に塗られたマス目が与えられます。 マス目の状態は A11 から AHW の HW 個の文字で表されており、 上から i 行目、左から j 列目にあるマスが黒色のとき Aij は #、 上から i 行目、左から j 列目にあるマスが白色のとき Aij は . となっています。
すべてのマスが黒色になるまで、以下の操作を繰り返し行います。
・辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも 1 つ黒色のマスが存在します。

制約

・1≦H,W≦1000
・Aij は # または .
・与えられるマス目には少なくとも 1 つ黒色のマスが存在する。

解答例

from collections import deque

h, w = map(int,input().split())

A = [] # マス目の文字配列
for i in range(h):
    A.append(list(input()))

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 白マスをすべて黒マスに変える回数を調べるbfs
def bfs():
    que = deque()
    # すべての黒マス座標をqueにいれる
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                que.append([i,j])
    # 操作回数
    res = 0

    # キューが空になるまで探索
    while True:
        num = len(que)
        while num > 0:          # 操作回数ごとの要素を取り出す
            p = que.popleft()   # 先入れのキューの要素を取り出す
            for i in range(4):  # pから4方向に移動 移動後のマス目は(nx,ny)
                ny = p[0] + dy[i]
                nx = p[1] + dx[i]
                # 隣接するマス目が範囲内で白色かの判定
                if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == ".":
                    A[ny][nx] = "#"     # 隣接する白マスを黒に置き換え
                    que.append([ny,nx]) # 隣接する白マスをqueにいれる
            num -= 1
        if len(que) == 0:
            break
        res += 1 # 操作回数を1増やす
    return res

print(bfs())

解説

H行、W列の白か黒に塗られたマス目があり、操作1回ごとに黒マスに隣接した白マスが黒マスに変わります。
すべてのマスが黒色に変わるために必要な操作回数を答える問題です。

先入れ先出しで探索できる幅優先探索の特性を活かして、探索する範囲を操作回数ごとに決めていきます。


bfs関数を呼び出すまでは基本的な幅優先探索と同じように普通に入力を受け取りました。
基本的な幅優先探索は次の記事で記載しています。
ebisuke33.hatenablog.com


bfs関数では最初に黒マスを全探索し、すべてキューに入れてしまいます。

このときキューに入っている要素が1回目の操作で探索する範囲です。


while文で幅優先探索を進めますが、len関数を用いてキューに入っている要素数だけ探索するようにしました。

例えば、while文の1回目のループでは、ループ前に全探索してキューに入っている黒マスが探索対象となります。

その探索中にキューに追加されていきますが、新しく追加された分は次回に探索することになります。

1回目のwhileを抜けると操作回数resに1を足します。


同じように2回目の操作対象は、2回目の探索時点でキューに入っている黒マスを探索し、新しくキューに追加された分は3回目に探索する、という処理を繰り返します。


最後はすべて黒マスに変わりますので、while文をbreakしてループを抜けます。

ループを抜けた後にresを出力すれば、求める操作回数となりACでした。


操作回数ごとの処理を実現するために、処理開始時点のキューの長さを覚えておくことがポイントでした。



AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com


【AtCoder版!蟻本】ABC 088 D - Grid Repainting【幅優先探索】

f:id:ebisuke33:20210317142816p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているABC088 DをPythonで解いていきます。

atcoder.jp

AtCoder Beginner Contest 088 D - Grid Repainting

問題文

縦 H マス, 横 W マスに広がるマス目があり, 各マスは白または黒で塗られている. 上から i 番目で左から j 番目のマスを (i,j) で表す. すぬけ君は, このマス目を使って次のようなゲームをしたい. ゲームの開始時点ではマス (1,1) にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す. けぬす君が白いマスだけを通って (H,W) にたどり着けばゲームクリアとなる.
ゲームを開始する前に, すぬけ君はいくつかの白いマス目の色を黒に変えることができる. ただし, マス (1,1) と (H,W) の色を変えることはできず, ゲームを開始するまでにすべての色の変更を行わなければならない.
ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる. そのとき, すぬけ君が取る可能性のある最大のスコアを求めなさい.ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H,W) にたどり着くことが出来ない場合、−1 と出力しなさい.
ただし, 各マスの色の情報は文字 si,j として与えられる. マス (i,j) が最初白で塗られている場合 si,j は . であり, マス (i,j) が最初黒で塗られている場合 si,j は # である.

制約

・H は 2 以上 50 以下の整数
・W は 2 以上 50 以下の整数
・si,j は . または # (1≤i≤H,1≤j≤W)
・s1,1, sH,W は . である

解答例

from collections import deque

# 入力
h, w = map(int,input().split())

maze = [] # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# 各座標への最短距離の配列(INFで初期化)
INF = int(1e9)
D = [[INF] * w for i in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタート地点
sy = 0
sx = 0
# ゴール地点
gy = h-1
gx = w-1


# スタートからゴールへの最短距離を求める
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    D[sy][sx] = 0 # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.popleft() # 先入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            # 移動可能か、訪れたことがあるかの判定
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and D[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D[ny][nx] = D[p[0]][p[1]] + 1
    return D[gy][gx]

# 最初黒色のマスの数
def black_count():
    black_num = 0 # 黒色のマス目の数
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                black_num += 1
    return black_num

tmp = bfs()
num = black_count()
if tmp == INF:
    print(-1)
else:
    res = h * w - tmp - num - 1
    print(res)

解説

縦 H マス, 横 W マスのマス目が白色か黒色で塗られていて、マス (1,1) からスタートし白色のマスだけを通ってマス (H,W)を目指します。
スタート前に白色のマスを黒色に変えることができ、塗り替えたマス目の数に応じて得点がもらえます。
このルールで最大何点をとることができるか、あるいはゴールにたどり着けないか 答える問題です。

初期状態のまま幅優先探索BFSでスタートからゴールへの最短経路を求めます。
この最短経路以外のマス目は黒に塗り替えても通らないで済むので、これを元に黒に塗り替える最大のマス目を解答する方針です。

幅優先探索は特に工夫しておらず、問題文から求まるスタート地点とゴール地点を代入して最短経路を求めます。
基本的な幅優先探索は次の記事で記載しました。
ebisuke33.hatenablog.com


次に初期状態の黒色のマス目を数えます。
black_count関数を作り、単純に全探索して黒色のマス目を数えます。

このふたつが求まれば、黒色に塗り替えることのできるマス目の最大値resは、H×Wのマス目から 最短経路と もともと黒色のマス目の数+1を引いた値になります。
もし、スタートからゴールにたどり着けないときはBFSでINFが返ってくるので、-1を出力し、それ以外のときはresを出力すればOKです。




AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com


パナソニックプログラミングコンテスト(ABC195 D - Shipping Center)【Python解答例】

f:id:ebisuke33:20210317140116p:plain
AtCoder Beginner Contest195のD - Shipping CenterについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder


AtCoder Beginner Contest 195 D - Shipping Center

D - Shipping Center

問題文

1 から N の番号がついた N 個の荷物と、1 から M の番号がついた M 個の箱があります。
荷物 i の大きさは Wi で、価値は Vi です。
箱 i には大きさが Xi 以下の荷物を入れることができます。
1 つの箱に 2 つ以上の荷物を入れることはできません。
Q 個のクエリが与えられます。各クエリでは 2 つの整数 L,R が与えられるので、次の問題を解いてください。

問題:M 個の箱のうち、箱 L,L+1,…,R の R−L+1 個の箱が使えなくなってしまいました。 残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。

制約

・1≤N≤50
・1≤M≤50
・1≤Q≤50
・1≤Wi≤10^6
・1≤Vi≤10^6
・1≤Xi≤10^6
・1≤L≤R≤M
・入力は全て整数

解答例

n, m, q = map(int,input().split())

WV = []
for i in range(n):
    array = list(map(int,input().split()))
    WV.append(array)
WV.sort(key=lambda x:x[1], reverse=True) # 価値Vの降順にソート

X = list(map(int,input().split()))

Q = []
for i in range(q):
    array = list(map(int,input().split()))
    Q.append(array)

# クエリ分だけループ
for i in range(q):  # i番目のクエリ
    ans = 0
    X_copy = X[:] # リストXをコピー
    del X_copy[Q[i][0]-1:Q[i][1]]   # LからRの箱を消去
    X_copy.sort()   # 箱の大きさを昇順でソート
    for wv in WV:   # 荷物のループ(Vが大きい順)
        for j in range(len(X_copy)):    #箱のループ(大きさが小さい順)
            if wv[0] <= X_copy[j]:  # 探索中の箱に荷物が入れば
                ans += wv[1]        # 価値Viを足して
                X_copy.pop(j)       # 荷物を入れた箱を消去
                break
    print(ans)

解説

それぞれ大きさがWi、価値がViの荷物がN個と、M個の箱があります。
箱iには大きさXi以下の荷物をひとつだけいれることができるという初期条件があります。
Q個のクエリがあり、各クエリでは箱LからRが使えなくなる条件が与えられ、残った箱に入れることができる荷物の価値の最大値をそれぞれ答える問題です。

各クエリごとに箱を消去し、残った箱の小さいものから、できるだけ価値の大きい荷物を貪欲に入れていく方針で進めればOKでした。

上記の方針があるので標準入力はWとVだけVの昇順(大きい順)にソートしました。

あとは各クエリ毎のループをまわします。
リストXは何度も使用するのでクエリ毎にコピーしました。
クエリの条件から使用できない箱をX_copyから消去し、箱の小さい順にソートします。

価値の大きい荷物から、小さい箱の順にループを回していき、入れることができる組み合わせを見つけたら順次荷物を入れていきます。
荷物を入れるたびに価値をansに足していき、入れた箱はリストX_copyから消去しました。

この2重ループを抜けたら価値の合計であるansを出力することを繰り返せばACをとれました。



問題を見ときはDPかと思いましたが、貪欲法で解ける問題でした。
コンテスト中でも解けるように学習を続けていきたいです。


ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

パナソニックプログラミングコンテスト(ABC195 C - Comma)【Python解答例】

f:id:ebisuke33:20210317143421p:plain
AtCoder Beginner Contest195のC - CommaについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder


AtCoder Beginner Contest 195 C - Comma

C - Comma

問題文

高橋君は整数を書くとき、下から 3 桁ごとにコンマで区切って書きます。例えば 1234567 であれば 1,234,567、777 であれば 777 と書きます。
高橋君が 1 以上 N 以下の整数を 1 度ずつ書くとき、コンマは合計で何回書かれますか?

制約

・1≤N≤10^15
・N は整数

解答例

n = int(input())

ans = 0

if n >= 1000: ans += n - 999
if n >= 1000000: ans += n - 999999
if n >= 1000000000: ans += n - 999999999
if n >= 1000000000000: ans += n - 999999999999
if n >= 1000000000000000: ans += n - 999999999999999

print(ans)

解説

問題文の通り1 以上 N 以下の整数を 1 度ずつ書くとき、コンマは合計で何回書かれるか答える問題です。

コンテスト中には解けず、公式解説より良い解法も思いつかないため公式解説と同じ解き方をしています。
Editorial - Panasonic Programming Contest (AtCoder Beginner Contest 195)
公式解説を見たほうが良いと思いますが、一応記事にしていきます…

千の位を表すコンマは999までは出てきませんが1000以上の数字では1つづつあります。
つまりNが1000以上ならN-999個出てきます。
百万の位を表すコンマは99万9999まで出てきませんが100万以上の数字では1つづつあります。
同様にNが100万以上ならN-999999個出てきます。
という感じで、コンマが増える場合ごとにansを足し合わせていけば答えが求まります。



コンテストではごちゃごちゃ演算しましたが、結局微妙に値が違ってACできませんでした。
シンプルで強力な考え方が思いつけるように地道に勉強を続けていきたいです。

ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

パナソニックプログラミングコンテスト(ABC195 A - Health M Death / B - Many Oranges)【Python解答例】

f:id:ebisuke33:20210317143925p:plain
AtCoder Beginner Contest195のA - Health M DeathとB - Many OrangesについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder


AtCoder Beginner Contest 195 A - Health M Death

A - Health M Death

問題文

魔法使いの高橋君がモンスターと戦っています。
高橋君が魔法を使うと、体力が M の倍数であるモンスターを倒すことができます。体力が M の倍数でないモンスターに対しては何の効果もありません。
高橋君の魔法によって、体力が H のモンスターを倒すことができるでしょうか?

制約

・1≤M≤1000
・1≤H≤1000
・M 及び H は整数

解答例

m, h = map(int,input().split())

if h % m == 0:
    print("Yes")
else:
    print("No")

解説

HがMの整数倍か答える問題です。

割り算して余りを確認すればいいので、余りを求める%演算子を使います。
余りが0ならYes、0でなかったらNoを出力すればACでした。

AtCoder Beginner Contest195 B - Many Oranges

B - Many Oranges

問題文

みかんがたくさんあります。どのみかんの重さも A グラム以上 B グラム以下であることがわかっています。(みかんの重さは整数とは限りません。)
この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど W キログラムになりました。
選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

制約

・1≤A≤B≤1000
・1≤W≤1000
・入力は全て整数

解答例

a, b, w = map(int,input().split())

weight = w * 1000 # 単位合わせ

flag = True # 組み合わせが起こり得るか判別フラグ

# 最大値を求める
tmp = weight // a # 余り切り下げ
if tmp * a <= weight and tmp * b >= weight:
    max_num = weight // a
else:
    flag = False

# 最小値を求める
tmp = -(-weight // b) # 余り切り上げ
if tmp * a <= weight and tmp * b >= weight:
    min_num = -(-weight // b)
else:
    flag = False

if flag:
    print(min_num, max_num)
else:
    print("UNSATISFIABLE")

解説

Aグラム以上、Bグラム以下のみかんをいくつでも選べるとき、重さの合計をWキログラムにできるかどうか、できるならみかんの個数の最小値と最大値を答える問題です。
解説では全探索していましたが、コンテスト中に思いついた方法を記載します。

標準入力のWはキログラム単位でA,Bグラムと単位が違うので単位合わせを行います。

みかんの個数の最大値は重さを余り切り下げでAで割った値が候補(tmp)です。
この値×Aと同じ値×Bの間にW[g]があれば、Wを作り出せることが可能で、最小値となります。
tmp+1個では必ずWを超えてしまうので、候補となる値はtmp以外にないと思います。

みかんの個数の最小値はBで割って余りを切り上げた値(tmp)を候補とします。
最小値と同じようにA×tmpとB×tmpの間にWがあれば、最大値となります。

もし最大値と最小値が存在していたら値を出力し、なければUNSATISFIABLEを出力すればACです。




B問題は余りの切り上げ、切り下げで頭を悩ませましたが解けてよかったです。
全探索で解けることはコンテスト中は全然気が付きませんでした (^_^;)
今回もD問題まで復習していきたいです。


ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

【AtCoder版!蟻本】AOJ0558 Cheese【幅優先探索】

f:id:ebisuke33:20210317144704p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているAOJ0558 CheeseをPythonで解いていきます。

AOJ0558

AOJ0558 Cheese

問題文

今年も JOI 町のチーズ工場がチーズの生産を始め,ねずみが巣から顔を出した.JOI 町は東西南北に区画整理されていて,各区画は巣,チーズ工場,障害物,空き地のいずれかである.ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる.

この町には,N 個のチーズ工場があり,どの工場も1種類のチーズだけを生産している.チーズの硬さは工場によって異なっており,硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある.

ねずみの最初の体力は 1 であり,チーズを 1 個食べるごとに体力が 1 増える.ただし,ねずみは自分の体力よりも硬いチーズを食べることはできない.

ねずみは,東西南北に隣り合う区画に 1 分で移動することができるが,障害物の区画には入ることができない.チーズ工場をチーズを食べずに通り過ぎることもできる.すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け.ただし,ねずみがチーズを食べるのにかかる時間は無視できる.

入力

入力は H+1 行ある.1 行目には 3 つの整数 H,W,N (1 ≤ H ≤ 1000,1 ≤ W ≤ 1000,1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている.2 行目から H+1 行目までの各行には,'S','1', '2', ..., '9','X','.' からなる W 文字の文字列が書かれており,各々が各区画の状態を表している.北から i 番目,西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W),第 i+1 行目の j 番目の文字は,区画 (i,j) が巣である場合は 'S' となり,障害物である場合は 'X' となり,空き地である場合は '.' となり,硬さ 1, 2, ..., 9 のチーズを生産する工場である場合はそれぞれ '1', '2', ..., '9' となる.入力には巣と硬さ 1, 2, ..., N のチーズを生産する工場がそれぞれ 1 つずつある.他のマスは障害物または空き地であることが保証されている.ねずみは全てのチーズを食べられることが保証されている.

解答例

from collections import deque
import copy

# 入力
h, w, n = map(int,input().split())
maze = [] # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# 各座標への最短距離の配列(INFで初期化)
INF = int(1e9)
D = [[INF] * w for _ in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタート位置の探索
for i in range(h):
    for j in range(w):
        if maze[i][j] == "S":
            sy = i
            sx = j


# 硬さxのチーズ位置の探索
def search_cheese(x):
    for i in range(h):
        for j in range(w):
            if maze[i][j] == str(x):
                gy = i
                gx = j
    return gy, gx # 硬さxのチーズ座標を返す


# スタートからゴールへの最短距離を求めるbfs
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    D_copy[sy][sx] = 0  # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.popleft()   # 先入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx:   # ゴールなら探索終了
            break
        for i in range(4):  # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            # 移動可能か、この探索で訪れたことがあるかの判定
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "X" and D_copy[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D_copy[ny][nx] = D_copy[p[0]][p[1]] + 1
    # ゴールまでの最短経路を返す
    return D_copy[gy][gx] 
                


# 硬さNまでの最短経路探索
res = 0 # 最短経路
for k in range(n):
    D_copy = copy.deepcopy(D)
    tmp = search_cheese(k+1)
    gy = tmp[0]
    gx = tmp[1]
    res += bfs()
    sy = gy
    sx = gx

print(res)

解説

N個のチーズ工場があり、それぞれ1からNまでの硬さのチーズを生産しています。
スタート地点から硬さNのチーズを食べるまでの最短経路を答える問題です。

この問題も幅優先探索(BFS)で最短経路を求めていきます。

入力を受け取ったあと、BFSの準備として迷路と同じ大きさの配列D(INFで初期化)を用意します。
迷路のスタート地点はSで表されているので、全探索してxy座標をsx,syに代入しました。

硬さiのチーズの位置はプログラムで何度も探す必要があるのでsearch_cheese関数を作成しました。
iを引数として渡すことで硬さiのチーズの位置をgx,gyとして返します。

BFSはスタート地点を渡すことで、gx,gy地点までの最短経路を返す関数です。
最短経路のリストDは以前の探索のデータを引き継いだら間違った答えになりますので、deepcopyしたD_copyに最短経路を記録していきました。

最後に1からNまでのチーズの最短経路をfor文で求めます。
次の目的地であるk+1の硬さのチーズの位置をsearch_sheese関数で求め、BFSで現在地から求めた地点までの最短経路をresに足していきました。
BFSが終わるとゴール地点を次のスタート地点として、次回のループに備えます。

ループを抜ければ求める最短経路がresとなりますので出力すればOKでした。




AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com