2019-09-13

JOI 2010 予選 E チーズ

の続きです。

BFSの続き。迷路には、'X'と'.'と1~9までの数字が埋まっており、スタートからマスを進んで、1~9を順番に取っていき、その時の最小手数を求めてねという問題。

from collections import deque
BIG = 1000000


def main():
    h, w, k = [int(i) for i in input().split()]
    f = []
    for i in range(h):
        line = list(input())
        for j, c in enumerate(line):
            if c == 'S':
                sy, sx = [i, j]
        f.append(line)

    turn = [[[BIG, 0] for i in range(w)] for j in range(h)]
    turn[sy][sx][0] = 0
    turn[sy][sx][1] = 1
    q = deque([[sy, sx]])
    # 探してる数
    c = 1
    y, x = (0, 0)

    while q:
        y, x = q.pop()
        if f[y][x] == str(c):
            c += 1
            if c > k:
                break
            q.clear()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w and \
                f[ny][nx] != 'X' and turn[ny][nx][1] < c:
                # 訪れたとこを記録していない
                turn[y+dy][x+dx][0] = turn[y][x][0] + 1
                turn[y+dy][x+dx][1] = c
                q.appendleft([ny, nx])
    print(turn[y][x][0])

if __name__ == '__main__':
    main()

手数と、c (探している番号) で通ったかをメモりながら、進んでいく。1 s はかからなかったけど、0.8 msぐらいかかってて遅いなと思った。オリジナルの地図に書き込んで進もうと思ったんだけど、なかなかうまくいかなかった。なので、諦めて 2 個組を要素にもつ地図をコピーしてやった。思ってたより実装に時間がかかったり、既に行ったかどうかが抜けてたりして、時間がかかってしまった。

2019-09-12

AOJ 1160 島はいくつある？とABC 007 C 幅優先探索

競技プログラミング

qiita.com

DFSとBFSの問題。愚直な実装でいける。

import sys

sys.setrecursionlimit(1000000)


def rec(y, x, f):
    f[y][x] = '0'
    for dy, dx in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0),
            (1, 1)]:
        if 0 <= y+dy < len(f) and 0 <= x+dx < len(f[0]) and f[y+dy][x+dx] == '1':
            rec(y+dy, x+dx, f)


def main():
    while True:
        w, h = [int(i) for i in input().split()]
        if w == 0 and h == 0:
            break
        field = []
        for i in range(h):
            field.append(input().split())
        ans = 0
        for i in range(h):
            for j in range(w):
                if field[i][j] == '1':
                    rec(i, j, field)
                    ans += 1
        print(ans)
    print(0)


if __name__ == '__main__':
    main()

と

from collections import deque
BIG = 100000


def main():
    h, w = [int(i) for i in input().split()]
    sy,sx = [int(i)-1 for i in input().split()]
    gy,gx = [int(i)-1 for i in input().split()]
    field = []
    d = [[BIG for i in range(w)] for j in range(h)]
    for i in range(h):
        field.append(list(input()))
    q = deque()
    q.appendleft([sy, sx])
    d[sy][sx] = 0
    ans = 100000
    while q:
        y, x = q.pop()
        if y == gy and x == gx:
            break
        field[y][x] = '#'
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= y+dy < h and 0 <= x+dx < w and field[y+dy][x+dx] == '.' \
                and d[y+dy][x+dx] == BIG:
                q.appendleft([y+dy, x+dx])
                d[y+dy][x+dx] = d[y][x]+1
    print(d[gy][gx])


if __name__ == '__main__':
    main()

BFSは、既に訪れたところを訪れないようにしないと、時間がかかってTLEになるので、別フィールドを用意して、訪れたか判定するのが良い。

2019-09-10

ARC 037 B バウムテスト

競技プログラミング

qiita.com

の続きです。

問題は、与えらたグラフが、木を何個持つか答える問題。

最初に考えたWAのやつ。単方向。

""" 木である場合は、含まれる頂点を 1 度開始しか通らない """
visited = []
tree = []

def rec(i, mark):
    global visited
    visited[i] = True
    ans = True
    for j in tree[i]:
        if not visited[j]:
            ans &= rec(j)
        else:
            # 木であるものと仮定しているので
            ans &= False
    return ans


def main():
    global visited, tree
    n, m = [int(i) for i in input().split()]
    tree = [[] for i in range(n)]
    for i in range(m):
        u, v = [int(j)-1 for j in input().split()]
        tree[u].append(v)
    visited = [False for i in range(n)]
    ans = 0
    for i in range(n):
        if not visited[i]:
            if rec(i):
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

こいつだと例えば、

というような入力だと、後の閉路を含むグラフが、すでに探索済み(木とみなしたグラフ)と結合することによって、木の数が減らず、WRになる。

したがって、繋がっているものを一気に探索できればOK。逆方向の辺は、たどる時に消すことに注意する。

""" 最初は辺を双方向(単方向*2)にしておいて、訪れる時に、逆方向を消しておく """
visited = []; table = []


