/
最近
.rdf
追記
編集
設定
本棚
翌日へ
前日へ
脳
l
o
g
[
2
0
2
3
0
1
2
4
]
2
0
2
3
年
0
1
月
2
4
日
(
火
)
[
A
t
C
o
d
e
r
]
精進
。
A
B
C
2
8
6
-
G
「
U
n
i
q
u
e
W
a
l
k
」
(
黄
d
i
f
f
)
。
おめでたいことがあ
ったらしいで
す
。
「
b
k
_
c
o
c
o
a
さんのウルシス
テ
ムズプログラミングコンテ
ス
ト
2
0
2
3
(
A
t
C
o
d
e
r
B
e
g
i
n
n
e
r
C
o
n
t
e
s
t
2
8
6
)
での成
績:
2
4
8
位 パフ
ォ
ーマ
ン
ス:
2
1
1
1
相当 レ
ー
テ
ィ
ン
グ:
1
1
4
0
→
1
2
8
3
(
+
1
4
3
)
:
)
H
i
g
h
e
s
t
を更新しました!
#
A
t
C
o
d
e
r
#
ウルシス
テ
ムズプログラミングコンテ
ス
ト
2
0
2
3
(
A
B
C
2
8
6
)
h
t
t
p
s
:
/
/
t
.
c
o
/
0
4
3
K
X
p
C
j
A
X
」
。
A
-
E
G
の6完らしい
。
G
問題の
A
C
抜きで
も
「
終了
3
0
秒前にようや
っと5完を確保した
」
自分では勝負にならない
。
F
も
G
も問題を読む時間さえ作れなか
った時点で負けが確定している
。
素直にすごい
。
F
がダメでもあわよくば
G
を狙うという姿勢がなければ望めない結果ですよ
。
■
提出
#
3
8
2
9
0
9
8
8
(
A
C
/
4
5
6
B
y
t
e
/
3
7
4
m
s
)
。
必ず1回だけ通らなければいけない辺がある
。
N
o
になる条件は何
か
。
最小の例はたぶん4頂点3辺の星型のグラフですべての辺を一度だけ通らなければいけないもの
。
条件付きの辺を一旦とりわけてその他の辺が作るグラフとの関係を考える
。
1回だけの辺が結ぶ2頂点が同じ連結成分に属するなら代替経路があるということで
、
その辺はあ
ってもなくてもいい存在であり1回だけ通ることも自由にできる
(
通
った後で元の頂点に戻
ってくることで通
った結果をキ
ャンセルできるので
)
。
異なる連結成分を結ぶならその辺は橋であり代替経路が存在しない
。
ただし代替となる橋が存在する可能性はある
。
ひと筆書きできるかどうかは頂点の次数の偶奇を見ればわかるというのは有名な話
>
「
ケ
ーニヒスベルクの七つの橋問題
」
。
解けると信じて臨んだ結果解けました
。
負けない
っ
。
翌日へ
前日へ