Atcoder水色への精選 100 問　幅優先探索(Python)

AtCoder Python 競プロ精進 精選100問

水色になるための精選100問、
今回は28~33までの「幅優先探索」です

qiita.com

前回↓
深さ優先探索
algo-archit.hatenablog.com

目次



28　ALDS_11_C - 幅優先探索

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja

dequeと呼ばれる両端キューを用いることで問題を解くことができます
そのノードに訪問したか、そのノードまでの距離をそれぞれ格納するリストを用意しておき、
訪問済みでないノードにたどり着いた場合にキューを追加します

キューがすべてなくなった時の距離が答えです

pythonでの実装例

from collections import deque

inf = 10**10

n = int(input())
network = [[] for _ in range(n+1)]
length_list = [inf for _ in range(n+1)]
visited_list = [0 for _ in range(n+1)]

for _ in range(n):
    inputs = list(map(int,input().split()))
    u,k = inputs[:2]
    v = inputs[2:]
    network[u] += v

que = deque() # キューを作成

que.append(1)
length_list[1] = 0 

while que:
    node = que.popleft() # 先頭から要素を取得
    visited_list[node] = 1

    for i in network[node]:
        if visited_list[i]:
            continue
        
        que.append(i) # 
        visited_list[i] = 1
        
        # 長さ+1をしても現在より短くなる場合は更新
        if length_list[i] > length_list[node]+1:
            length_list[i] = length_list[node]+1

for i in range(1,n+1):
    if length_list[i] == inf:
        print(i,-1)
    else:
        print(i,length_list[i])



29　AtCoder Beginner Contest 007 C - 幅優先探索

問題文
atcoder.jp

マス目状の問題の場合でも二次元型のリストを使って同じように解くことができます
壁に当たらず、かつ訪問済みでないマスをキューに追加して答えのマスまでの距離を求めます

pythonでの実装例

from collections import deque

inf = 10**10

R,C = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

c = [input() for _ in range(R)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1

inf = 10**10
visited = [[0 for i in range(C)] for j in range(R)]
length = [[inf for i in range(C)] for j in range(R)]

que = deque([]) 

que.append([sy,sx])
visited[sy][sx] = 1
length[sy][sx] = 0

while que:
    y,x = que.popleft()

    for y_move,x_move in [[-1,0],[1,0],[0,-1],[0,1]]:
        ny = y+y_move
        nx = x+x_move

        if visited[ny][nx] or c[ny][nx] == "#":
            continue

        que.append([ny,nx])
        visited[ny][nx] = 1

        if length[ny][nx] > length[y][x]+1:
            length[ny][nx] = length[y][x]+1

print(length[gy][gx])



30　JOI 2011 予選 5 - チーズ

問題文
atcoder.jp

硬さ１のチーズから順番に食べていけばOKです
順番を辞書に格納しておき、各中継地点までのかかる時間（距離）を合計したものが答えとなります

pythonでの実装例

from collections import deque,defaultdict

inf = 10**10

h,w,n = map(int,input().split())
town = [input() for _ in range(h)]
factory = defaultdict(int)

# スタートと工場の順番を辞書に入れる(スタートを0とする)
for i in range(h):
    for j in range(w):
        if town[i][j] == "S":
            factory[0] = [i,j]
        elif town[i][j] == "X" or town[i][j] == ".":
            continue
        else:
            factory[int(town[i][j])] = [i,j]

def bfs(sy,sx,gy,gx):
    visited = [[0 for j in range(w)]for i in range(h)]
    length = [[inf for j in range(w)]for i in range(h)]

    que = deque([])
    que.append([sy,sx])
    visited[sy][sx] = 1
    length[sy][sx] = 0
    
    while que:
        y,x = que.popleft()

        for i,j in [[-1,0],[0,1],[0,-1],[1,0]]:
            ny,nx = y+i,x+j

            if 0 <= ny < h and 0 <= nx < w and visited[ny][nx]== 0 and town[ny][nx] != "X":
                que.append([ny,nx])
                visited[ny][nx] = 1
                length[ny][nx] = length[y][x]+1

    return length[gy][gx]

total = 0 # 最終的にかかる時間

# 順番に経路をたどっていく
for i in range(1,n+1):
    sy,sx = factory[i-1]
    gy,gx = factory[i]

    total += bfs(sy,sx,gy,gx)

print(total)



31　JOI 2012 予選 5 - イルミネーション

問題文
atcoder.jp

やっかいな問題に見えますが、移動できる方向が４→６に増えたと考えれば大丈夫です（偶奇の時の場合分けに注意）
今回はマス目の外側に１つ分余分なマスを作り、自由に動き回ったときに、何回壁に当たったかをカウントします

このときのカウント数がイルミネーションする壁面の個数になります

この問題に関しては公式の解説図がとっっっても分かりやすかったので確認してみてください↓
www.ioi-jp.org

pythonでの実装例

from collections import deque

inf = 10**10

w,h = map(int,input().split())
field = [[0 for j in range(w+2)]for i in range(h+2)]
visited = [[0 for j in range(w+2)]for i in range(h+2)]

for i in range(h):
    field[i+1][1:w+1] = map(int,input().split())

# どの行かで動き方が異なる
odd_move = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[0,-1]]
even_move = [[-1,-1],[-1,0],[0,1],[1,0],[1,-1],[0,-1]]