def rec(i):
    global visited, table
    visited[i] = True
    ans = True
    for to, v in enumerate(table[i]):
        # 辺があるか or もう訪れたか
        if v and not visited[to]:
            # 逆方向は消しておく
            table[to][i] = False
            ans &= rec(to)
        # 辺があるのに、行ったことがある
        elif v and visited[to]:
            ans &= False
    return ans


def main():
    global visited, table
    n, m = [int(i) for i in input().split()]
    table = [[False for j in range(n)] for i in range(n)]
    for i in range(m):
        u, v = [int(j)-1 for j in input().split()]
        table[u][v] = True
        table[v][u] = True
    visited = [False for i in range(n)]

    ans = 0
    for i in range(n):
        if not visited[i]:
            if rec(i):
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

今日は 1 問しかできなかったね。残念。

2019-09-08

ATC 001 A 深さ優先探索とARC 031 B 埋め立て

競技プログラミング

qiita.com

qiitaの初級編の問題。

ATC 001 A 深さ優先探索

深さ優先は、そのまんま

import sys

sys.setrecursionlimit(10000000)

f = []
h, w = 0, 0
def rec(y, x):
    if f[y][x] == 'g':
        return True
    f[y][x] = '#'
    ans = False
    for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] != '#':
            ans |= rec(y+dy, x+dx)
    return ans


def main():
    global f, h, w
    h, w = [int(i) for i in input().split()]
    start = []
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == 's':
                start = [i, j]
        f.append(list(s))
    print('Yes' if rec(*start) else 'No')


if __name__ == '__main__':
    main()

setrecursionlimitの値は適当です。1000ぐらいにしたらREで落ちたので。

ARC 031 B 埋め立て

問題は、10*10の 'o' or 'x' でできたマスのうち、'x' を 1 マスだけ 'o' に変えて、全ての 'o' の島をつなぐことができるか問う問題。

自分は、'x' のうち、上下左右が 'o' が、2 つ以上あるかどうかで、'o' に変える必要があるかどうかを検索した。全ての 'x' を試してもいい気がするが。あと、10 * 10 なので、戻す操作をせず、コピーして使うことにした。以下、ACコード

import sys

sys.setrecursionlimit(1000)


def rec(y, x, f):
    f[y][x] = 'x'
    for dy, dx in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
        if 0 <= y+dy < 10 and 0 <= x+dx < 10 and f[y+dy][x+dx] == 'o':
            rec(y+dy, x+dx, f)


def main():
    field = [list(input()) for i in range(10)]
    choice = []
    for y in range(10):
        for x in range(10):
            count = 0
            for dy, dx in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                if 0 <= y+dy < 10 and 0 <= x+dx < 10 and field[y+dy][x+dx] == 'o':
                    count += 1
            if count >= 2:
                choice.append([y, x])
    ans = False
    for y, x in choice:
        f2 = [line.copy() for line in field]
        rec(y, x, f2)
        tmp = True
        bs = False
        for line in f2:
            for c in line:
                if c == 'o':
                    tmp = False
                    # break switch
                    bs = True
                    break
            if bs:
                break
        ans |= tmp
        if ans:
            break
    print('YES' if ans else 'NO')


if __name__ == '__main__':
    main()

今日はあんまし考えることがなかったな。この調子で頑張るぞい。

2019-09-06

ABC 002 D - 派閥

競技プログラミング

はい、昨日完成できなかった問題。布団に入ったあと、すぐに浮かんだ解答。寝ようと思ったあとに、考えたり、思いつくのやめたい。昨日より、すっきりしたし、簡単だと思った。 bit全探索 $O(2^{n})$ で、頂点の組み合わせを出す。その後、それらの頂点が、互いに繋がっているときの、辺を無理やり出す。実際に、繋がっているか確認する。という手順でやった。n < 12なので、bit全探索をした上で組み合わせ計算しても間に合うくらいになってる(んだと思う)。

import itertools as it


def main():
    n, m = [int(i) for i in input().split()]
    table = [[False for j in range(n)] for i in range(n)]
    for i in range(m):
        x, y = [int(j) for j in input().split()]
        table[x-1][y-1] = True
    # bit全探索(頂点の組み合わせを出す)
    ans = 0
    for i in range(1<<n):
        tmp = []
        for j in range(n):
            if i >> j & 1:
                tmp.append(j)
        if len(tmp) < 2:
            continue
        edges = it.combinations(tmp, 2)
        if all(map(lambda x: table[x[0]][x[1]], edges)):
            ans = max(ans, len(tmp))
    print(ans if ans != 0 else 1)


if __name__ == '__main__':
    main()

2019-09-06

ARC 029 A - 高橋君とお肉と ABC 002 D - 派閥

競技プログラミング

けんちょんさんがまとめてくれてるqiitaのAtCoder精選問題集の問題(初級)。

高橋くんとお肉は、そんなに難しくなかった。樹形図的に2のN乗の全探索で、肉を2つの鉄板に振り分けていく問題。こういうパターンもあるのかという気持ちになった。

