2008 Qual

終わってた。出したものは通っていたっぽい。きっと今なら好き勝手コメントしていいに違いない。別にこれで失格になったりしないだろう。多分。サブミットした時間遅かったし、2問しか解いてないから、1742位でしたよと。全部で6000人ちょっと通過しているっぽい。

A

検索エンジンに対して、エンジン名を検索することはできない、という状況下で、クエリ列が与えられる時、検索エンジンを何回切り替えれば検索列を処理できるか、という問題。

検索エンジン名に該当するクエリが来たら、それ以外のエンジンが受注していたことにして、N番目のヤツが来たら、そいつが受注していたけどスイッチするよ、みたいな感じのgreedy割り当てで起こるスイッチ回数を計算すれば良さそう。

B

二つの駅の間を電車が折り返し運転する。出発時刻と到着時刻が与えられて、折り返しにかかる時間が与えられる。ある駅を出発した電車はもう一方の駅を出発しない限り、元の駅から出発することはできない。このとき、両方の駅から出発する電車の最小数をそれぞれ答えよ、という問題。

要は片方の駅を出た電車をできる限りもう一方の駅から出発するように使い回せ、という問題。問題をややこしくしないようにするために、ある駅を出発しないといけない電車について、もう一方から来たものを流用できる数の最大数を求める、というのを双方の駅についてやる。(流用の連鎖をたくさん取る、みたいにするのでもいいけど、実装が多分面倒。)

これを実現するには、ある駅への到着時刻＋折り返し時間がその駅での出発時刻に間に合うものには枝がある二部グラフを作って、左ノードはある駅へ到着する電車、右ノードはある駅から出発する電車、とやって最大マッチングを取ればいい。最大二部グラフマッチングはいわゆる最大流なので、BFS回して...。ライブラリないや...、なので適当に作成した。

C

なんか幾何っぽいよ、程度に眺めただけ。