que = deque([])
que.append([0,0])
visited[0][0] = 1

# 壁にぶつかった回数をカウント
collision = 0

while que:
    y,x = que.popleft()

    if y%2 == 1:
        move = odd_move
    else:
        move = even_move

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h+2 or nx < 0 or nx >= w+2:
            continue
        elif field[ny][nx] == 1:
            collision += 1 # 壁にぶつかったのでカウント
            continue
        elif visited[ny][nx]:
            continue
        else:
            que.append([ny,nx])
            visited[ny][nx] = 1

print(collision)



32　AOJ 1166 - 迷図と命ず

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166

一見ややこしくてわかりにくい問題ですが、マス目を新しく自分で作り、
縦横の４方向に動くことができるかを壁のリストから参照します

端側の処理だけ注意していれば問題なく解くことができます

pythonでの実装例

from collections import deque

inf = 10**10

# 0,0入力が来るまで
while True:
    w,h = map(int,input().split())

    if w == 0 and h == 0:
        break
    
    v_wall = [] # 垂直壁
    h_wall = [] # 水平壁

    for i in range(2*h-1):
        if i%2 == 0:
            v_wall.append(list(map(int,input().split())))
        else:
            h_wall.append(list(map(int,input().split())))

    visited = [[0 for i in range(w)] for j in range(h)]
    length = [[inf for i in range(w)] for j in range(h)]

    visited[0][0] = 1
    length[0][0] = 1

    que = deque([])

    que.append([0,0])

    while que:
        y,x = que.popleft()
        can_go = [] # 行くことができる方向
      
        # 左確認
        if x != 0 and v_wall[y][x-1] != 1:
            can_go.append([y,x-1])
        # 右確認
        if x != w-1 and v_wall[y][x] != 1:
            can_go.append([y,x+1])
        # 上確認
        if y != 0 and h_wall[y-1][x] != 1:
            can_go.append([y-1,x])
        # 下確認
        if y != h-1 and h_wall[y][x] != 1:
            can_go.append([y+1,x])
        
        if not can_go:
            continue

        for ny,nx in can_go:
            if visited[ny][nx]:
                continue

            que.append([ny,nx])
            visited[ny][nx] = 1
            length[ny][nx] = length[y][x]+1
    
    if length[h-1][w-1] != inf:
        print(length[h-1][w-1])
    else:
        print(0)



33　AtCoder Beginner Contest 088 D - Grid Repainting

問題文
atcoder.jp

問題文を言い換えると
「最短距離のマス目以外を黒くするにはあと何マス塗りつぶせばいいですか？」
となります

よって答えは、
「全マスの個数H＊W - 最短距離 - すでに黒いマスの個数」
です

pythonでの実装例

from collections import deque

inf = 10**10

h,w = map(int,input().split())
field = [input() for _ in range(h)]

length = [[inf for j in range(w)]for i in range(h)]
visited = [[0 for j in range(w)]for i in range(h)]

move = [[-1,0],[1,0],[0,-1],[0,1]]

que = deque([])
que.append([0,0])
length[0][0] = 1 # １スタート
visited[0][0] = 1

white = 0

for i in range(h):
    white += field[i].count(".")

while que:
    y,x = que.popleft()

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        elif field[ny][nx] == "#":
            continue
        elif visited[ny][nx] == 1:
            continue
        
        visited[ny][nx] = 1
        que.append([ny,nx])
        length[ny][nx] = length[y][x] + 1

if length[h-1][w-1] == inf:
    print(-1)
else:
    print(white-length[h-1][w-1]) # 白の総数から最小距離分引く

Atcoder水色への精選 100 問　深さ優先探索(Python)

AtCoder Python 競プロ精進 精選100問 深さ優先探索

水色になるための精選100問、
今回は24~27までの「深さ優先探索」です

再帰は前から苦手だったので理解するいい機会になりました

qiita.com

前回↓
二分探索
algo-archit.hatenablog.com

目次



24　ALDS_11_B - 深さ優先探索

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B

深さ優先探索では、目的のノードをみつけるか、探索できる子ノードがなくなるまで探索を行っていきます
スタックを使った方法や再帰関数を用いた解き方ができます

この問題ではたどり着いた時間だけでなくそのノードについて一通り調べ終わった順番まで記録しなければいけなかったので再帰的な手法で解きました

ネットワークとして全てのノードがつながっているとは限らない点に注意です

pythonでの実装例

