JOI本選参加記

JOI予選を４完＋部分点でAランク取れたのでJOI本選に行って来ました。
JOI本選通ってしまったということでそれまでの期間、意識高い顧問からの課題をこなす日々を過ごした。
一応自分でもAOJのVolume 5は全部解こうと目標立ててたのに結局４問ほど残ってしまう意識の低さで当日を迎えてしまった。

• 2/9(土)

集合時間が12時くらいなので9時ぐらいまでゆっくり睡眠をとり、11時半くらいに家を出る。
新幹線では昼食を食べ、同じ学校の@public_sateが横で爆睡してる中蟻本を読みながら意識高いふりをしながら東京へ向かった。

去年の本選では0完太陽が生えたので今年は絶望しないように明治神宮でお祈り。
おみくじには、「糸を解こうとして間違って糸口を見失うと、もつれもつれて、ついには解きほぐす方法を失う」みたいなこと書かれてて絶望。

3時過ぎ頃、プラクティスの会場へ到着。
顧問の知り合いの先生が僕のAOJのID知っててマークされてるらしく怖い
会場では、EPOCHの参加者など知ってる人がいたので去年のような悲しみは背負わずにすんだ。
問題は、やるだけと過去問だったので適当に解いて、乱数を吐く奴書いて負荷をかけて遊んでいた。

夕食は去年より品数が多かったように思う。覚えていない
自己紹介では、去年と同じようにTwitterアカウント晒しが始まってた。
Twitter昨日はじめた人やハラスメンターの方々が怖かった（小並感）
名刺交換タイムは毎回作ってこようと思っていて忘れてしまっているので見学

夜は談話室で他の学校の人と交流。
「実用がメインで競技はおまけです。去年は適当にやったら合宿いけました」などというハラスメントを受けて精神を傷つけられる。
魔理沙のコスプレをした人が、男性だということにかなり後半で気付く。言われなければ気付かない。
実用プログラムの怖い話を聞きながら、23時半までなのに23時頃風呂に向かい、日付が変わってから寝た。

• 2/10(日)

緊張してるせいか5:30→5:45→6:00を起床とn度寝を繰り返す。

朝食は高専の方々と食べた。EPOCHで一発街で盛り上がったように、今回は大浴場で盛り上がった。
笑いすぎて疲れて本選のこと忘れた。

8:30チェックアウトなのに8:30に宿泊棟を出る屑

待合室では、4問目にsegment木が出るそうなので蟻本読む……がわからん
座標圧縮とかLCAのページパラパラ見ながら時間を潰してるといつの間にか時間になってた。

入り口で綾鷹をもらい、競プロには炭酸がいいと何処かで聞いたのでccレモンを買って本線に望む。

1問目　電飾
緊張のあまり謎の解法で解いてバグる。
チグハグになってるとこを前後で3つ足せばいいことに20分ぐらいたってから気付く。

• 100/100

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int a[1111111];
vector<int> v;
int main(void){
  scanf("%d",&n);
  int best = -1;
  int c = 0;
  int tu;
  int f=2;
  for(int i = 0; i < n; i++){
    scanf("%d",a+i);
  }
  for(int i = 0; i < n; i++){
    //printf("a:%d:%d\n",i,a);
    if(f != a[i]){
      f = a[i];
      if(!c) tu = i;
      c++;
    }else{
      v.push_back(c);
      f = 2;
      i--;
      c = 0;
    }
  }
  if(c) v.push_back(c);

  for(int i = 0; i < (int)v.size(); i++){
    //printf("v[%d] = %d\n",i,v[i]);
    int t = v[i];
    if(i) t += v[i-1];
    if(i+1 < (int)v.size()) t += v[i+1];
    best = max(best,t);
  }
  printf("%d\n",best);
}

