はじめに
初投稿になるが、コンテスト中に今までできなかったことができたことからその記念(?)も兼ねて投稿する。
A - 1-2-4 Test
配点が1,2,4点とあるので2進数で考える。
少なくとも一方が解けた問題は解け、2人とも解けなかった問題は解けないとあるので論理和をとればよい
a.py
A,B = map(int,input().split())
print(A|B)
B - Hammer
XとYの位置関係から先に考えて、経路に壁がある場合にZが壁より原点寄りにあるか考える。
ゴールに到達可能なのは以下のパターンである。
- X,Yが異符号 (1)
- X,Yが同符号
- XがYより壁寄り (2)
- ZがYより壁寄り (3)
(3)に関しては、Xへの最短経路にZがない場合(X,YとZが異符号)の場合はZを経由する必要があることに注意する。
b.py
import sys
X,Y,Z = map(int,input().split())
if X*Y < 0:
print(abs(X))
sys.exit()
if X * Y > 0 and abs(X)<abs(Y):
print(abs(X))
sys.exit()
if X < 0 and Y < 0 and Y < Z:
if Z > 0:
print(abs(2*Z-X))
sys.exit()
else:
print(abs(X))
sys.exit()
if X > 0 and Y >0 and Y > Z:
if Z > 0:
print(abs(X))
sys.exit()
else:
print(abs(2*Z-X))
sys.exit()
print(-1)
(3)は(1),(2)のように絶対値を使ってスマートに書きたかったがいい方法が思いつかなかったので保留。
sys.exit()を至る所につけるのがなんとも言えぬ、、、
C - Simple path
公式解説では深さ優先探索で行っていたが、本番中は幅優先探索で解いた。
今回の問題で大変なことは、スタートからの最小コストを格納した変数を使って当該の目的地への最短パスを求めることである。(これが初で戸惑った)
手順は以下のとおりである。
-
defaultdictを使って木を管理 - BFSでスタートからの最小コストを求める
-
defaultdictを使ってkeyをコスト、valueをそのコストでいけるノードとする変数を管理 - ゴールから逆算してスタートまでの経路を記録
- 4の配列を逆で表示
c.py
from collections import defaultdict, deque
tree = defaultdict(list)
N,X,Y = map(int,input().split())
# 1
for i in range(N-1):
u,v = map(int,input().split())
tree[u].append(v)
tree[v].append(u)
history = [-1]*(N+1)
history[X] = 1
def bfs(T,i):
Q = deque([i])
while Q:
q = Q.popleft()
for c in T[q]:
if history[c] == -1:
history[c] = history[q] + 1
Q.append(c)
# 2
bfs(tree,X)
# 3
root = defaultdict(list)
for i in range(1,len(history)):
root[history[i]].append(i)
# 4
ans = [Y]
now = Y
for i in range(history[Y]-1,0,-1):
for j in root[i]:
if j in tree[now]:
ans.append(j)
now = j
# 5
print(*ans[::-1])
4に関して、ゴールからスタートして、辿ることのできるノードかつコストが辿る前の-1であるものは今回の場合一意に定まるため上記の処理で実装できる。計算量的には問題ないが、もっとスマートな書き方で行先のノードを求める方法がある気がする。
最後に
コンテスト中は速さ重視で使い捨てのようなコードを書いてしまうが、詰まったとき原因に気づくのが遅くなるため決めたルールに従って書くようにしたい。