n = int(input())
v_list = [[] for _ in range(n+1)]

for _ in range(n):
    li = list(map(int,input().split()))
    u,k = li[:2]
    v = li[2:]
    v.sort()
    v_list[u] += v

inf = 10**8

d = [inf for _ in range(n+1)]
f = [inf for _ in range(n+1)]

time = 1

def dfs(now):
    global time

    # 探索済みだった場合中断
    if d[now] != inf:
        return

    d[now] = time
    time += 1

    for i in v_list[now]:
        dfs(i)
    
    f[now] = time
    time +=1

# 1番目から探索を開始（孤立ノードに注意）
for i in range(1,n+1):
    dfs(i)

    print(i,d[i],f[i])



25　AOJ 1160 - 島はいくつある？

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160

まずW＊H個のすべてのマスについて１つづつ探索を行います
未だ探索されておらず、かつ島のマスがあった場合、そのマスを始点として深さ優先探索を隣接する8マスに対して行います
また島の個数を１カウント増やします

この際、探索をし終わった島のマスを海のマスに変更することで重複して島をカウントするのを防ぐことができます

pythonでの実装例

while True:
    w,h = map(int,input().split())

    if w == 0 and h == 0:
        break

    c = [list(map(int,input().split())) for _ in range(h)]
    visited = [[0 for i in range(w)]for j in range(h)] # 訪問したか確認

    island = 0 # 島の個数
    xy_move = []
    
    # 8方向のパターン
    for i in range(-1,2):
        for j in range(-1,2):
            if not(i == 0 and j == 0):
                xy_move.append([i,j])

    # 全てのマスに関して探索　
    for i in range(w):
        for j in range(h):
            # 海or探索済みだった場合打ち切り
            if visited[j][i] == 1 or c[j][i] == 0:
                continue

            stack = [[i,j]]
            island += 1

            while stack:
                x,y = stack.pop()
                c[y][x] = 0 # 自身は塗りつぶす

                for k in xy_move:
                    x_move,y_move = k
                    nx = x+x_move
                    ny = y+y_move

                    if 0 <= nx < w and 0 <= ny < h and c[ny][nx] == 1 and visited[ny][nx] == 0:
                        visited[ny][nx] = 1
                        c[ny][nx] = 0 # 自身は塗りつぶす
                        stack.append([nx,ny])

    print(island)



26　AtCoder Beginner Contest 138 D - Ki

問題文
atcoder.jp

「各 i (1 ≤ i ≤ N −1)に対して頂点 ai が bi の親であるとは限らない」（解説引用）ため、再帰を使わない深さ優先探索では問題を解くことができません（コンテスト本番中はこの制限に引っかかるテストケースがなかったためACできたみたいですがAfter Contestテストケースが追加されました）

そこで親ノードに至るまでの加算値を再帰関数の引数として残しておき、自身の加算値と合計したのちに子ノードに引き継ぐという方針を取りました

自分のノードが加算値の対象になるかを辞書型を用いて管理しています（リストでも問題なし）

pythonでの実装例

from collections import defaultdict
from sys import setrecursionlimit # 再帰エラー対策
setrecursionlimit(10 ** 7)

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

connection = [[] for _ in range(n+1)]
counter = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
point_dic = defaultdict(int)

for _ in range(n-1):
    a,b = map(int,input().split())
    connection[a].append(b)
    connection[b].append(a)

# 各ノードの加算値を記録
for _ in range(q):
    p,x = map(int,input().split())
    point_dic[p] += x

# 現在のノード(node)とそれまでに加算された値(before_point)
def dfs(node,before_point):
    if visited[node]:
        return
    
    # 現在のノードの加算値を足す
    if point_dic[node]:
        point = point_dic[node]+before_point
    else:
        point = before_point
    
    # 訪問済みにする
    visited[node] = 1
    counter[node] += point

    for i in connection[node]:
        if visited[i]:
            continue

        dfs(i,point) # 再帰して子ノードに引き継ぐ

dfs(1,0)

print(' '.join(map(str, counter[1:])))



27　JOI 2009 予選 4 - 薄氷渡り

問題文
atcoder.jp

氷を適切に割っていった際に何区間移動できるかを聞いた問題です

移動を行う際に、現在の深さを引数にとっておき、移動後の深さがそれまでの最大深さより大きい値になった場合更新をします

またその地点を訪問した際の広場のリスト(どこまで氷を割ったかのリスト)を見るために、再帰したときに一旦氷を割る動作を行い
その地点から行きうるすべての地点を探索し終わったら氷を元の状態に戻します

M*N個のすべての地点からスタートした際の最大深さがどうなるかを調べればOKです

現在の状態をこのように保持するやり方は知らなかったので新鮮でした

pythonでの実装例

m = int(input())
n = int(input())

place = [list(map(int,input().split())) for _ in range(n)]
move = [[-1,0],[1,0],[0,-1],[0,1]]
max_depth = 0 # 最大で行ける深さ

