読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC020を解いてみた

競技プログラミング

A問題

 qの値に合わせて出力する内容を変えます。

q = int(input())

if q == 1:
    print("ABC")
else:
    print("chokudai")

B問題

 文字列として入力をそれぞれ受け取り連結しました。そして、整数型に変換して2倍したものを出力しました。

a, b = input().split()

c = a + b
c = int(c)

print(c*2)

C問題

 全探索する方法しか思いつかなかったので解説を見ました。蟻本を参考にダイクストラ法と二分探索を組み合わせて実装しましたが、全てのケースでREになってしまいました… 手元の環境でREを再現できない…

import math
#入力
h, w, t = map(int, input().split())
board = [[i for i in input()] for j in range(h)]

# route_list[i][j] は i から j へのコスト
# ノードの番号は左上が0で右下が最大 
# 0 1 2 3
# 4 5 6 7 みたいな感じ
route_list = [[math.inf for i in range(h*w)] for j in range(h*w)]
moveCol = [0, 0, 1, -1]
moveRow = [1, -1, 0, 0]

low = 1
high = t
mid = int((low + high) / 2)

while True:
    # 入力をグラフとして隣接行列の形に落とし込む
    for i in range(w):
        for j in range(h):
            # 探索元のノードの番号
            current_node_num = (j * w) + i

            # startとgoalのノードの番号
            if(board[j][i] == 'S'):
                start_node_num = j * w + i
            elif(board[j][i] == 'G'):
                goal_node_num = j * w + i

            for k in range(4):
                # つながっている次のマスはどこか
                nextx = i + moveCol[k]
                nexty = j + moveRow[k]
                # print("i:{0} j:{1} k:{2} nextx:{3} nexty:{4}".format(i, j, k, nextx, nexty))

                # 次のマスが枠外になっていなかったら
                if( 0 <= nextx and nextx < w and 0 <= nexty and nexty < h):
                    # 次のマスのノードの番号
                    next_node_num = nexty * w + nextx

                    # 次に行くのが黒いマス 黒いマスにうつるのはx秒かかる
                    if(board[nexty][nextx] == '#'):
                        route_list[current_node_num][next_node_num] = mid
                    else:
                        route_list[current_node_num][next_node_num] = 1

    # スタートからの最短距離
    d = [math.inf for i in range(w*h)]
    # 使われたかのフラグ
    used = [False for i in range(w*h)]

    # 始点への距離は0
    d[start_node_num] = 0

    # ダイクストラ法
    while True:
        v = -1
        # まだ使われていない頂点のうち距離が最小のものを探す
        for u in range(h*w):
            if ((not used[u]) and (v == -1 or d[u] < d[v])): v = u

        # すでに全部探索していればループを抜ける
        if(v == -1):
            break
        # 番号vの使用されたかのフラグをTrueにする
        used[v] = True

        # 今までのと今回のループで短いほうを最小の距離とする
        for u in range(w*h):
            d[u] = min(d[u], d[v] + route_list[v][u])

    # 時間内にたどり着けるなら
    if(d[goal_node_num] <= t):
        low = mid
    else:
        high = mid
    mid = int((low + high) / 2)

    # 条件を満たすまで2分探索
    if(high - low == 1):
        break

    #print("low:{0} mid:{1} high:{2}".format(low, mid, high))

print(low)

D問題

 自力では15点まで、解説読んで100点分までは実装できました。満点解法は包除定理の実装部分で詰まったのでできたら追記します…