トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

A - Buy a Pen

概要：赤、青、緑の3本のペンのうち1本を除外して最も安いものの金額を出力してね

$C$ で除外する対象の色が与えられるので、これを除いた2つの最小値を出力します。

$C$ は'Red'、'Blue'、'Green'のいずれかであるので、3パターンの分岐を書く必要があります。

#ABC362 A - Buy a Pen
R, G, B = map(int, input().split())
C = input()
if C == 'Red':
    print(min(G,B))
if C == 'Blue':
    print(min(R,G))
if C=='Green':
    print(min(R,B))

提出リンク：提出 #55513537 - トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

B - Right Triangle

リンク：B - Right Triangle (atcoder.jp)

概要：三角形の頂点の座標が与えられるので、この三角形が直角三角形かどうか判定してね

直角の判定ということでベクトルの内積を使います。

3つの頂点を仮に頂点a、頂点b、頂点cとして、 $\vec{ab}・\vec{ac}=(x_b-x_a) \times (x_c-x_a)+(y_b-y_a) \times (y_c-y_a)=0$ であれば頂点aは直角であることが判定できます。

#ABC362 B - Right Triangle
from itertools import combinations
X = []
Y = []
for _ in range(3):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
X += X[:2]
Y += Y[:2]
for i in range(3):
    xa, xb, xc = X[i:i+3]
    ya, yb, yc = Y[i:i+3]
    if (xb-xa)*(xc-xa) + (yb-ya)*(yc-ya) == 0:
        print('Yes')
        exit()
print('No')

提出リンク：提出 #55525012 - トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

C - Sum = 0

リンク：C - Sum = 0 (atcoder.jp)

概要：整数列 $X$ の各要素について値の取りうる範囲を $(L_i,R_i)$ で与えるので、うまいこと決めて $sum(X)=0$ にしてね

初期解決めてうまいこと値変えたいけどうまい方法が思いつかず仕舞。

頭から貪欲に決めていくことでいいみたいです。

初期解は全要素の最小値（もしくは最大値）として、合計値を0に近づけるように努力させればいいです。

$sum(L) \gt 0$ もしくは $sum(R) \lt 0$ ならば明らかに条件を満たさないのでNoを出力する
初期解を $L$ として、各要素について $L_i～R_i$ の中で合計を0にできるものがあるなら採用する。なければ $R_i$ に更新して次の要素へ

#ABC362 C - Sum = 0
N = int(input())
L = []
R = []
for _ in range(N):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
if sum(L) > 0 or sum(R) < 0:
    print('No')
    exit()
ans = L[:]
now = sum(ans)
for i in range(N):
    d = min(R[i]-L[i], -now)
    ans[i] += d
    now += d
print('Yes')
print(*ans)

提出リンク：提出 #55578052 - トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

D - Shortest Path 3

リンク：D - Shortest Path 3 (atcoder.jp)

概要：頂点と辺に重みがある単純連結無向グラフで経路の重みの最小値を教えてね

最短経路問題ということでダイクストラ法を使います。

頂点の重みは $A$ で、辺の重みは $b$ で与えられます。

辺だけでなく頂点にも重みがあるので、頂点 $u_i$ から辺 $i$ を通って頂点 $v_i$ に行くときの重みを $w = b_i + A_v$ とします。

出力するときは始点の重みを足し忘れずに。

ここまで分かってABC340くらいでつくったダイクストラ法を投げると2ケースでTLEしました。

たぶんダイクストラ法の中身で無駄な処理をしているんだと思います。

提出リンク：提出 #55536533 - トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

公式解析からダイクストラ法をもらってきてその他はそのままでACできました。もったいない。

#ABC362 D - Shortest Path 3
from heapq import heappush, heappop
def dijkstra(G, s):
    INF = 10**18
    dist = [INF] * len(G)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, v = heappop(pq)
        if d > dist[v]:
            continue
        for u, weight in G[v]:
            nd = d + weight
            if dist[u] > nd:
                dist[u] = nd
                heappush(pq, (nd, u))
    return dist
N, M = map(int, input().split())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    u, v, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, b+A[v]]) 
    G[v].append([u, b+A[u]])
d = dijkstra(G,0)
ans = []
for i in range(1, N):
    ans.append(d[i]+A[0])
print(*ans)