2問目　IOI 列車で行こう
1問目遅くなったので問題文雑に読み解き始める。
stack使いそうとか思ったけど全然関係なかった。
・いくつか捨てられる事を忘れる。
・最後'I'でなくてはならないのを忘れる。
・一番最初しか捨てられないのを忘れる。
dp書いて気付いて直して気付いて…を繰り返したのでゴリ押し感がパない。
おみくじ通り間違ってると思ったらすぐ解法考えなおすようにしたのでなんとかいけた
40分ぐらいかかった気がする。

• 100/100

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int n,m;
string s,t;
string io = "IO";

int dp[2][2002][2002];
int solve(int f,int a,int b){
  if(dp[f][a][b] >= 0) return dp[f][a][b];
  if(a == n && b == m) return f?0:-444444;

  int res = -1;
  if(a < n && io[f] == s[a]) res = max(res,solve((f+1)%2,a+1,b)+1);
  if(b < m && io[f] == t[b]) res = max(res,solve((f+1)%2,a,b+1)+1);
  /*
  if(a < n) res = max(res,solve(f,a+1,b));
  if(b < m) res = max(res,solve(f,a,b+1));
  */
  if(res == -1) return f?0:-444444;
  return dp[f][a][b] = res;
}

int main(void){
  cin >> n >> m >> s >> t;
  int res = 0;
  memset(dp,-1,sizeof(dp));
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      res = max(res,solve(0,i,j));
    }
  }
  cout << res << endl;
}

3問目　現代的な屋敷
制限見てやばそう
とりあえずスイッチのある場所だけ考えればいいことに気付く。
おもむろにdp書き始める。サンプル微妙にバグって冷える。
12:00ぐらいで閉路であることに今更気付き絶望
ココらへんでccレモンが猛威を振るってきたのでトイレにいく
おみくじさんのおかげでDijkstraだと気付く。
解いてる途中5回ぐらいUbuntu壊れる（ctrl押しっぱなしの状態になる）

「時間超過1 (80)」絶望

辺おおすぎるからなぜかMLEだと思う
Dijkstraを信じすぎていたためTLEは全く疑わない
なぜかpriority_queueをただのqueueに直す
なぜか「時間超過1 (80)」

終わり際にDijkstraがO(ElogV)だったの気づくがもう遅かった。

• 80/100

ソースで時折char型が出てくるのはMLEだと思ってた時の名残

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define F first
#define S second
#define INF (((ll)1<<20)<<20)
using namespace std;
typedef long long ll;
struct P{
  ll x,y;
};
ll n,m,k;
vector<ll> ix[111111];
vector<ll> iy[111111];
P s[222222];
ll d[2][222222];
bool flag;
int main(void){
 scanf("%lld %lld %lld",&m,&n,&k);
  k++;
  for(int i = 1; i < k; i++){
    ll x,y;
    scanf("%lld %lld",&x,&y);
    //if(x == 1 && y == 1) flag = true;
    P p = {x,y};
    s[i] = p;
    ix[x].push_back(i);
    iy[y].push_back(i);
  }
  P p = {1,1};
  s[0] = p;
  ix[1].push_back(0);
  iy[1].push_back(0);
  P q = {m,n};
  s[k] = q;
  ix[m].push_back(k);
  iy[n].push_back(k);

  priority_queue< pair<ll,pair<char,int> >, vector< pair<ll,pair<char,int> > > ,greater< pair<ll,pair<char,int> > > > que;
  //priority_queue< pair<ll,pair<char,int> > > que;
  //queue<pair<ll,pair<char,int> > > que;
  fill(d[0],d[0]+k+1,INF);
  fill(d[1],d[1]+k+1,INF);
  que.push( make_pair(0,make_pair(0,0)) );
  d[0][0] = 0;
  while(!que.empty()){
    ///*
    ll c = que.top().F;
    char f = que.top().S.F;
    int p = que.top().S.S;
    //*/
    /*
    ll c = que.front().F;
    char f = que.front().S.F;
    int p = que.front().S.S;
    */
    //printf("(%lld,%lld)\n",s[p].x,s[p].y);
    que.pop();
    if(d[f][p] < c) continue;
    if(p && d[(f+1)%2][p] > c+1){
      d[(f+1)%2][p] = c+1;
      que.push(make_pair(c+1,make_pair((f+1)%2,p)));
    }
    if(!f){
      for(int i = 0; i < (int)ix[s[p].x].size(); i++){
	ll q = ix[s[p].x][i];
	if(d[f][q] <= d[f][p] + abs(s[p].y-s[q].y)) continue;
	d[f][q] = d[f][p] + abs(s[p].y-s[q].y);
	que.push(make_pair(d[f][q],make_pair(f,q)));
      }
    }else{
      for(int i = 0; i < (int)iy[s[p].y].size(); i++){
	ll q = iy[s[p].y][i];
	if(d[f][q] <= d[f][p] + abs(s[p].x-s[q].x)) continue;
	d[f][q] = d[f][p] + abs(s[p].x-s[q].x);
	que.push(make_pair(d[f][q],make_pair(f,q)));
      }
    }
  }
  ll res = min(d[0][k],d[1][k]);
  if(res >= INF) puts("-1");
  else printf("%lld\n",res);
}

