Bまで二完。Cの考察が全然間違っていた……。
No.1605 Matrix Shape
解説AC。
自分の考察はおかしかったけど、「有向グラフが与えられる。このグラフのオイラー路(全ての辺をちょうど 回ずつ通るパス)の始点と終点の組み合わせとして考えられるものは何通りあるか？」（公式解説より）という問題になるところは良いと思う。
（なお、私は「終点と終点の前の頂点」の組を考えていた。行列の積をちゃんと考えましょう）
その後の処理も勉強になった。
オイラー路が存在するグラフは、連結で、かつ、次のいずれかの条件を満たす
・全ての頂点の相対入次数が 0
・相対入次数が -1, 1である頂点が1つずつ存在し、他の頂点の相対入次数が全て0
（解説より）
無向グラフのオイラー路判定が、全ての頂点の次数が偶数か、または奇数の頂点が二個、となることは知っていたけど、有向グラフでは相対入次数を考えれば良いことには気付けなかった。
そして、後者の場合、始点・終点は一意に定まる。まあ、次数を見ればそれはそうですね。
しかし、なぜか私は、始点が一意に決まっても、終点が一通りにならないグラフがあると勘違いしていた。
こう書いて見ると、普段はしないような勘違いをしていた気がする。頭が働いてなかったか。
No.1606 Stuffed Animals Keeper
部分和問題と似た問題になることは分かったが、その後のDPでやや苦戦。
二乗が通る制約なのでそういうDPをすれば良い、と気付けば解けた。
No.1607 Kth Maximum Card
これは自力で解けた。
ただ、01BFSと思って書いたものがそうなっていなかったためWAを出してしまった。
01BFSの復習になりました。
0 件のコメント:
コメントを投稿