12/31 PKU

1904 King's Quest

王様にはN人の息子がいる(1<=N<=2000)。N人の少女もいる。それぞれの息子がどの少女が好きかのリストがある。それぞれの息子は、好きな少女のうち誰か１人と結婚しなければならない。魔法使いは、二部マッチング問題を頑張って解いて結婚の組み合わせのリストを作った。でも王様は、それぞれの息子が結婚することができるすべての少女をリストアップしろとかいう無理難題を言い出した。魔法使いのために、これを解いて！

息子iをS(i)、少女iをG(i)として、息子iが少女jを好きなときS(i)->G(j)のリンクを、リストに息子iと少女jの関係が書かれているときG(j)->S(i)のリンクを張った有向グラフを作り、強連結成分分解。各息子について、「自分が好きでかつ同じ強連結成分に含まれる少女」をリストアップする。O(N+sum(Ki))。
証明は面倒なので略。

1733 Parity game

あなたと友人が変なゲームをしている。友人が0と1からなる数列を書きだして、あなたがその数列の第i項から第j項までの和の偶奇を尋ねるというもの。あなたはたくさん質問できる。もしかすると友人は嘘を答えるかもしれないので、その嘘を見抜きたい。何個目の質問までだったら、今までの答えに合致する数列を作れる？

数列をa[i]として、第1項から第i項までの和をs[i]として定める。s[0]=0とする。a[i]からa[j]までの和というのはs[j]-s[i-1]として表せるので、i-1とjだけを集めて、座標圧縮。その後、s[i-1]とs[j]の差の偶奇をUnion Findを使って管理して、矛盾が出るまでやる。