def dfs(x,y,now_depth):
    global depth

    place[y][x] = 0 # 氷を割る

    if now_depth > depth:
        depth += 1 # 深さの最大値を超えた場合更新する

    for x_move,y_move in move:
        nx = x+x_move
        ny = y+y_move

        if 0 <= nx < m and 0 <= ny < n and place[ny][nx] == 1:
            dfs(nx,ny,now_depth+1)
    
    place[y][x] = 1 # 元に戻す(地点を探索する前のリストの状態にする)
        
# 全てのマス目に対して可能性を試す
for i in range(n):
    for j in range(m):
        if place[i][j] == 0:
            continue
        
        depth = 0
        dfs(j,i,1)

        max_depth = max(max_depth,depth)

print(max_depth)

↓次回　幅優先探索
algo-archit.hatenablog.com

Atcoder水色への精選 100 問　二分探索(Python)

AtCoder Python 競プロ精進 精選100問 二分探索

水色になるための精選100問、前回から大分空いてしまいましたが引き続き更新していきます
今回は18~23までの「二分探索」です

qiita.com

前回↓
順列全探索
algo-archit.hatenablog.com

目次



18　ALDS_4_B - 二分探索

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B

pythonの二分探索ライブラリであるbisectを使います
bisect.bisect_right(もしくはbisect.bisect)で挿入したい数字をリストに入れたときの右端のインデックスを
bisect.bisect_leftで挿入したい数字をリストに入れたときの左端のインデックスを返してくれます

今回の問題ではこの両者の差が1以上の場合にカウントすることで解くことができます

pythonでの実装例

import bisect

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

point = 0

for i in t:
    if bisect.bisect_right(s,i)-bisect.bisect_left(s,i) > 0:
        point += 1
    
print(point)



19　JOI 2009 本選 2 - ピザ

問題文
https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4
ジャッジページ
atcoder.jp

店の配置を記録するリストの先頭と末尾に０とｄを追加してあげればOKです
右側と左側のそれぞれ最も近い位置の店のうち、距離が短い方を答えに足します

pythonでの実装例

import bisect

d = int(input())
n = int(input())
m = int(input())
# 店の座標（１番目の店だけ先頭と後方につける）
shop = [0]+[int(input()) for _ in range(n-1)] + [d]
shop.sort()
# 配送先
delivery = [int(input()) for _ in range(m)]

ans = 0

for i in delivery:
    # 隣の一番近い店の座標を求める
    rightside_shop = shop[bisect.bisect(shop,i)]
    leftside_shop = shop[bisect.bisect(shop,i)-1]

    ans += min(abs(rightside_shop-i),abs(leftside_shop-i))

print(ans)



20　AtCoder Beginner Contest 077 C - Snuke Festival

問題文
atcoder.jp

各段ごとにパターンを列挙していては到底間に合いそうにありません
そこで少し工夫をして解く必要があります

祭壇のうち真ん中の段について残り二つの段については条件が一度に定まることに注目します
中段の祭壇について全探索を行い、条件を満たす上段と下段の組み合わせを二分探索によって求めることで計算を高速にすることができます

pythonでの実装例

import bisect

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
c.sort()

ans = 0
C = len(c)

# Bを中心に考える
for i in b:
    ans += (bisect.bisect_right(a,i-1))*(C-bisect.bisect_left(c,i+1))

print(ans)



21　AtCoder Beginner Contest 023 D - 射撃王

問題文
atcoder.jp

すべての風船のペナルティをｐ以下にでき、かつ各風船を割るときの時間が負にならないようなpの値を二分探索で求めます

条件を満たさなかった場合ｐの下限を変更、満たす場合ｐの上限を変更することで最終的に答えを求めることができます

こういった形式の類題として以下の問題も参考になると思います
atcoder.jp

pythonでの実装例

import numpy as np

n = int(input())
h,s = [],[]

for _ in range(n):
    i,j = map(int,input().split())
    h.append(i)
    s.append(j)

h = np.array(h,dtype=np.int64)
s = np.array(s,dtype=np.int64)

# 全てのペナルティをp以下にできるかで二分探索
hi = 10**18
low = 0

def min_pena(p):
    # 各風船のペナルティをｐ以下にするためにかかる時間
    time = (p-h)//s
    time.sort()
    # 各風船の時間がマイナスになっていないかを判定
    return (time >= np.arange(n)).all()

while hi-low > 1:
    mid = (hi+low)//2
    if min_pena(mid):
        hi = mid
    else:
        low = mid

print(hi)



22　AtCoder Regular Contest 054 B - ムーアの法則

問題文
atcoder.jp

様々な解法が考えられる問題ですが、今回は二分探索の解き方でやります
三分探索のpythonに関する解法はじゅっぴーさんのこちらのブログが参考になりました
↓
juppy.hatenablog.com