4問目　JOIOIの塔
よく分からん嘘貪欲を書く。サンプル通ったので何故かいけると思う。
制限見てO(n)であるこの解法は絶対違うだろ！と気付く
が解き方分からんので諦め

• 0/100

5問目　バブルソート
この問題蟻本でやった問題だ！！！
と思い何も考えずBIT書く。
書いてる途中にO(n^3logn)でこれダメじゃね？と思う。
別解法思いつかないので提出

• 0/100

結果

• 280/500

部分点全然取れなくて悲しい。
トイレに行きたくなる飲み物は良くない。2回行った
どっかで合宿いくのには3完+部分点と聞いていたので絶望してた

昼食は、競技終わったあとなのにカツカレーで英気を養う。
4問目部分点は前日の夜、他の人に偉そうに「n=15位だったらbitDPだと思えばいいよ（笑）」とか言っていたので恥ずかしくて死にそうだった

解説は、全部わかりやすくてとても良かった（5問目は例外）。
5問目は解説はすごい丁寧でわかりやすいんだろうけど、後半ちょっと何行ってるかわからなかった。激ムズ
3問目満点はなぜ気付かなかったか自分を責める。
4問目は頭良いなと思った

時間が遅れて、電車がやばかったのでろくに挨拶もせず帰ってしまったのがちょっと後悔
なにはともあれ、今年のJOIはとても楽しかったです

2/11に送られてきたメールでAランクだったとわかったので合宿いけるそうです。
皆さんよろしくお願いします！

AOJ0570

Zig-Zag Numbers

■問題
2947や71946などの各桁が増加、減少、増加…およびその逆となってる数字をジグザグ数とする。
A以上B以下のMの倍数であるジグザグ数の個数を求めよ。

■解法
制限が 1 <= A <= B <= 10^500 なので整数型には入らないため文字列として扱う。

A以上B以下はx以下のジグザグ数の個数をf(x)とすると、f(B) - f(A-1)　となる。A-1なのは区間にAを含むためであり、Aの文字列から1引くために多倍長っぽいことをする。

Mの倍数かの判定は、Mで割り切れるかを調べるのだが文字列なので面倒である。
整数同士の割り算の筆算のように、”前の桁の余り*10 + 今の桁 % M = 今の桁の余り”というのをすべての桁に対してやり最後の値が0なら割り切れたと判断できる。

先ほど出てきたf(x)をどうやって作るかは、上位の桁から1つずつ決定していく方法でやります。
x = 256のとき、先頭の桁には0,1,2が成り得ます。しかし、その後の桁については場合によって異なり
x = 0,1　の時はその後の桁についてはどの数値でも採用でき、
x = 2 の時は次の桁では5まで、その次の桁では6までしか使えません。
このように、すでに上限の値以下になることが確定されたかどうか、0～9の数値を自由に選べるかのフラグが必要となります。

