Cまで三完。Dが解けなかったのは、Cで苦戦して集中力が落ちていたせいかも。
D. Dogeforces
ちょっと分かりにくいけれど、難しい問題ではなかった。
小さい給料の人から順に木を作っていく。（与えられた表をx:給料、i,j:人として(x, i, j)のリストとみて、xでソートする）
その際、最下層の人それぞれについて、「現在の木に関して、自分の一番上の上司は誰か」が分かるようにしておく。（Union-hindの要領で、再帰を使って書ける）
すると、新たな給料xと人i, jを見る際、「iに関する一番上の上司もしくはjに関する一番上の上司」の給料がxであれば、新しいノードを作らないようにすれば良い。（そうでなければ、新しいノードを作り、その人を「i, jの一番上の上司」の上司にする）
うーん、本番中は、（clarが来てたけど）解の存在とかが気になって思考が疎かになっていた気がする。特に発想もいらないし、できなきゃいけない問題でしたね。
E. A-Z Graph
解説AC。
解説を読んだらギャグだった……。
・頂点u, vの間に双方向のpathがあればkが奇数のときは条件を満たす
・さらに、そのラベルが一致していれば、kが偶数のときも条件を満たす
となる。どちらも、u, vを行ったり来たりするpathを考えれば良い。
ギャグだけど、最も単純なパスを考えれば答えに辿り着ける、という意味では教育的かも？
0 件のコメント:
コメントを投稿