Google Code Jam 2014 Round 1A A問題 - Charging Chaos

Source

Google Code Jam 2014 Round 1A A問題
Problem Statement

問題概要

$N$ 個のデバイスの電源プラグの形と，$N$ 個のコンセントの形が与えられる．
形は $L$ 文字の $\{0,1\}$ のみからなる文字列で表される．
コンセントはスイッチを押すと変形でき，スイッチ $k$ を押すと，全てのコンセントの $k$ 文字目が $0$ → $1$，$1$ → $0$ と変更される．（$1 \leq k \leq L$）
各デバイスは同じ形（すべての文字が一致）する場合のみコンセントに刺すことができる．
全てのデバイスを同時にコンセントに指したいとき，最小で何回スイッチを押す必要があるかを求める問題．
不可能ならばそれを指摘する．

解法

$1$ 個目のデバイスを，どのコンセントに対応させるかの $N$ 通りを全部試す．
一致させるためには，どのスイッチを押す必要がある家が一意に定まる．
その時，全てのデバイスをコンセントにさせるかをチェックするには，電源プラグの形とコンセントの形が（それぞれソートした後に）全部一致するかを調べれば良い．
時間計算量は $O(N^2 L \log N)$ で，ソートせずにハッシュなどでチェック，$L$ ビットを $\verb|long long|$ に押し込めるとかすると $O(N^2)$ になる．

C++によるスパゲッティなソースコード

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

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

#define INF 1000000000

vector<int> reader(void){
  int i;
  vector<int> res;
  char buf[1000];
  scanf("%s",buf);
  for(i=0;;i++){
    if(buf[i]=='\0') break;
    res.push_back(buf[i]-'0');
  }
  return res;
}

int main(){
  int i, j, k;
  int T, cnt = 0;
  int N, L;
  int res, tmp;
  char buf[1000];
  vector<int> fst[200], sec[200];
  vector<int> mfst[200], msec[200], modi;

  scanf("%d",&T);
  while(T--){
    fprintf(stderr,"rest %d\n",T);
    printf("Case #%d: ", ++cnt);

    scanf("%d%d",&N,&L);
    rep(i,N) fst[i] = reader();
    rep(i,N) sec[i] = reader();

    res = INF;
    rep(k,N){
      modi = sec[k];
      rep(i,L) modi[i] ^= fst[0][i];

      rep(i,N){
        mfst[i] = fst[i];
        rep(j,L) mfst[i][j] ^= modi[j];
      }
      rep(i,N) msec[i] = sec[i];

      sort(mfst, mfst+N);
      sort(msec, msec+N);

      rep(i,N) if(mfst[i] != msec[i]) break;
      if(i<N) continue;

      tmp = 0;
      rep(i,L) tmp += modi[i];
      res = min(res, tmp);
    }

    if(res==INF) puts("NOT POSSIBLE"); else printf("%d\n",res);
  }

  return 0;
}

Current time: 2024年04月24日22時31分06秒
Last modified: 2014年04月26日14時25分47秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2014 GCJ_2014_Round_1A
トップページに戻る

Logged in as: unknown user (not login)

ログイン：