問題の式は凸関数と凸関数の和なので凸関数になります（解説文引用）
式として書くと
f(x) = x + p\cdot2^{-\frac{2}{3}x} です

これを微分すると
f'(x) = 1- \frac{2p\log 2}{3\cdot2^{\frac{2}{3}x}}

になり、この f'(x)が0を取るようなxの値を求め、 f(x)に代入した答えを2分探索すればOKです

実際には f'(x)=0となるxを計算すると
x = \frac{3}{2}\log_{2} (\frac{2p\log 2}{3})

となるのでこれを代入しても正解を得られます

今回のように微分の式が複雑で解きにくい場合はsympyなどで正解となるxを求めてプログラムに代入するだけでも大丈夫だと思います(REが出るので直接使うことはできませんが)

あとhighの値を極端に大きく設定するとオーバーフローエラーを起こすので注意です


pythonでの実装例

from math import log

p = float(input())

# かかる時間の計算式
def f(x):
    return x+p/2**(2*x/3)

# f'(x) : 微分したもの
def diff(x):
    return 1-2*p*log(2)/(3*2**(2*x/3))
   
high = 10**3
low = 0

# 傾きが0になるxを2分探索（x<0の場合もあるためlow=0に設定）
while high-low > 10**(-10):
    mid = (high+low)/2
    if diff(mid) < 0:
        low = mid
    else:
        high = mid

print(f(high))



23　JOI 2008 本選 3 - ダーツ

問題文
atcoder.jp
※リンク先からさらに問題文のpdfを開く必要があります

ダーツを投げなかった場合を0点として考えます
４本のダーツの得点の組み合わせは０点の時も含めて(n+1)**4通りもあるのでn = 1000の時にTLEを起こしてしまいます

そこで最初に２本投げたときの得点の合計値の可能性を全列挙し、ソートしておきます
その後残りの２本を投げたときの得点の可能性を求めます

この際、「m点を超えないような残り２本の得点の合計（m-i番目の値）が取りうる最大値」を先ほどソートしたリストを使って二分探索します

合計得点がｍを超えなかったもののうち、最大となる得点が答えです

pythonでの実装例

import bisect
from itertools import combinations_with_replacement

n,m = map(int,input().split())
p = [int(input()) for _ in range(n)]+[0] # 投げなかった時の0点も含める

# ダーツ2本の合計得点の組み合わせ全列挙(同じダーツを選ぶ場合があることに注意)
two_darts = [sum(i) for i in combinations_with_replacement(p,2)]
two_darts.sort()

max_point = 0

# m-i以下を満たす範囲での残り2本投げた際の最大得点を求める
for i in two_darts:
    ans = two_darts[bisect.bisect_right(two_darts,m-i)-1]+i

    if ans > m:
        continue

    max_point = max(max_point,ans)

print(max_point)

↓次回　深さ優先探索
algo-archit.hatenablog.com

Atcoder水色への精選 100 問　全探索：順列全探索(Python)

AtCoder Python 競プロ精進 全探索 精選100問 順列

水色になるための精選100問、
今回は15~17までの「全探索：順列全探索」です

qiita.com

前回↓
ビット全探索
algo-archit.hatenablog.com

目次



15　AtCoder Beginner Contest 145 C - Average Length

問題文
atcoder.jp

座標群を並び替え、どの順番で行くかの順列を全探索すればOKです
距離の計算だけ注意です

pythonでの実装例

from itertools import permutations
import math

n = int(input())
li = [tuple(map(int,input().split())) for _ in range(n)]

# 2点間の距離
def length(x1,y1,x2,y2):
    return(math.sqrt(abs(x2-x1)**2+abs(y2-y1)**2))

point = 0

for i in permutations(li):
    for j in range(1,n):
        point += length(i[j-1][0],i[j-1][1],i[j][0],i[j][1])

print(point/math.factorial(n))



16　AtCoder Beginner Contest 150 C - Count Order

問題文
atcoder.jp

並び替えられたリストから、何番目に出てくるかを調べる問題です
こういった時、pythonのitertools関数のpermutationを使うとリストの順列を簡単に生成できるので便利です

for i , j enumerate( list ) の形でリストのインデックスと中身を同時に取り出すことができます
（python辞書型のitemsのようなもの）

pythonでの実装例

from itertools import permutations

n = int(input())
li = [i for i in range(1,n+1)]
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

# pとqが何番目に出てくるかを記録
for i,j in enumerate(permutations(li)):
    if j == p:
        num_p = i
    if j == q:
        num_q = i

print(abs(num_p-num_q))



17　ALDS_13_A - 8 クイーン問題

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A

8×8マスのうちどの８マスにコマを置くかを全通り考えてしまうと
{}_6{}_4 C _8 = 178,462,987,637,760通りもあるので間に合いそうもありません

そこで正解となる置き方において、どの行でもクイーンの個数は１個しかないことに注目します
そのような行の並べ方は８個存在するので、それをどの順番で積み重ねていくかを全探索です