t = []
n = 0
def rec(i, a, b):
    if i == n:
        return max(sum(a), sum(b))
    ans = 10000

    a.append(t[i])
    ans = min(ans, rec(i+1, a, b))
    a.pop()

    b.append(t[i])
    ans = min(ans, rec(i+1, a, b))
    b.pop()

    return ans


def main():
    global n
    n = int(input())
    for i in range(n):
        t.append(int(input()))
    print(rec(0, [], []))


if __name__ == '__main__':
    main()

これで、ACした。

できてないのが、派閥。問題としては、幾何学っぽい感じがする。N 個の頂点が、互いにランダムに結びついていて、その中で、全ての頂点同士が結び付いているグループの最大頂点数を求める問題(だと思う)。

テストケース正解数が、62/70だから、88%ぐらいは、できてる(こんなこと言ったら、全部合ってこそ正解だバカヤローと言われてしまいそうだが)。

table = []


def rec(a):
    ans = 1
    if not a:
        return ans
    first = a[0]
    del a[0]
    common = set(table[first]) & set(a)
    nxt = sorted(list(common), key=lambda x: len(table[x]), reverse=True)
    ans += rec(nxt)
    return ans


def main():
    global table
    n, m = [int(i) for i in input().split()]
    table = [[] for i in range(n)]
    for i in range(m):
        x, y = [int(j) for j in input().split()]
        table[x-1].append(y-1)
    ans = 0
    for i in range(n):
        ans = max(ans, rec([j for j in range(i, n)]+[k for k in range(i)]))
    print(ans-1)


if __name__ == '__main__':
    main()

失敗するテストケースは、わかってるんだけど、探索の仕方がまだわかってなくて、部分的にこうじゃないかな、ぐらいの考えで書いてるからなんとも言えない感じ。近日中に解きたい(できれば明日)。

蟻本の練習問題は、英語だし、C++だし、あまり合わなかったんだけど、これなら、行けそうかもと思ってる。楽しくやるのが一番だけどね。こっちで慣れたらPOJもやりたみは、今のところあるし、このモチベでやっていきたひ。

2019-09-04

train ticket と all green

競技プログラミング

今日の競プロ。

train ticket は、与えられた4桁の数字の各桁を順番そのままに、引くか足すかして、=7ができるか問う問題。簡単な全探索でeval使って瞬殺。

def main():
    abcd = list(input())
    flag = False
    for op1 in ['+', '-']:
        for op2 in ['+', '-']:
            for op3 in ['+', '-']:
                ans = abcd[0]+op1+abcd[1]+op2+abcd[2]+op3+abcd[3]
                if eval(ans) == 7:
                    flag = True
                    print(ans+'=7')
                    break
            if flag:
                break
        if flag:
            break

if __name__ == '__main__':
    main()

問題は all green の方だったんだけど、正直なぞい。一応、解が、多くなかったから、移植してメモ。

def main():
    D, G = [int(i) for i in input().split()]
    p = []
    c = []
    for i in range(D):
        pp, cc = [int(i) for i in input().split()]
        p.append(pp); c.append(cc)
    ans = 1e9
    for mask in range(1<<D):
        s = 0; num = 0; rest_max = -1
        for i in range(D):
            # どのビットが立っているか確認する
            if mask >> i & 1:
                # i 番目の問題を全完した時の点数を追加する
                s += 100 * (i+1) * p[i] + c[i]
                num += p[i]
            else:
                # ビットが立っていない点数が一番高い問題のメモ
                # 足りなかったらここから解いて点数を追加する
                # 残ったやつ 1 つだけを見ればばいい
                # なぜなら、bit全探索で、他のパターンは自動的に出るから
                rest_max = i
        if s < G:
            # rest_max 番目の点数をあらかじめ計算しておく
            s1 = 100 * (rest_max+1)
            # 目標 - 今まで解いた問題の得点 + rest_max 番目の問題の得点 - 1
            need = (G - s + s1 - 1) // s1 # max になってはいけない
            if need >= p[rest_max]:
                continue
            num += need
        ans = min(ans, num)
    print(ans)


if __name__ == '__main__':
    main()

如何せん 27 行目。ここは、(G-s)//s1でやると、落ちる意味わからん。教えてエロい人。それは、置いといて、ビット全探索からの、問いてない点数が高い方から探索っていうのが、できなかった。解説動画のコメントで、これ、300?っていうのがあったけど、全く同感だった。きついわ。

いろんなことで四苦Hack（仮）

b1u3の技術ブログ

JOI 2010 予選 E チーズ

AOJ 1160 島はいくつある？とABC 007 C 幅優先探索

ARC 037 B バウムテスト

ATC 001 A 深さ優先探索とARC 031 B 埋め立て

ATC 001 A 深さ優先探索

ARC 031 B 埋め立て

ABC 002 D - 派閥

ARC 029 A - 高橋君とお肉と ABC 002 D - 派閥

train ticket と all green