2004/Contest/国内予選/Problem F

2004/Contest/国内予選

Problem F : Name the Crossing †

↑

問題概要 †

↑

解法 †

まず，各通りを点とする有向グラフを作る．辺については次にしたがう．

交差点 A-B があれば A→B なる重さ 1 の有向辺を結ぶ．
2 つの通り A，B が同水準ならば A→B および B→A なる重さ 0 の有向辺を結ぶ．

ここで 2 つの通り A，B が同水準であることは，次のいずれかを満たすこと~~と同値~~が必要条件．

ある通り C に対して，2 つの交差点 A-C，B-C の両方が存在する．
ある通り C に対して，2 つの交差点 C-A，C-B の両方が存在する．

上の条件を満たす 2 つの通り A，B が，さらに次の 2 つの条件を両方とも満たせば A と B は同水準．

任意の通り C に対して，2 つの交差点 A-C，C-B のいずれかが存在しない．
任意の通り C に対して，2 つの交差点 C-A，B-C のいずれかが存在しない．

あとは単なる経路探索になる．A-B が有効であるかどうかは，A，B の間に経路が存在して，かつその経路における辺の重さの合計値が奇数であることに等しい．

↑

議論・その他 †

アルゴリズムを考える時間などを含めると 1 時間程度．この問題はちょっとしんどい．添付したプログラムは上のアルゴリズムをもとに書いたけど，あまり忠実ではないかも．［泉，2004/07/04］

同じタイミングで解いてやがる。 (笑)

かかった時間も同様に一時間程度。やっていることも泉と同じ。「入力に存在する」か「同水準」かで初期状態のグラフを作って、そこから Floyd-Warshall ですね。 (三廻部; Jul 4, 2004)

...と思ったけれど、入力 2 に対する答えが違う...。

泉の回答では、問題文中の

D-AとB-Dが入力の中にあるような通りDはない． [#p2a97f15]
A-EとE-Bが入力の中にあるような通りEはない． [#z577a8bf] という条件が無視されているような気がするのだけど、これはいいのか?

ちなみに自分のプログラムからその条件を抜くことで、泉の出力データと一致。

さらに自分の (初期の) 出力データは reject された horizon の出力データと一致。ってことは、自分が間違ってるのかなあ。 (三廻部; Jul 4, 2004)

失礼．たぶん俺のミス．たとえば A-C，B-C となる通り C があったとしても，A-D，D-B となる通り D がないとは言えないのか．審判団から「問題 F について事故で正しい判定ができなかったチームがありました」という旨の連絡があったけど，ひょっとして審判団も俺とまったく同じミスをした？（追記：入力 1 に対する解答もあわないからこれはない．［泉，2004/07/04］）

ちなみに，泉は Floyd-Warshall なんて高級な方法は利用していない（だからちょっと遅い）．Dijkstra のアルゴリズムに近いかな？［泉，2004/07/04］

あ，よく考えたらさっきの修正版でもだめだ．再修正版を添付．一応，誤りのあるソースコードも残しておきます．［泉，2004/07/04］