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] が奇数個

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

泉のプログラム †

1003.cpp

1004 †

問題原文

問題 †

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

なお，2 点間の辺の数は 1 つとは限らない．

解法 †

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

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

泉のプログラム †

1004.cpp