次に、生成された盤面が、先に与えられるK個のコマの配置と一致しているかを考えます

その後、縦方向と横方向にクイーンが被ることはないので、残り斜め方向の被りがないかだけチェックします
チェックにはいろいろ方法がありそうですが私は「右上（左上）からの距離が等しいマスにクイーンは2つ以上存在しない」という条件で探索しました

以下は４×４マスの例です
これで斜め方向にクイーンが２個以上存在するかを調べることができます

f:id:algo_archit:20200619040132p:plain

右下斜め方向、左下斜め方向が条件を満たすような盤面は１つに限られるのでそれを出力します

pythonでの実装例

from itertools import permutations

n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
chess = [["." for i in range(8)]for j in range(8)]

for i in range(8):
    chess[i][i] = "Q"

# 行のchessの並べ方を探索
for patern in permutations(chess):
    for y,x in li:
        if patern[y][x] != "Q":
            break
    else:
        rd = [0]*15 # i+jの合計を記録（右下斜め方向）
        ld = [0]*15 # 7-i+jの合計を記録（左下斜め方向）
        for i in range(8):
            for j in range(8):
                if patern[i][j] == "Q":
                    rd[i+j] += 1
                    ld[i+(7-j)] += 1
        for k in range(15):
            # 各斜め方向には１つまでしかQがあってはならない
            if rd[k] > 1 or ld[k] > 1:
                break
        else:
            for l in patern:
                print("".join(l))

↓次回　二分探索
algo-archit.hatenablog.com

Atcoder水色への精選 100 問　全探索：ビット全探索(Python)

AtCoder Python 競プロ精進 全探索 精選100問 bit全探索

水色になるための精選100問、
今回は10~14までの「全探索：ビット全探索」です

qiita.com


