ebisuke競プロ初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。C言語も少しだけ勉強中

AtCoder-ABC197 A - Rotate / B - Visibility【Python解答例】

f:id:ebisuke33:20210328102900p:plain
AtCoder Beginner Contest197のA とB問題についてPythonの解答例を記事にしていきます。
atcoder.jp



AtCoder Beginner Contest197 A - Rotate

A - Rotate

問題文

長さ 3 の文字列 S が与えられます。
S の先頭の文字を S の末尾に移動して得られる文字列 S′ を出力してください。

制約

・S は英小文字のみからなる長さ 3 の文字列である

解答例

S = input()

ans = S[1] + S[2] + S[0]

print(ans)

解説

問題文のように与えられた3文字の文字列の先頭を末尾に移動させた文字列を答える問題です。

入力をSで受け取った後、Sの2文字目、3文字目、1文字目の順番でans変数に代入します。

そしてans変数を出力すればACでした。

AtCoder Beginner Contest197 B - Visibility

B - Visibility

問題文

縦 H 行、横 W 列のマス目があり、いくつかのマスには障害物が置かれています。
上から i 番目、左から j 番目のマスをマス (i,j) と表すことにします。
H 個の文字列 S1,S2,S3,…,SH が与えられます。
Si の j 文字目はマス (i,j) の状態を表し、# なら障害物が置かれていることを、. なら障害物が置かれていないことを表します。
このマス目上のあるマスからあるマスが見えるとは、2 つのマスが同じ行または列にあり、2 つのマスの間 (2 つのマス自身を含む) に障害物が 1 つも置かれていないことを意味します。
このマス目上のマスであって、マス目 (X,Y) から見えるもの (マス (X,Y) 自身を含む) の数を求めてください。

制約

・1≤H≤100
・1≤W≤100
・1≤X≤H
・1≤Y≤W
・Si は . および # のみからなる長さ W の文字列
・マス (X,Y) に障害物は置かれていない

解答例

h, w, x, y = map(int,input().split())
x -= 1
y -= 1

S = []
for i in range(h):
    S.append(input())

# 座標(x,y)自身もカウントするので初期値は1
ans = 1

# 座標(x,y+1)から下方向の探索
for i in range(1,101):
    if y+i >= w or S[x][y+i] == "#":
        break
    if S[x][y+i] != "#":
        ans += 1

# 座標(x,y-1)から上方向の探索
for i in range(1,101):
    if y-i < 0 or S[x][y-i] == "#":
        break
    if S[x][y-i] != "#":
        ans += 1

# 座標(x+1,y)から右方向の探索
for j in range(1,101):
    if x+j >= h or S[x+j][y] == "#":
        break
    if S[x+j][y] != "#":
        ans += 1

# 座標(x-1,y)から左方向の探索
for j in range(1,101):
    if x-j < 0 or S[x-j][y] == "#":
        break
    if S[x-j][y] != "#":
        ans += 1

print(ans)

解説

縦H行、横W列のマス目があり、マス目(x,y)から同じ行か同じ列で、間に障害物がないマス目の数を答える問題です。

問題文のようにマス目(x,y)から縦横4方向に探索しました。
求める数はans変数とし、座標(x,y)自身もカウントするので初期値は1にしました。
それぞれの探索はH行W列の範囲外に出るか、障害物にあたるまでansを1だけ足し続けていきます。

それぞれの4方向の探索が終わった後にansを出力すればOKです。




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


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

【AtCoder版!蟻本】ARC 005 C - 器物損壊!高橋君【幅優先探索】

f:id:ebisuke33:20210319000747p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているAtCoder Regular Contest 005 C - 器物損壊!高橋君をPythonで解いていきます。


C - 器物損壊!高橋君

AtCoder Regular Contest 005 C - 器物損壊!高橋君

問題文

良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
 彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
 しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。

 高橋君が魚屋に辿り着くことができるかどうか答えてください。

入力

