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)

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

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

print(low)

D問題

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