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]

  • izumi_F0.cpp(もとのやつ)
  • izumi_F1.cpp(修正版)
  • izumi_F2.cpp(再修正版)

先にあげたプログラムで正解の模様。順位は修正されました。 (三廻部; Jun 5, 2004)


ファイルを添付する

filehorizon_F.cpp 590件 [詳細] fileizumi_F2.cpp 583件 [詳細] fileizumi_F1.cpp 577件 [詳細] fileizumi_F0.cpp 574件 [詳細] filemikurube_F.c 582件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filehorizon_F.cpp 590件 [詳細] fileizumi_F2.cpp 583件 [詳細] fileizumi_F1.cpp 577件 [詳細] fileizumi_F0.cpp 574件 [詳細] filemikurube_F.c 582件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (3243d)