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)$ になる.
#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月27日04時16分39秒
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)