A Canadian Contest
教授と話していたので1時間遅れで参戦。
チームメイトと合流するのも今更な気がしたし、むしろここから逆転して勝ったら格好良いのでソロでやってみました。
Problem A: Social Constraints
- コイツは臭ぇ！DPの臭いがプンプンするゼっーーーッ！！！
- 余裕で全探索でした。Accepted.
Problem B: Credit Check
- 書くだけ。Accepted.
- なんか最近英語力が落ちてきた気がする。
Problem C: Parallel Carry Adder
- 書くだけ。しょーもないバグを埋め込んだけどAccepted.
- チームメイトはDを解いてたけど、ACが少なかったのとInputが厄介そうに見えたので、普通にACの多い方に行ってみる。
Problem F: Heavy Cycle Edges
- 与えられたグラフの任意の閉路の中で最も重い辺を全列挙せよ。
- 「グラフが閉路を持つ => その閉路の中で最も重い辺を含まないMSTが存在する」はず。
- 単にMSTに含まれない辺を全部出せばいいのでは。
- ・・・いや、逆を証明しないといけないよね。できるのかな。
- まぁ、みんな解いてるんだしどうせ成り立つんでしょ。WA食らったらその時考えよう。
- Accepted.
Problem J: Installing Diagnostic Software
- 重み付き最小頂点被覆問題。ただし、ノードiの重みは2^i。
- 重みの大きい頂点から順に、その頂点を使わずに被覆できるなら使わない、そうでなければ使う、とGreedyしてみます。
- Accepted.
Problem G: Rigging Elections
- n人の立候補者とm人の投票者がいる。各投票者の、立候補者の好みの順番が与えられる。立候補者から2人選んで決選投票をさせて負けた方を落選、ということを繰り返して、最後に残った人が当選。対戦カードを自由に組む権利が与えられたとき、特定の立候補者を当選させられるか。
- 直接勝てる相手はそのまま倒す。勝てない相手は勝てる相手に倒してもらう。でいいはずだ。
- WA.うむむ。
- あ、勝てない相手同士潰し合わせるパターンもあるのか。
- ならグラフに落として勝てる相手に向けて辺を張って、勝たせたい人から他の全員に到達できれば良さそう。
- BFSした。Accepted.
- Standing見てみた。
- チームメイトに追いついてきた。id:iakasTのチームはもはや逆転した。
- と思ったらLayCurseさんがものすごい勢いで追い上げてきてた。
Problem D: Slitherlink
Problem H: Poor Trade Advisor
- 与えられたグラフの辺の部分集合で、空でなく連結なもので、重みの平均値が最大のものを挙げよ。複数あれば、その辺集合がカバーする頂点が最も多い物を挙げよ。
- どう見ても重み最大の辺しかいらないように見える。あとはDisjointSetで適当に。
- WA.問題の解釈ミスかな。DよりACが少ないんだから、こんな簡単なはずがないんだよね。
- でも何度読んでも解釈は合ってるように見える。
- 負の辺もあるっぽい！・・・けどあっても正しく動くはずだよね。
- ・・・むむむ。分からん。