また、ジグザグ数になっていなければいけないため、今選んだ桁をk、直前に選んだものをbとすると、
一つ前が増加していたときは、k < b
一つ前が減少していたときは、k > b
にならなくてはなりません。

これらのすべての条件を満たせるように情報を持たせてメモ化再起するには、
dp[k桁目][直前の数字][直前が増加か減少か][自由に選べるか][前の桁での余り]
とし、値をk桁目までの値を決めた時のジグザグ数の数とすることで求められます。

また、五次元配列なので多めに確保しようとするとMLEになってしまうかもしれません。
また10^500は桁数としては501なので配列の数を気をつけましょう。

■ソース

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
//dp[何文字目か][直前の数字][上下][自由に選べるか][余り]
//上:0 下:1
int m;
string s;
char z[555];
int dp[501][10][3][2][500];
int solve(int n,int be,int ud,int ok,int md){
  if(n == (int)s.size()){
    return md?0:1;
  }
  if(dp[n][be][ud][ok][md] >= 0) return dp[n][be][ud][ok][md];

  int ret = 0;
  for(int i = 0; i <= ((ok)?9:(int)(s[n]-'0')); i++){
    if(ud == 0 && be <= i) continue;
    if(ud == 1 && be >= i) continue;
    if(ud == 2 && be != 0 && be == i) continue;
    int u;
    if(ud == 2){
      if(be == 0) u = 2;
      else if(be > i) u = 1;
      else u = 0;
    }else{
      u = (ud+1)%2;
    }
    ret += solve(n+1,i,u,(ok || i != (int)(s[n]-'0'))?1:0,(md*10+i)%m);
  }
  return dp[n][be][ud][ok][md] = ret%10000;
}

int main(void){
  string c,d;
  cin >> c >> d >> m;
  for(int i = (int)c.size()-1; i >= 0; i--){
    if(c[i] == '0'){
      c[i] = '9';
    }else{
      c[i]--;
      break;
    }
  }
  s = c;
  memset(dp,-1,sizeof(dp));
  int a = solve(0,0,2,0,0);
  s = d;
  memset(dp,-1,sizeof(dp));
  int b = solve(0,0,2,0,0);
  cout << (b + 10000 - a)%10000 << endl;
}

AOJ1140

Cleaning Robot

■問題
部屋の盤面が与えられ、スタートからすべての汚れたマスを通るように移動するときの最小距離を求めろ。

■解法
すべてのマスを通ってという巡回セールスマン問題のような問題だがスタートと各汚れとの距離は障害物があるため、先にBFSしてすべての2つの汚れまたは、スタート地点間の距離を求めておく。この時、辿りつけない組み合わせがあった場合は全てにたどり着くことが出来ないということがわかる。
あとは、その情報をもとにbitDPなどやるだけで求めることができる。

■ソース

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int w,h;
int b;
char c[33][33];

struct P{
  int x,y;
  P(int x,int y):x(x),y(y){}
};

vector<P> v;
int used[33][33];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int d[11][11];
int p;

int dp[1<<11][11];
int solve(int bit,int a){
  if(bit == (1<<p)-1) return 0;
  if(dp[bit][a] >= 0) return dp[bit][a];

  int ret = 1 << 28;
  for(int i = 1; i < p; i++){
    if(bit & 1 << i)continue;
    ret = min(ret,solve(bit | 1<<i,i) + d[a][i]);
  }
  return dp[bit][a] = ret;
}

