1060

連立方式でとくためには… http://www.ic-net.or.jp/home/takaken/nt/light/light2.html 参照

1003

問題原文

問題

最大 10 億桁の 0,1 のビット列がある(ことになっている).入力として,ある範囲における 1 の個数の偶奇(パリティ)が与えられる(ただし正しいとは限らない).具体的にはこんな感じ.

  1. ビット 1 からビット 2 まで 1 が偶数個.
  2. ビット 3 からビット 4 まで 1 が奇数個.
  3. ビット 5 からビット 6 まで 1 が偶数個.
  4. ビット 1 からビット 6 まで 1 が偶数個.
  5. ビット 7 からビット 10 まで 1 が奇数個.

ここで,上から何番目 Consistent な情報であるかを答える.たとえば上の例では 1. から 3. までは正しい可能性があるが,4. は明らかに嘘なので 3 と出力する.全部の情報が正しい可能性がある場合は与えられた情報の数(上の例では 5)を出力する.

解法

自然言語で記述するとややこしいのでエッセンスだけ.

たとえば上の例であれば

  • 範囲 [1,2] が偶数個
  • 範囲 [3,4] が奇数個
  • 範囲 [5,6] が偶数個

というようなデータ構造を作る.ここでたとえば

  • 範囲 [1,4] が偶数個
  • 範囲 [3,4] が奇数個

というデータが与えられたら

  • 範囲 [1,2] が奇数個
  • 範囲 [3,4] が奇数個

というデータに改変する必要がある.

泉のプログラム

file1003.cpp

1004

問題原文

問題

与えられた無向グラフに対して 3 点以上(全部の点を含む必要はない)からなる閉路のうち距離の和が最小のものを求める.ただし,同じ点を複数回通ってはならない.

なお,2 点間の辺の数は 1 つとは限らない.

解法

2 点間の辺の数は 1 つとは限らないが,同じ点を 2 度以上通ってはならないことから,ある 2 点間については一度しか通過することがない.したがって,距離最小の辺だけとっておけば大丈夫.

ここまでやった後,泉は任意の 2 点 ij について辺 (i,j) を含まないグラフにおける最短経路を Dijkstra 法で探索した.この最短経路に辺 (i,j) を加えたものが i からはじまり最後に j を通るような閉路のうちで最短のものとなる.ただし,(既知の閉路長)<(辺 (i,j) の距離)のときは枝を刈らないと時間切れになる.

泉のプログラム

file1004.cpp


添付ファイル: file1004.cpp 470件 [詳細] file1003.cpp 439件 [詳細]

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