やっていくVulkan入門を読んでくれている人をTwitterで観測して泣くほど嬉しい気分になった。

どこの方が作られたのかわからないけど「やっていくVulkan入門」最高すぎる….Vulkanチュートリアルとかわけわからない単語の羅列だけど、このサイトでは丁寧に教えてもらえているのでとてもありがたい…..https://t.co/mYW03CyPUw

— nop (@NOP_LAB) December 15, 2022

---

今日解いた競プロの問題。

ABC239-F: グラフに辺を張って各頂点を指定の次数にした全域木にしろという問題なので、丁寧に実装すれば解ける。3回もWAとREを出してしまったが。

• 辺を張ることはできるが消すことは許されていないので、既に決まっている辺の次数が目標の次数を超えていたらアウト。
• 目標の次数Diの総和がN-1でないなら木にはならないのでアウト。
• 既に決まっている辺の中にサイクルがある場合はどうあがいても木にはならないのでアウト。UnionFindなどで検出できる。

これらをまず最初に判定すればあとは木の部品が散らばっている感じになるので、順に組み合わせていくだけになる。各部品(連結成分)について、追加で張る必要のある辺の数が求まるので、その数が多いものから順に採用して繋げていく。少ないものから採用してしまうと、例えば「1本追加するべき部品が2個、2本追加するべき部品が1個」といった状況の時に、1本の部品2つを繋げて2本の部品を余らせてしまうといったことが考えられる。

腕の多い部品から採用すれば問題ないという厳密な証明はしていないが、まあ通ったのでヨシ！