・入力は H+1 行ある。
・1 行目は、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
・2 行目からの H 行には、格子状の街の各区画における状態 c(i,j)(0≦i≦H−1, 0≦j≦W−1) が与えられる。
・i 行目 j 文字目の文字 c(i,j) はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
・s : その区画が家であることを表す。
・g : その区画が魚屋であることを表す。
・. : その区画が道であることを表す。
・# : その区画が塀であることを表す。
・高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
・与えられた街の外を通ることはできない。
・s と g はそれぞれ 1 つずつ与えられる。

解答例

from collections import deque

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

# スタート、ゴールの探索
for y in range(h):
    for x in range(w):
        if maze[y][x] == "s": # スタート座標はsx,sy
            sx = x
            sy = y
        if maze[y][x] == "g": # ゴール座標はgx,gy
            gx = x
            gy = y

# scoreは各座標へ到達するまでに壊す必要のある壁の数(INFで初期化)
INF = int(1e9)
score = [[INF] * w for _ in range(h)]

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


# スタートからゴールへのscoreを求めるbfs
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    score[sy][sx] = 0 # スタート地点のscoreを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 nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            # 移動先が壁で未到達ならqueの後ろにpush
            if maze[ny][nx] == "#" and score[ny][nx] == INF:
                # scoreは+1
                score[ny][nx] = score[p[0]][p[1]] + 1
                que.append([ny,nx])
            # 移動先が壁でなく未到達ならqueの先頭にpush
            if maze[ny][nx] != "#" and score[ny][nx] == INF:
                # scoreはpと同じ
                score[ny][nx] = score[p[0]][p[1]]
                que.appendleft([ny,nx])

    return score[gy][gx]

res = bfs()
if res <= 2:
    print("YES")
else:
    print("NO")

解説

これまでの幅優先探索の問題のようにスタート地点からゴール地点に向かってBFSを行う問題です。
違う点は最短距離を求めるのでなく、壁を2回まで壊してゴールに到着できるかを答える問題です。

今回も迷路と同じ範囲の配列scoreを作成しますが、最短距離でなく壊した壁の数を記録していきます。

bfsではスタート地点をキューに入れて探索を始めます。
探索先が道と壁の場合で、キューの入れ方を変えました。
探索先が道の場合、探索元と同じscoreを記録してキューの先頭に入れます。
壁の場合は、探索元のscoreに+1した数を記録してキューの最後尾に入れました。

キューから先頭からしか取り出さないので、最初は壁を壊さずに行くことができるすべての道に到達するまで探索を続けます。

道の探索が終われば次はscoreが1の壁の探索です。
このとき、また道に出ればscore1として道の探索を行いました。
未探索の壁があればscoreをさらに+1してキューの最後尾に入れます。

このような探索を繰り返していけば、最終的にはゴールまで探索が進み 壊した壁の数がscoreに記録されています。

問題にあわせてscoreが2以下ならYes、それより大きければNoを出力すればOKでした。



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


Pythonで解く!初中級者が解くべき過去問精選 100 問 まとめ

f:id:ebisuke33:20210322135453p:plain
AtCoderの学習のためこちらの記事で紹介されている初中級者が解くべき過去問精選100 問に取り組みました。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】 - Qiita

問題数が多いため分野ごとに分けて記載した記事を紹介します。

目次


作成中の記事ばかりですが地道に取り組んで更新していきます m(_ _)m

全探索:全列挙

ebisuke33.hatenablog.com

全探索:工夫して通り数を減らす全列挙

ebisuke33.hatenablog.com

全探索:ビット全探索

ebisuke33.hatenablog.com

全探索:順列全探索

ebisuke33.hatenablog.com

深さ優先探索(以下作成中です m(_ _)m)

動的計画法:ナップザック DP

動的計画法:bit DP

動的計画法:その他

最短経路問題:ダイクストラ

最短経路問題:ワーシャルフロイド法

高速な素数判定法

高速なべき乗計算

逆元を使う問題

累積和

Union-Find

その他のテクニック