(※bit全探索を知らない方へ：bit全探索に関するpythonの詳しい解説は以下がおすすめです）
qiita.com



前回↓
工夫して通り数を減らす全列挙
algo-archit.hatenablog.com

目次



10　ALDS_5_A - 総当たり

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

N個の数字からどれを選ぶのかをbit全探索します

ここで各bitごとに０か１かの２通りの可能性があることから
2^n通りの可能性を試せば大丈夫です
今回はmax_n = 20なので100万通り

1 << n と 2^nは同じ意味なことに注意です

pythonでの実装例

n = int(input())
a = list(map(int,input().split()))
pos = set()

# n桁分のbit探索
for i in range(1 << n):
    point = 0
    for j in range(n):
        # j個目の商品が含まれるか
        if (i >> j)&1:
            point += a[j]
    # 作ることができるものをsetに加えていく
    pos.add(point)

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

for i in m:
    if i in pos:
        print("yes")
    else:
        print("no")



11　AtCoder Beginner Contest 128 C - Switches

問題文
atcoder.jp

問題文は少し難解ですが、N個のスイッチのうちONにするものをbit全探索していき、各パターンで電球は点灯するのかどうかを検証します

pythonでの実装例

n,m = map(int,input().split())
li = [list(map(int,input().split()))[1:] for _ in range(m)]
p = list(map(int,input().split()))
ans = 0

for i in range(1 << n):
    switch = set()
    # どのスイッチがONになっているか
    for j in range(n):
        if (i >> j)&1:
            switch.add(j+1)
    # 点灯条件を満たすか
    for k in range(m):
        point = 0
        for l in li[k]:
            if l in switch:
                point += 1
        if point%2 != p[k]:
            break
    else:
        ans += 1

print(ans)



12　AtCoder Beginner Contest 002 D - 派閥

問題文
atcoder.jp

派閥に含める人の選び方をbit全探索します
選ばれた人から２人を選ぶときに矛盾が生じないかを確認すれば大丈夫です

pythonでの実装例

from itertools import combinations

n,m = map(int,input().split())
rel = {}

# ハッシュテーブルで管理
for _ in range(m):
    x,y = map(int,input().split())
    rel[x,y] = True

max_num = 1 # 作成可能な派閥の最大人数

# どの人を派閥に加えるか
for i in range(1 << n):
    human = []
    for j in range(n):
        if (i >> j)&1:
            human.append(j+1)
    for k,l in combinations(human,2):
        if (k,l) not in rel:
            break
    else:
        max_num = max(max_num,len(human))

print(max_num)



13　JOI 2008 予選 5 - おせんべい

問題文
atcoder.jp

どの列のおせんべいを裏返すかをbit全探索します
裏返すときにはその列の要素全体に対して１とXORでかけ合わせます
( 0 XOR 1 = 1, 1 XOR 1 = 0　なので )

こういった行列全体への計算にはnumpyを使うと便利です

また裏返し処理が終わったあと、各列の裏返っているせんべいの枚数をカウントします（Aと仮定）
この際に、その列の裏返っている枚数がR-A枚未満だった場合は列をひっくり返すのが最適です

pythonでの実装例

import numpy as np

r,c = map(int,input().split())
senbei = [list(map(int,input().split())) for _ in range(r)]
senbei = np.array(senbei,dtype=np.int64)
senbei_max = 0 # せんべいの最大枚数

# どの列を裏返すかをbit全探索する
for i in range(1 << r):
    senbei_c = np.copy(senbei)
    for j in range(r):
        if (i >> j)&1:
            senbei_c[j] ^= 1 # ひっくり返す
    count = senbei_c.sum(axis=0) # 現在の状態の列の裏返っている個数
    senbei_num = np.maximum(count,r-count).sum()
    senbei_max = max(senbei_num,senbei_max)

print(senbei_max)



14　Square869120Contest #4 B - Buildings are Colorful!

問題文
atcoder.jp

どの建物をｋ個以上見えるようにしたいかをbit探索します
i番目の建物が見えてほしいとき、i-1番目までの最高高さがi番目の建物以上の場合i番目の建物の高さをmax(a[ : i ])+1にします

pythonでの実装例

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**20

# どのビルを見るかをbit全探索
for i in range(1 << n):
    li = []
    for j in range(n):
        if (i >> j)&1:
            li.append(j)
    if len(li) < k:
        continue
    point = 0
    now = a[0]# 最大高さ
    for l in range(1,n):
        if l in li and a[l] <= now:
            point += now+1-a[l]
            now += 1
        # 最大高さ更新
        now = max(now,a[l])
    ans = min(ans,point)

print(ans)

次回↓
順列全探索(15~17まで)
algo-archit.hatenablog.com

Atcoder水色への精選 100 問　全探索 : 工夫して通り数を減らす全列挙(Python)

AtCoder Python 競プロ精進 全探索 全列挙 精選100問

引き続き水色になるための精選100問を解いていきます
今回は5~9までの「全探索 : 工夫して通り数を減らす全列挙」です

qiita.com

前回↓
全列挙
algo-archit.hatenablog.com


目次



5　AtCoder Beginner Contest 095 C - Half and Half

問題文
atcoder.jp

ABピザを２枚で１セットC×2円で考えると
ABピザを何セット分買うかを全探索することで残りのA,Bピザを何枚買うかを求めることができます

pythonでの実装例

a,b,c,x,y = map(int,input().split())
ans = 10**10

# ABピザ２枚セットを何枚分買うか
for i in range(max(x,y)+1):
    point = 2*c*i
    # 足りない分は買い増し
    if i < x:
        point += a*(x-i)
    if i < y:
        point += b*(y-i)
    ans = min(ans,point)

print(ans)



6　三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

問題文
atcoder.jp

暗証番号の個数はせいぜい000~999までの1000通りなので
これらの番号が文字列から生成することができるかを全列挙することで問題は解けます
しかしながら以下のようなコードをPythonで提出しようとしても間に合いません(PyPy3だと500msくらいで間に合う)

TLE例

n = int(input())
s = input()
point = 0

# 暗証番号を全探索する
for i in range(1000):
    t = str(i).zfill(3)
    now = 0
    # sで暗証番号が作れるかを検証
    for j in s:
        if j == t[now]:
            now += 1
        if now == 3:
            point += 1
            break

print(point)

そこで少し工夫をして、暗証番号を１桁づつ見ていき、Sから作ることができない数を除外してやると間に合わせることができます

pythonでの実装例

n = int(input())
s = input()
point = 0

# 100の位
for i in range(10):
    # Sのn-2番目までにiがあるか
    str_i = str(i)
    for a in range(n-2):
        if s[a] == str_i:
            now_i = a
            break
    # 作れなかった場合打ち切り
    else:
        continue
    # 10の位
    for j in range(10):
        str_j = str(j)
        for b in range(now_i+1,n-1):
            if s[b] == str_j:
                now_j = b
                break
        else:
            continue
        # 1の位
        for k in range(10):
            str_k = str(k)
            for c in range(now_j+1,n):
                # 暗証番号がそろった
                if s[c] == str_k:
                    point += 1
                    break

print(point)



7　JOI 2007 本選 3 - 最古の遺跡

問題文
https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf#page=5

柱を２点選び、残りの２点を正方形の形になるように座標を求めた際に、その位置に柱が存在するかを確認できればOKです
注意書きがあった通りPythonで解こうとすると下手なコードではTLEを起こしてしまいます
itertoolsのcombinationやset型を用いることでなんとか間に合わせることができました

pythonでの実装例

from itertools import combinations

n = int(input())
xy = [tuple(map(int,input().split())) for _ in range(n)]
set_xy = set(xy)

# 面積の最大値
max_s = 0

# 2点の組み合わせ
for (x1,y1),(x2,y2) in combinations(xy,2):
    dx = x1-x2
    dy = y1-y2
    # 残りの２点の座標が柱として存在するかを検索
    if (x2-dy,y2+dx) in set_xy and (x1-dy,y1+dx) in set_xy:
        # 存在した場合面積を更新する
        max_s = max(max_s,(x1-x2)**2+(y1-y2)**2)

print(max_s)



8　Square869120Contest #6 B - AtCoder Markets

問題文
atcoder.jp

与えられた地点の最小値から最大値までの範囲でスタートとゴールを全探索します

A A地点 -> B地点 -> ゴール
となるように移動するのが最短経路になります

中央値を使った求め方もできるようです
以下の解答リンク参照
https://img.atcoder.jp/s8pc-6/editorial.pdf

pythonでの実装例

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n)]
set_ab = set()
ans = 10**20

