Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1882-63e5c345
この記事にトラックバックする(FC2ブログユーザー)

SRM496 DIV1 MEDIUM - OneDimensionalBalls (この記事を編集する[管理者用])

Source

TopCoder SRM496 DIV1 MEDIUM (500pt)
Problem Statement
SRM496 DIV1 自分の参加記録

問題概要

1次元上を左右どちらにかわからないが速度1で動いている粒子がある.
最初N個 (50以下) の粒子の初期位置が与えられる.
その後,いくらか正の時間が経った後 (たった時間は未知) のM個 (N以上) の粒子の位置が与えられる.
それは,N個の粒子に加え,M-N個の粒子を加えている.
さて,最初のN個の粒子と,M個の粒子の対応関係としてvalidなものはいくつあるか,を求める問題.
最初,最後には,同じ位置には粒子はないとする.

解法

あるボールに着目して,それがどこに移動したか50通りしかないので,経過時間の候補は高々50通りしかないので全部調べる.
後は,2部グラフのマッチングの個数を求める問題に帰着される.
その2部グラフは,連結成分を取り出すと,/\/\のような形をしているので,そのマッチングの個数は解析的に簡単に求まるので,それをかければ良い.
例えば,/\/\だったら,上の2点をどっちに繋げるか,左左,左右,右右の3通り.
同様に,上の点がn個で,下の点がn+1個だと,左左…左,右左…左,右右…左,…,右右…右,のn+1通り.

以下のコードは,結局,グラフが特徴的な形をしているので,枝刈りが効くのと,答えの最大値はそんなに大きく無いので,全探索してみました,というコード.
(本番は,これで通してしまったが良い解法とは言えない)

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int ab(int x){if(x<0)return -x; return x;}

int a[60], b[60], as, bs;
int tmm[6000], tm_size, T;

int edgeA[51][51], esA[51];
int edgeB[51][51], esB[51];
int useA[51], useB[51];
ll res;

int is_free(int num){
  int i,res=0;
  rep(i,esB[num]) if(!useA[edgeB[num][i]]) res++;
  return res;
}

void brute_force(ll now){
  int i,j,k,ok,go,mul;

/*  printf("%d : ",T);
  rep(i,as) printf("%d ",useA[i]);
  printf(": ");
  rep(i,bs) printf("%d ",useB[i]);
  printf(": %lld\n",now);*/

  k=0; rep(i,as) if(!useA[i]) k++;
  if(k==0){
/*    printf("%lld\n",now);*/
    res += now; return;
  }

  rep(i,as) if(!useA[i]){
    ok=0;
    rep(j,esA[i]){
      k = edgeA[i][j];
      if(useB[k]==0){ ok++; go=k; }
    }
    if(ok==0) return;
    if(ok==1){
      useA[i]^=1; useB[go]^=1;
      brute_force(now);
      useA[i]^=1; useB[go]^=1;
      return;
    }
  }

  rep(i,as) if(!useA[i]){
    ok=1;
    rep(j,esA[i]){
      k = edgeA[i][j];
      if(useB[k]) continue;
      if(is_free(k)!=1) ok=0;
    }
    if(!ok) continue;
    mul = 0;
    rep(j,esA[i]){
      k = edgeA[i][j];
      if(useB[k]) continue;
      mul++;
    }
    useA[i] ^= 1;
    brute_force(now*mul);
    useA[i] ^= 1;
    return;
  }

  rep(i,as) if(!useA[i]){
    rep(j,esA[i]){
      k = edgeA[i][j];
      if(useB[k]) continue;
      useA[i] ^= 1; useB[k] ^= 1;
      brute_force(now);
      useA[i] ^= 1; useB[k] ^= 1;
    }
    return;
  }


}

class OneDimensionalBalls {
public:
long long countValidGuesses(vector <int> A, vector <int> B) {
  int i,j,k;

  res = 0;
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  as = A.size(); bs = B.size();
  rep(i,as) a[i]=A[i]; rep(i,bs) b[i]=B[i];

  tm_size=0;
  rep(i,as) rep(j,bs) tmm[tm_size++] = ab(a[i]-b[j]);
  sort(tmm,tmm+tm_size);

  k=0;
  rep(i,tm_size){
    if(tmm[i]==0) continue;
    if(k && tmm[k-1]==tmm[i]) continue;
    tmm[k++]=tmm[i];
  }
  tm_size = k;

  rep(k,tm_size){
    T = tmm[k];
    rep(i,as) esA[i]=0; rep(i,bs) esB[i]=0;
    rep(i,as) rep(j,bs) if(ab(a[i]-b[j])==T){
      edgeA[i][esA[i]++]=j;
      edgeB[j][esB[j]++]=i;
    }
    rep(i,as) useA[i]=0;
    rep(i,bs) useB[i]=0;

    brute_force(1);
  }
  
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1882-63e5c345
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。