int main(void){
  while(cin >> w >> h && w){
    v.clear();
    memset(c,-1,sizeof(c));
    v.push_back(P(0,0));
    p = 1;
    for(int i = 1; i <= h; i++){
      for(int j = 1; j <= w; j++){
	cin >> c[j][i];
	if(c[j][i] == 'o'){
	  c[j][i] = 0;
	  v[0].x = j;
	  v[0].y = i;
	}else if(c[j][i] == '*'){
	  c[j][i] = p;
	  p++;
	  v.push_back(P(j,i));
	}else if(c[j][i] == 'x'){
	  c[j][i] = -1;
	}
      }
    }

    memset(d,-1,sizeof(d));
    bool f = false;
    for(int i = 0; i < p; i++){
      memset(used,-1,sizeof(used));
      queue<P> que;
      que.push(P(v[i].x,v[i].y));
      used[v[i].x][v[i].y] = 0;
      while(!que.empty()){
	P a = que.front(); que.pop();
	if(c[a.x][a.y] == -1) continue;
	if(c[a.x][a.y] != '.'){
	  d[i][(int)c[a.x][a.y]] = used[a.x][a.y];
	}
	for(int i = 0; i < 4; i++){
	  int nx = a.x + dx[i];
	  int ny = a.y + dy[i];
	  if(used[nx][ny] == -1){
	    que.push(P(nx,ny));
	    used[nx][ny] = used[a.x][a.y] + 1;
	  }
	}
      }

      for(int j = 0; j < p; j++){
	if(d[i][j] == -1){
	  f = true;
	  break;
	}
      }
      if(f) break;
    }
    if(f){
      cout << -1 << endl;
    }else{
      memset(dp,-1,sizeof(dp));
      cout << solve(1,0) << endl;
    }
  }
}

AOJ0548

方向音痴のトナカイ

■問題
教会と家の情報がn*mの盤面で与えられます。
トナカイは上下左右に直進しかできず、一度止まった家の上は通過できなくなります。
教会からスタートし、すべての家に訪れてまた教会に戻ってくるルートは何通りあるか求めよ。

■解法
まずこの問題の一番厄介なところは一度止まった家の上を通過できなくなるというところだが、それはゴールからスタートに向かうと考えると通った家は必ず止まる、同じ家に止まらないという事だけ考えれば良いことになる。
探索に必要な情報はどの家に止まったかと今の座標であり、今の座標は家に番号を振り分けておくと一つですみ、どの家に止まったかをbitで管理すると、dp[どの家に止まったかのbit][今いる家の番号]で答えを求めることができる。

この開放のオーダーを考えると家の数をhとするとO(2^h * h)となり、家の数は最大23であるため、つらそうに見えるが、どの家に止まったかのbitは盤面では実現不可能な状態も多くあり、計算量はもっと少なくなる。

答えとソースのみを送るJOI予選ならこれでいいのだが、オンラインジャッジだとメモリが足りなくてMLEになってしまうためいろいろ工夫しなくてはならない。
オーダーのとこで言ったように実現不可能な状態も配列で確保すると必要になり無駄なので、mapを使ってdpする。
これでも足りないが、訪れた家の数が多くなっていくにつれ、探索する量も減っていくため、探索の多い訪れた家の数が少ない(立っているbitが少ない)時のみメモし、小さい時は毎回探索することによりメモリを減らすことができる。
いくつになったら毎回探索に切り替えるかはメモリの上限と実行時間とか考えながら適当な値にする（これでは13とかにしてる）。

■ソース

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#define F first
#define S second
using namespace std;
int n,m;
int c;
int f[22][22];
typedef pair<int,int> P;
vector<P> v;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool used[33];
map<P,int> dp;
int solve(int bit,int h){
  if(bit == (1<<c)-1){
    if(v[h].F == v[0].F || v[h].S == v[0].S){
      return 1;
    }
    return 0;
  }

  if(dp.find(P(bit,h)) != dp.end()){
    return dp[P(bit,h)];
  }

  int ret = 0;
  for(int i = 0; i < 4; i++){
    int nx = v[h].F + dx[i];
    int ny = v[h].S + dy[i];
    while(0 < nx && nx <= n && 0 < ny && ny <= m){
      if(f[nx][ny] && !used[f[nx][ny]]){
	used[f[nx][ny]] = true;
	ret += solve(bit | (1<<f[nx][ny]),f[nx][ny]);
	used[f[nx][ny]] = false;
	break;
      }
      nx += dx[i];
      ny += dy[i];
    }
  }
  if(__builtin_popcount(bit) < 13) dp[P(bit,h)] = ret;
  return ret;
}

