9/11 PKU
1631 Bridging signals
左のP点と右のP点を結ぶケーブルがスパゲッティしてる。互いに交わらないようにできるだけたくさん選べ、という問題。
最初「DP安定ｗｗｗ」って思ったらP<40000って書いてあって無理だった。でもO(nlogn)の最長増加部分列を使えば一瞬
3211 Washing Clothes
リア充が服を洗おうとしている。本人か彼女かのどちらかがそれぞれの服を洗う。同時に洗ってもいいけど、同じ色の服は連続して洗わなきゃいけない。最短何分かかるか求めよ、という問題。
3259 Wormholes
農場にいくつかの一方通行の道とワームホールがある。ワームホールを使うと時間を遡れる。ある点から始めて同じ点に、始めた時刻よりも速い時間に戻ってくる方法が存在するか？という問題。
Bellman-Fordやるだけ。昔のWAの訳…初期化忘れ
1325 Machine Schedule
２種類の機械があって、それにいくつかのタスクをやらせたい。機械は何種類かのモードを持っている。各タスクは両方の機械において、あるモードで実行できる。最初のモードはどちらも0である。モードを変更するには再起動しないといけない。再起動の回数は最小何回必要か求めよ、という問題。
「Asteroids」とかとほとんど何も変わらない。モード0は再起動なしで実行できることに注意して最大マッチングやるだけ
3080 Blue Jeans
長さ60のDNA配列がいくつかある。最長の共通部分文字列を求めよ、という問題。
最初のDNA配列に対して始点の各位置からの文字列を検索文字列にして、他のDNA配列に対して文字列検索するだけ。KMPを使って解いたけど多分ナイーブな方法でも余裕で通る。
1789 Truck History
いくつかの長さ7の文字列があって、どうやらこの文字列たちにはそれぞれ起源があるらしい（すべての起源となる文字列を除く）。文字列たちの系図を作ったときに、「すべての文字列に対するその文字列とその起源文字列の距離」の総和を最小にするとき、これを求めよ、という問題。文字列の距離は、2つの文字列が同じ位置において異なる文字を持つような位置の数、として定義される。
最初盛大に問題文読み間違えていて（ある文字列がすべての文字列の直接的起源になると考えていた）WA。クラスカルやるだけ。もしかしたら辺の数が多いのでバケットソートしないとTLEするかも
2240 Arbitrage
為替レート一覧が与えられるので、ある通貨を両替の末に同じ通貨に戻して金額を増やせるか判定せよ、という問題。
Bellman-Fordやるだけ
3461 Oulipo
長いこと言ってるけど要約すると「文字列Tの中で文字列Wが何回現れるか」
言うまでもなくKMPやるだけ
1693 Counting Rectangles
X軸かY軸に平行な線分が与えられるので、長方形が何通りできるか求める問題。
X軸に平行な直線を2本選んで、それを使う長方形の数を数えるのは、それらと交わるようなY軸に平行な直線を数えればよくO(N)でできる。合計でO(N^3)。N<=100なので余裕。
3275 Ranking the Cows
牛がN頭かいて、何らかの規則で順序付けようとしている。FJはM組の牛に対して2頭の間の順序がどうなるか調べた。順序を完全に定めるためには最低何回順序を調べる必要があるか。
N<=1000, M<=10000だから、O(NM)で2頭の間の順序が定まるところは全部決定できる。順序の定まらない組の数を返せば終了。というのも、どんな調べ方に対しても、それを妨害するような順序を作れるから。
