Codeforces Beta Round #8

Codeforces初参戦．WARush!!

A Train and Peter

簡単な問題なんだけど，最後まで自分の間違いに気付かなかった．終了後に手元でサンプルケースを作ってみたら一瞬で間違いがわかった…

教訓：テストケースを作ってみよう．

B Obsession with Robots

UDRLで与えられる道筋がショーテストパスかどうかを判定する問題．一度歩いた所をもう一度歩かなければいいと思っていたけど，蛇行運転もショーテストじゃないね．

123456789の順に歩くとき，同じ道は通ってないけどショーテストではない．

..67.
12589
.34..

これに気付かずWA．

C Looking for Order

終了後にダイクストラで解いた．breakを入れるかどうかでTLEがACになる．ていうかなんでここでbreakしていいのかよく分からない…

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <complex>
#include <set>
#include <vector>
#include <bitset>

#define REP(i,N)for(int i=0;i<(int)N;i++)
#define MP(a,b) make_pair(a,b)
using namespace std;

int bx,by;
int N;
int x[25],y[25];
int dp[1 << 24] = {};
int path[1 << 24] = {};
int dist[25][25];
struct State{
  int state;
  int cost;
  bool operator<(const State& s)const{
    return cost > s.cost;
  }
};

int main(){
  while (~scanf("%d %d",&x[0],&y[0])){
    N=nextInt();
    REP(i,N)
      x[i+1] = nextInt(),y[i+1] = nextInt();
    REP(i,1<<N)
      dp[i] = 1 << 25;
    REP(i,N+1){
      REP(j,N+1){
        dist[i][j] = (x[i]-x[j]) * (x[i]-x[j]) +
          (y[i] - y[j]) * (y[i] - y[j]);
      }
    }
    priority_queue<State> up;
    up.push((State){0,0});
    while (!up.empty()){
      int state = up.top().state;
      int cost = up.top().cost;
      up.pop();
      //cout << bitset<10>(state) << " " << cost << endl;
      if (state == (1 << N) -1) {
        printlineInt(cost);
        int p = state;
        int s = path[state];

        for (;; s=path[s]){
          printf("0 ");
          //cout << bitset<10>(s) << " " << bitset<10>(p) << endl;
          REP(i,N){
            if (((s & (1 << i)) ^ (p & (1 << i)))){
              printf("%d ",i+1);
            }
          }
          p = s;
          if (!s) break;
        }
        printf("0 \n");
        break;
      }
      if (dp[state] < cost) continue;
      REP(i,N){
        if (state & (1 << i)) continue;
        
        int nstate = state | (1 << i);
        int ncost = cost + (dist[0][i+1] << 1);
        if (dp[nstate] > ncost){
          dp[nstate] = ncost;
          path[nstate] = state;
          up.push((State){nstate,ncost});
        }
        
        for (int j=i+1;j<N;j++){
          if (state & (1 << j)) continue;
          int nstate = state | (1 << i) | (1 << j);
          int ncost = cost + dist[0][i+1] + dist[0][j+1] + dist[i+1][j+1];
          if (dp[nstate] > ncost){
            dp[nstate] = ncost;
            path[nstate] = state;
            up.push((State){nstate,ncost});
          }
        }
        break; // このbreakをとるとTLE
      }
    }
  }
}

だれか説明してくだしあ．

結果

1490のdiv2からスタート(´・ω・｀)．その代わり次のラウンドはdiv2onlyみたいなので出れるみたい．その次div1onlyかもしれないからぜひ上がりたい．
codeforces用のスクリプト書こうかなぁ．