ABC362振り返り

前回の振り返り

今日はABC開催日だったので参加結果を振り返る

今回はなんとA,B,D(!)の3完だった
Cがなんとかなれば2回目の4完達成だったけど…まあしょうがない

A

それぞれの値をdictに入れて
嫌いな色をkeyを削除してmin

ソースコード

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)



def main():
    R, G,B = rLI()
    dic = {
        "Red":R,
        "Green":G,
        "Blue":B
    }
    S = rS()
    del dic[S]
    print(min(dic.values()))
if __name__ == '__main__':
    main()

B

だから座標系の問題ヤメテ…

今回はratedなのでブッチせず頑張って三平方の定理で攻略
1度WAしてしまったのがdistで使っていたmath.sqrtを除外したらACできた

ソースコード

main.py

import sys
import math
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def dist2(p1, p2):
    return ((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)

def main():
    A = rLI()
    B = rLI()
    C = rLI()
    
    ab = dist2(A,B)
    bc = dist2(B,C)
    ca = dist2(C,A)
    
    if (
        ab == bc + ca
        or bc == ca + ab
        or ca == ab + bc
    ):
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

C

DP使おうとしたけどよくわからなくて撃沈。(ここで1時間沼って別問題)

解説によると貪欲法で良かったみたい。

D

グラフはできません…とスルーしてたけど
Cで沼っていたのでもう一度みたらダイクストラ法すればよくねってなって検索して出てきた以下のプログラム
https://note.com/strictlyes/n/na40717351795
を改造してあとは各ノードの重みの足すタイミングを適当に計算に加えたらACできた

ソースコード

main.py

import heapq
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def dijkstra(graph):
    distances = {node: float('infinity') for node in graph}
    distances[1] = 0
    queue = [(0, 1)]
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        

        if distances[current_node] < current_distance:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
                
    return distances

def main():
    N, M = rLI()
    A = {i:a for i,a in enumerate(rLI(),start=1)}
    graph = {i:{} for i in range(1,N+1)}
    for i in range(M):
        U, V, B = rLI()
        graph[U][V] = B+A[V]
        graph[V][U] = B+A[U]
    dists = dijkstra(graph)
    ans = [dists[i]+A[1] for i in range(2,N+1)]
    print(*ans)
if __name__ == '__main__':
    main()

E

制約的に3重ループできるなら各値の差分だしてDPできそう。
と思ったけど残り15分でどうやって作るのってなって流石にブッチ

また今度解き直します。

F

Dのグラフ問題でギリギリなのにもっと難しいのはちょっと…

G

順位表みたらこっちのほうが解いてる人おおくね？

まとめ

今回はCが解けなかったがDが解けたという回だった。
C問題に沼ってしまったが、一旦飛ばしてDを解く判断ができたのは良かったが、1時間経過するまで悩む必要はあったのかは課題。

D問題のキーとなったダイクストラ法は過去に実装したことがなく、高専生の頃に習った薄い記憶を引き出した結果ギリギリ解いたので、ぶっつけ本番のコーディングになってしまった。今回はうまくいったが、そうともいかない場合もあるので、
知っているアルゴリズムは何かしらの問題を探して一度ぐらいは実装の練習しとくべきだと思った。

とはいえ、過去に学んだ知識はいつでも引き出せるよう整理したほうが良いのは間違いない。