for i,j in ab:
    set_ab.add(i)
    set_ab.add(j)

set_ab = list(set_ab)
S = len(set_ab)

# スタートとゴールの範囲を全探索する
for i in range(S-1):
    for j in range(i,S):
        point = 0
        for a,b in ab:
            point += abs(set_ab[i]-a) # start -> a
            point += abs(set_ab[j]-b) # b -> goal
            point += b-a # a -> b
        ans = min(ans,point)

print(ans)



9　JOI 2008 予選 4 - 星座探し

問題文
atcoder.jp

与えられたN個の星を星座の中の１地点と一致させるときのずれを記録し、残りのN-1個の星座+ずれ分の座標がM個の星の中にあるかを全探索します
M個の座標をハッシュテーブル(Pythonの辞書型)で管理することで計算量O(N*M)で解くことができます（この問題の制限時間ではあまり関係ありませんが）

pythonでの実装例

m = int(input())
star = [tuple(map(int,input().split())) for _ in range(m)]
star.sort()

n = int(input())
stars = [tuple(map(int,input().split())) for _ in range(n)]
stars.sort()

# ハッシュテーブルで管理
dic = {}
for i,j in stars:
    dic[i,j] = True

for i,j in stars:
    # 星座の一つめの星とのずれを記録
    x_gap = i-star[0][0]
    y_gap = j-star[0][1]
    for k,l in star:
        if (k+x_gap,l+y_gap) not in dic:
            break
    # breakが発生しなかった場合
    else:
        print(x_gap,y_gap)
        exit()

次回↓
bit全探索
algo-archit.hatenablog.com

Atcoder水色への精選 100 問　全探索 : 全列挙(Python)

AtCoder Python 競プロ精進 全探索 全列挙 精選100問

E869120さんが作成した、精選100問を解いていきます
今回は1~4までの「全探索 : 全列挙」をやります
qiita.com

目次



1　How many ways?

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

２つ目までの範囲を決めたときの残った３番目の要素が目的の数値に等しいかをカウントします
（ちなみに３番目までを全探索したときでも 10^6程度なので間に合うっぽい）

pythonでの実装例

li = []

while True:
    n,m = map(int,input().split())
    if n == 0 and m == 0:
        break
    li.append((n,m))

for n,m in li:
    point = 0
    for one in range(1,n-1):
        for two in range(one+1,n):
            three = m-one-two
            if two < three < n+1:
                point += 1
    print(point)



2　B - 105

問題文
atcoder.jp

１からNまでの奇数のうち、各数字の約数を全列挙したときの長さが８のものの個数をカウントします

pythonでの実装例

n = int(input())

# 約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

point = 0

# 奇数全探索
for i in range(1,n+1,2):
    j = make_divisors(i)
    if len(j) == 8:
        point += 1

print(point)



3　AtCoder Beginner Contest 122 B - ATCoder

問題文
atcoder.jp

部分文字列を全探索していきます(空文字は除く)
部分文字列の先頭と終了地点を決め、作られた文字列がACGT文字列だった場合をカウントします
ACGT文字列だった場合、さらに文字列の長さが今までのACGT文字列よりも長かった場合、更新をします
フラグ管理やmax関数を使うと便利です

pythonでの実装例

s = input()
n = len(s) # 文字の長さ
max_length = 0 # 最大長さ

for i in range(n):
    for j in range(i,n):
        t = s[i:j+1]
        flag = True # ACGT文字列であるかのフラグ
        for k in t:
            if k not in "AGCT":
                flag = False
        if flag:
            max_length = max(max_length,len(t))

print(max_length)



4　C - カラオケ

問題文
atcoder.jp

1曲目と2曲目の組み合わせを求めておき、各パターンの得点を数えます
得点が過去の最大値を上回った場合は更新をします

pythonでの実装例

n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]

ans = 0

# 1曲目と2曲目を全探索する
for i in range(m-1):
    for j in range(i+1,m):
        point = 0
        # n人が曲を歌った時の得点を求める
        for k in range(n):
            point += max(a[k][i],a[k][j])
        # 最大値を更新 
        ans = max(ans,point)

print(ans)

次回↓
工夫して通り数を減らす全列挙
algo-archit.hatenablog.com