int main(void){
  while(1){
    cin >> n >> m; if(!n) break;
    c = 1;
    v.clear();
    v.push_back(P(0,0));
    memset(f,0,sizeof(f));
    memset(used,false,sizeof(used));
    for(int i = 1; i <= m; i++){
      for(int j = 1; j <= n; j++){
	cin >> f[j][i];
	if(f[j][i] == 2){
	  v[0].F = j;
	  v[0].S = i;
	  f[j][i] = 0;
	}else if(f[j][i] == 1){
	  f[j][i] = c;
	  v.push_back(P(j,i));
	  c++;
	}
      }
    }

    dp.clear();
    cout << solve(1,0) << endl;
  }
}

PKU1990

MooFest

■問題
直線上にいるN匹の牛の聴力と座標が与えられる。
異なる2匹の牛の座標の差の絶対値と聴力の大きい方を掛けたものをすべての組み合わせに対して求めその総和を出力せよ。

■解法
すべての組み合わせを試す際、聴力に対して昇順ソートすることで「i番目の牛の聴力*i番目以前のすべての牛の距離の差の総和」をすべての牛に対してやることで聴力の最大を気にする必要がなくなる。よって牛の距離の差の総和を高速に求める必要がある。

距離の差は自分の座標をX,相手をxiとすると相手が小さい場合はX-xi、大きい場合はxi-Xとなり、
小さい牛の総和は X-x1 + X-x2 + ・・・ + X-xn = X*n - (x1 + x2 + ・・・ + xn)
大きい牛の総和は x1-X + x2-X + ・・・ + xn-X = (x1 + x2 + ・・・ + xn) - X*n
という式によって求めることができる。

その式の括弧の中は、配列の添字を座標と対応させたBITによって求める。
i番目以前というのは使ったものから順番にBITに値を追加していくことで解決できる。

小さい牛の数、大きい牛の数もわからなくてはならないので総和とは別にもう一つBITを作り、牛の数もBITで求める。

int型に収まらないことがあることにも注意する。

■ソース

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <map>
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int n;

long long l[22222],c[22222];
long long sum(long long a[],int i){
  long long s = 0;
  while(i > 0){
    s += a[i];
    i -= i & -i;
  }
  return s;
}

void add(long long a[],int i,int x){
  while(i <= 20000){
    a[i] += x;
    i += i & -i;
  }
}

P m[22222];
int main(void){
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> m[i].F >> m[i].S;
  }
  sort(m,m+n);

  long long res = 0;
  for(int i = 0; i < n; i++){
    long long sl = sum(l,m[i].S);
    long long bl = sum(l,20000);
    long long sc = sum(c,m[i].S);
    res += m[i].F*(m[i].S*sc-sl+bl-sl-m[i].S*(i-sc));
    add(c,m[i].S,1);
    add(l,m[i].S,m[i].S);
  }
  printf("%lld\n",res);
}

AOJ2011

Gather the Maps!

■問題
n人の子孫がそれぞれ宝の地図の断片を１枚ずつ持っています。
n人の日程はわかり、その日が暇な人同士なら誰かにその断片を渡すことができます。
誰かがすべての断片を手にするまでの最小の日数を求めなさい。

