マラソン（ヒューリスティック）形式の問題が含まれるコンテストでは、まずその問題から見るようにしています。
その問題にちょっと不備があった、というのが後の出来に多少は影響したかもしれないけど、Cで苦戦しDが解けない、というのは情けなかった。
C - A + B
次数を考えれば良い。
思いつけばシンプルだけど思いつかないと厳しい……というタイプの問題なので仕方ない面はあるけど、次数を考えるのは定石の一つなので、素早く思いつきたかったところ。
D - Animal Show
動物aにアレルギーを持っている人が全員ショーを行ったら、動物aを使ったショーができる。ということは、人を頂点とし、ある動物に対して「アレルギーを持つ人」から「ショーで使う人」に辺を引いて、トポロジカルソートをすれば良い。（ちょっと戸惑ったけど、ここまではコンテスト中に分かった）
ただ、これだと辺の数が大きくなり過ぎる。
なので、グラフを陽にもたず、「各動物について、その動物のアレルギーを持っている人は何人か」「各人について、まだショーに使用できない動物は何種類か」というリストを持っち、それぞれが0になったら適切な処理をして……として解いた。
これ、基本的にはKahnのアルゴリズムをやろうとしています。入次数が0になるところを探す、という処理をしている。
ただ、そういうとことをしようと思っても、色々混乱して正しいコードにするのにはかなり時間がかかってしまった。
公式解説はシンプルですね。
頂点を増やした方が辺が減るのか。なるほど確かに。
E - 老朽化対策
解説AC。
なるほどとは思うものの、そもそも座標の最大値・最小値をあまりチェックしていなかったので思いつけなかった気がする。確かに、$5*10^4$とちょっと小さめなのは気になったけど……。こういうところにも気を配らなきゃいけないのね。
0 件のコメント:
コメントを投稿