ぼうメモ帳

2005-08-02

続き

| 続き - ぼうメモ帳 を含むブックマーク

会社のお昼休みに問題DとEを考えた.

問題Dは,やっぱりダイクストラでいく.昨日は,チケットの使用順序を固定しても,チケットの使用状況が異なるから,単純な距離比較は出来ないってところで終わった.だったら,使用状況別に距離比較をすれば良いんじゃないか.

すなわち,ダイクストラだと各ノードはその時点での最短距離を持っているんだけど,最短距離をチケット使用状況別に分けて比較すればよい.チケット使用状況は,使った・使ってないの2の8乗=256種しか存在しないから,ノードに256種類の距離の値を持たせて置けばよい.

で,ダイクストラアルゴリズムを改変して,あるノードの距離の値をチェックするときに,使ってないチケットを使うとどうなるかってのを計算して,256種の距離の値を更新していけば良いんじゃないだろうか.

ついでに,この方法だとチケットの使用順序を固定する必要もなくなるから,1回の探索で求まることになる.

う〜ん,出来そうな気がしてきた.

問題Eは,シミュレーションは止め.解析的に解く(解けるかも).

まず,ロボットAとロボットBが動く軌跡において,通信を行うことが出来るかどうか,出来るならばその時刻の区間は何時から何時までかを調べる.どうやって調べるかというと,各時刻区間のロボットの座標(x,y)は,時刻tを媒介変数とした数式によって表すことが出来る.で,(x-x')^2 + (y-y')^2 < R^2の式に代入して,tに関する2次不等式を作る.この不等式が,数式が成立するtの区間において2次不等式が成り立つtの区間を求める.で,これを時刻0から最終時刻まで全ての区間において調べる.すると,ロボットAとロボットBが通信を行える時刻の区間の集合を求めることが出来る.

それが求まったら,各ロボットが最も早く情報を仕入れる時刻を,その区間を頼りに求めていけば,最終的にどのロボット情報を仕入れることが出来るかを調べられる.

問題DとEについては,これでどうだろう.なんとなく解けそうな気がしてきたので,今夜にでも酒のつまみに実装してみる.

追記

問題D,この方法だとダイクストラじゃダメだったねorz

ノードチケット使用方法による距離の値が収束するまで近隣のノードと値を計算していかないといけないorz

ほとんど全探査やんけ.

結論.どうせ全探査やるんだったら,やっぱり一番得意するバックトラックに切り替えます.

追記2

う〜ん,バックトラックの全探査にしたらすぐにプログラムが書けた.しかも動いたorz

4年前の経験が活かされてない罠.余計なこと(カッコイイこと)は考えない.とにかく,動くものを作る.すっかり忘れてたよ.

で,実装したアルゴリズムだけど,こんな感じ.ちなみに,入出力は省いているから.

public void search( int current, int usage, int[] weights, double distances, int tickets ){
    for( int i=0; i<weights.length; i++ ){
        if( i == current ) continue;
        if( weights[current][i] != Integer.MAX_VALUE ){
            for( int k=0; k<tickets.length; k++ ){
                if( (usage & (1<<k)) == 0 ){
                    int nu = usage | (1<<k);
                    double nd = distances[current][usage] + ((double)weights[current][i])/tickets[k];
                    if( distances[i][nu] > nd ){
                        distances[i][nu] = nd;
                        search( i, nu, weights, distances, tickets );
                    }
                }
            }
        }
    }
}

簡単に説明すると,引数はそれぞれ,現在位置,使用したチケットフラグ,各ノード間の距離,各ノードまでのチケット使用状況における最短距離,チケットの内容.

全ての都市iに対して繰り返す.
 もし,iが現在位置ならばスルー.
 もし現在位置からiまで接続されているならば,
  全てのチケットkについて繰り返す.
   kが使用済みでなければ,
    kを使用済みとしたときのチケットの使用状況をnuとする.
    kを使用してiへ移動したときのスタート地点からの距離をndとする.
    もし,ndがkを使う前よりも小さければ,
     iへの最短距離をndとする.
     iを現在位置,チケットの使用状況をnuとして再帰的に繰り返す.

なお,distancesが再帰中にがんがん変更されるのは仕様です.

2005-08-01

久しぶりに考えてみる

| 久しぶりに考えてみる - ぼうメモ帳 を含むブックマーク

今年のWEB予選がいつの間にか終わってたみたいですね.私が参加していた時期は,10月初めとかだったから,すっかりチェックしてなかったよ.

で,問題を読んでみた.

今年の問題は難易度の壁が激しいなあってのが第一印象.問題A,B,Cに関しては,15分コース.なので,コメントなし.

問題D,E,Fがちとムズイかも.てか,現役退いて,ヌルいプログラミングしかしていない俺にはキツイ.

問題Dは,バックトラックで解くのが一番簡単なんだけど,最大30P8*8!(でいいのか?)の計算をしないといけないから,バックトラックだと計算時間的に解けない.ようするに,答えが出ない.で,この手の問題は,ダイクストラアルゴリズムを使うことを考えるんだけど,チケットの使用方法によって距離が動的に変化するので,単純にダイクストラを使えないのがつらい.

まず,仮定を立てる.ルートが決定されている場合,距離が長い区間に高価なチケットを使ったほうが良いので,ルートが決定されれば,所要時間は自動的に求まる.でも,そのルートを求めるのがこの問題なわけで...これを使っても,さっきの式が30P8になるだけだから...

てことで,逆を考える.チケットの使用順序を決定した上で,ダイクストラをかける.いやまて,使用順序を決定しても,ダイクストラは無理じゃないか? あるノードに到達した時点での残りチケットが違うなら,どちらを優先するか決定できない以上,ダイクストラを使えないんじゃないか?

となると,幅優先探索か.ルート到達時点で,各チケット使用状況とそれまでの時間を保存しておき...って,これだと,バックトラックとほとんど変わりがないような...

一番理想的な状況は,チケットの値の関係と,ルートの値の関係が近似することなんだよなあ.例えば,チケットが(1,5,25)とあったとき,ルート(10,10,10)よりもルート(1,5,25)の方が良いってこと.

う〜んどうしたらいいんでしょう.頭がわけ分からんことになってきた.

問題Eは,問題の制約の意味が良く分からん.イベントシミュレータよろしくで解くのが一番なのか? ステップシミュレータだと,計算時間が足りなさそう.イベントシミュレータで解くにしても,なんか,数式を弄る必要がありそう.う〜ん,今の俺の頭には無理.

問題Fは,あらかじめ幅優先探索で,各汚れたタイル間の距離を求めておく.そして,その距離を重みとして,完全グラフを構築する.で,後は巡回セールスマン問題ということで,面倒なのでバックトラック仕掛ける.10!で求まる.10!ならぎりぎり計算が終わりそう.

とりあえず,問題DEFについては,アルコールが抜けてから考えるか.

2004-07-31 眠い

愛媛大会

| 愛媛大会 - ぼうメモ帳 を含むブックマーク

http://www.ehime-u.ac.jp/ICPC/problems/domestic/d2004/

テスト入力に対する出力例が公開されていました.ということで,早速テスト...うぎゃ,問題Dをミスっているという罠.2点で1つも円が作れないときに間違えているということが分かったので,バグを修正して完了.

274015