ABC309復習

デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309） - AtCoder

■結果

• ABC3完。3完なのに茶パフォ(620)と比較的良かったので、Dは少し難しかったのかも。
• Dは復習に良さそうだったのでじっくり復習して再提出。（グラフの隣接リストを復習し、BFS幅優先探索の基本を学んだ。）

■Ａ問題（Nine）

隣接をb-a==1、行またぎがない事をa !=3とa !=6で判定。
汎用性は薄いがルールは間違ってないし、5分で解けたからヨシ！

a,b = map(int, input().split())

if b-a == 1 and a != 3 and a !=6:
    print('Yes')
    exit()
print('No')

■Ｂ問題（Rotate）

１行目、最終行、それ以外の行で処理を場合分けした。（リストでなく文字列で扱う事、スライス等の文字列操作でずらし操作などを表現するのは自分は良く使う手。）
見通し持ってやったわけではないけど、整理しきったからヨシ！

n = int(input())
m=[]

for ii in range(n):
    a = input()
    m.append(a)

for ii in range(n):
    if ii==0:
        print (m[ii+1][0],end='')
        print (m[ii][:n-1])
    elif ii== n-1:
        print (m[ii][1:n],end='')
        print (m[ii-1][n-1])
    else:
        print (m[jj][0],end='')
        print (m[ii][1:n-1],end='')
        print (m[ii-1][n-1])

■Ｃ問題（Medicine）

日数が経つほど飲む薬が減る。累積和（減少方向）的な考え方でいけそう。
であれば、なにはともあれ、日数順にソートする実装が必要。部活のOさんに習ったm_list.sort(key=lambda x: x[0])を使う。（便利）
その日のむ薬の量を、初日のTotalから減算していくループを作って判定すればOK。（読み込み時にtotalを計算する小技も追加。）
提出してみると、飲む薬が初日からk以下で良いケースでWAが出たので、初日特化の判定を追加した。

n,k = map(int, input().split())
total = 0
m_list = []

for ii in range(n):
    a,b = map(int, input().split())
    total = total + b
    m_list.append([a,b])

if total <= k:
    print(1)
    exit()

m_list.sort(key=lambda x: x[0])

num = total
for ii in range(n):
    num = num - m_list[ii][1]
    if num <= k:
        print(m_list[ii][0]+1)
        exit()

■Ｄ問題（Add One Edge）

１）まずデータを隣接リストに取り込む。（隣接リスト - Wikipedia）

　何故隣接リストが良いのか、隣接リストはどういう構造か、軽くグラフの演習を思い出す。
　実装上はグラフのノード番号をゼロから始めた(0-indexed)。習慣上グラフのノードは１開始で出題される模様。ぐぐると1開始のまま扱うコードもそれなりに見られるしデバッグはそちらがし易そう。0-indexedだとコードが統一的な記述で処理でき楽そう（リストの0番目の特別扱いが不要なのは楽な印象。）

２）次に始点からの最大距離を求める

　グラフの距離を求めるアルゴリズムだと、例えばワーシャルフロイド法が有り、任意の２ノード間の距離が求まる（全点対最短経路問題）。しかし本問題では始点以外との点間距離は不要。ワーシャルフロイド法は計算量がO($n^3$)必要でTLEすると思われるのでこの作戦は避けよう。
　特定の点（スタート）から全ての点への距離を求める問題と考えよう。それなら幅優先探索が良いと思われる。
　考え方としてはこんな感じ。【幅優先探索】木構造（グラフ）における頂点間距離を求める【Python】| くまと梨 (kunassy.com)　これはTreeの説明だが、幅優先探索ではvisitedを記録して次に行く層を管理するので、ループがあっても特に気にしないで良さそう。

３）上記の１，２を実装する。

出来るだけ基本に忠実にbfs実装する。

from collections import deque

n1,n2,m = map(int, input().split())

g1 = [[] for _ in range(n1)]
g2 = [[] for _ in range(n2)]

for _ in range(m):
	a, b = map(int, input().split())
	if a <= n1:
		g1[a-1].append(b-1)
		g1[b-1].append(a-1)
	else:
		g2[a-1-n1].append(b-1-n1)
		g2[b-1-n1].append(a-1-n1)
#print(g1,g2)

def bfs(graph, start):
	distances = [-1] * len(graph)
	distances[start] = 0
	queue = deque([start])
	while queue:
		node = queue.popleft()
		for neighbor in graph[node]:
			if distances[neighbor] == -1:
				distances[neighbor] = distances[node] + 1
				queue.append(neighbor)
	return distances

d1 = bfs(g1,0)
d2 = bfs(g2,n2-1)
#print(d1, max(d1), d2, max(d2))

print(max(d1)+max(d2)+1)

本コードでAC