■解法
誰かの断片を別の誰かに渡す時、当然だが持っているすべてを渡すほうが良い。
さらに、渡すという処理は自分のものを渡すのではなくそのコピーを渡してやるというふうに処理するとスケジュールがあった場合の渡した場合と渡さなかった場合の両方の状態を調べることができる。
誰がどの断片を持っているかはbitを使って管理して、渡す処理はORを取ればいいためすべてのbitが立つ状態になるまでシミュレーションすればよい。
また、人数はn<=50なのでbitで管理する変数は2^50が入るlong long intで無くてはならない。
プログラム中のシフト演算でもオーバーフローに気をつける。

■ソース

#include <cstdio>
#include <vector>
using namespace std;
int main(void){
  while(1){
    long long int c[55];
    vector<int> d[33];
    int n;
    scanf("%d",&n); if(!n) break;
    for(int i = 0; i < n; i++){
      c[i] = 1LL << i;
      int f;
      scanf("%d",&f);
      for(int j = 0; j < f; j++){
	int a;
	scanf("%d",&a);
	d[a].push_back(i);
      }
    }
    bool f = false;
    for(int i = 1; i <= 30; i++){
      for(int j = 0; j < (int)d[i].size(); j++){
	for(int k = 0; k < (int)d[i].size(); k++){
	  c[d[i][k]] |= c[d[i][j]];
	  if(c[d[i][k]] == (1LL << n) - 1){
	    f = true;
	    printf("%d\n",i);
	    break;
	  }
	}
	if(f) break;
      }
      if(f) break;
    } 
    if(!f) puts("-1");
  }
}

AOJ1138

Traveling by Stagecoach

■問題
m個の街がp本の道路でつながれている。
道路を利用するには券が必要で、移動にかかる時間は距離/券の数字だけの時間が掛かる。
また、券は１枚につき１回しか使えません。
あなたはn枚の券を持っていて街aから街bに行きたい時の最短時間を求めなさい。
またいけない場合は"Impossible"を出力しなさい。

■解法
今どの券を使ったかをbitで管理し、d[使用した県の情報][街の番号]でDPっぽいDijkstraする。

■ソース

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define F first
#define S second
using namespace std;

struct edge{
  int to,cost;
  edge(int to,int cost):to(to),cost(cost){}
};

typedef pair<double,pair<int,int> > P;

int n;
int m,p,a,b;
double t[11];
vector<edge> v[33];
double d[1<<9][33];

int main(void){
  while(1){
    cin >> n >> m >> p >> a >> b; if(!n) break;
    a--;b--;
    for(int i = 0; i < n; i++) cin >> t[i];
    for(int i = 0; i < 33; i++) v[i].clear();
    for(int i = 0; i < p; i++){
      int x,y,z;
      cin >> x >> y >> z;
      x--;y--;
      v[x].push_back(edge(y,z));
      v[y].push_back(edge(x,z));
    }

    priority_queue<P,vector<P>,greater<P> > que;
    for(int i = 0; i < 1<<9; i++) fill(d[i],d[i] + 33,1 << 28);
    d[0][a] = 0;
    que.push(P(0,make_pair(0,a)));
    while(!que.empty()){
      P p = que.top();que.pop();
      if(d[p.S.F][p.S.S] < p.F) continue;
      for(int i = 0; i < (int)v[p.S.S].size(); i++){
	for(int j = 0; j < n; j++){
	  if(p.S.F & 1 << j)continue;
	  if(d[p.S.F | 1 << j][v[p.S.S][i].to] > p.F + v[p.S.S][i].cost / t[j]){
	    d[p.S.F | 1 << j][v[p.S.S][i].to] = p.F + v[p.S.S][i].cost / t[j];
	    que.push(P(d[p.S.F | 1 << j][v[p.S.S][i].to],make_pair(p.S.F | 1 << j,v[p.S.S][i].to)));
	  }
	}
      }
    }
    double ret = (double)(1 << 28);
    for(int i = 0; i < 1 << 9; i++){
      ret = min(ret,d[i][b]);
    }
    if(ret == 1 << 28) puts("Impossible");
    else cout << ret << endl;
  }
}