実装問題

数学的な問題

蟻本の類題も解いていますので興味があればこちらもおすすめです。
ebisuke33.hatenablog.com

AtCoder-ABC196 D - Hanjo【Python解答例】

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



AtCoder Beginner Contest196 D - Hanjo

D - Hanjo

問題文

縦 H メートル、横 W メートルの長方形の部屋があります。
この部屋に 2 メートル × 1 メートルの区別できない畳 (長方形のタイル) A 枚と、1 メートル × 1 メートルの区別できない半畳 (正方形のタイル) B 枚を敷き詰めます。
2 メートル × 1 メートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか?
なお、2A+B=HW であることが保証されます。 また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

制約

・入力は全て整数
・1≤H,W
・HW≤16
・0≤A,B
・2A+B=HW

解答例

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

used = [[0]*w for _ in range(h)] # 畳があるか管理

res = 0

# マス(1,1)から(1,w)、(2,1)から(2,w)・・・(h,1)から(h,w)の順にdfs
def dfs(i,j,a,b):
    global res
    if a<0 or b<0:  # 畳がa枚以下やb枚以下になれば失敗
        return
    if j == w:      # 右端に来たら次の行へ
        j = 0
        i += 1
    if i == h:      # iがhになれば成功(条件にあう畳の敷き詰め方)
        res += 1
        return
    if used[i][j] == 1: # 調べるマスに畳があれば次のマスに
        return dfs(i,j+1,a,b)

    used[i][j] = 1
    dfs(i,j+1,a,b-1)    # 半畳 使う場合
    if j+1 < w and used[i][j+1] == 0:    #横に1畳置く場合
        used[i][j+1] = 1
        dfs(i,j+1,a-1,b)
        used[i][j+1] = 0

    if i+1 < h and used[i+1][j] == 0:   #縦に1畳置く場合
        used[i+1][j] = 1
        dfs(i,j+1,a-1,b)
        used[i+1][j] = 0

    used[i][j] = 0  # 元に戻す
    return res

print(dfs(0,0,a,b))

解説

縦H、横Wの部屋において、1畳(2マス分)の畳をA枚と、半畳(1マス分)の畳をB枚の敷き詰め方が何通りあるか答える問題です。

公式解説動画のようにDFSを用いた解法になります。

DFSでは左上マス(1,1)から(1,w)、(2,1)から(2,w)・・・(h,1)から(h,w)のように横書き文章の順に進めていきました。

関数では終了条件から書いています。
ひとつ目の終了条件は畳の枚数aやbがマイナスになれば終了しています。
畳を使いすぎれば失敗です。
2つ目は終了条件ではないですが、右端のマスを探索した後に次の行に移る動きをさせています。
3つ目は途中で畳が足りなくなったりしないで全マス探索し終えたことになるので、求める置き方ができたことになります。
したがってresに1を足しました。
4つ目は今、探索しているマスにすでに畳が置かれている状態なので、なにもしないで次のマスに移ります。

次からは遷移の部分です。
まず、現在のマスに畳を置かれたことをusedリストに記録します。
そこから3通りに分岐します。
・半畳の畳を置く場合
半畳の畳はどこでもおけるので、次のマス目に移動し半畳の畳を1枚引いて再度DFSします。

・1畳の畳を横に置く場合
現在のマスの右横に畳をおけるなら探索します。
右横のマスに畳を置いたことをusedにメモして、次のマス目から1畳の畳を1枚引いて再度DFSしました。
このDFS関数から戻ったとき、以降の探索のため右横の畳は消しておきます。

・1畳の畳を縦に置く場合
同じように現在のマスの下に畳をおけるなら探索します。
同様に下マスに畳を置いたことをusedにメモし、次のマス目から1畳の畳を1枚引いて再度DFSです。
このDFS関数から戻ったときも、下の畳は消しておきました。


このDFSによりi == hとなった数を数えることで、畳の敷き詰め方がわかります。
最後にresを出力すればOKでした。



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