2014 Google Code Jam Round 1A

こんにちは。chigichanです。

最近色々と忙しかったような気がしてたけど、そうでもないようなみたいな日々を過ごしてます。

さて、昨年参加をすっかり忘れていたGCJに今年は参加(レジ成功)したので、そこら辺の話。

GCJ(Google Code Jam)は天下のグーグルさんが年に一回開いてくれているコンテストで、結構有名ですね。

何はともあれ僕みたいな底辺プログラマはTシャツをゲットを頑張るわけですね。

で、もちろん参加すれば無条件にもらえるわけでもなくて、ある程度勝ち進めばの話なんですよ。

順に

Qualification Round

Online Round 1: Sub-Round A
Online Round 1: Sub-Round B
Online Round 1: Sub-Round C

Online Round 2

Online Round 3

Onsite Finals

となっています。

でそれぞれのRoundを上がるのにも条件が会って今日のは上位1000位以上で進めました。

結果から言うとダメでしたね。

まあそこら辺の話を今日はしようと思います。

一応ここです
本家のサイト

includeとか

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<numeric>
using namespace std;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
#define INF 1e+8
#define EPS 1e-7
#define PB push_back
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
typedef pair<int,int> Pii;
typedef vector<int> vi;

僕は英語ができないマンなので実際とは大分異なる訳をしていると思いますが、
そこは善意で、ね。

問題A Charging Chaos

電源供給のタイプが(1,0)で表される(長さはL)家電をn個持ってる。

その人の住む家にもn個の電源供給口がある。もちろんその電源供給口にも家電と同様にタイプ(長さはL)がある。

家電を充電したいときはこの(1,0)のタイプが合致していないと出来ない。

また、もう一つの特徴として、n個すべての電源供給口のそれぞれのi番目(0 ≦ i ＜ L)
のタイプを変えることができるボタンがL個ある。タイプを変えるとは0 -> 1 , 1 -> 0のことである。

この時にボタンを押す回数を最も少なくして全部の家電を一度に一気に充電したい。
出来ない場合は "NOT POSSIBLE" と出力する。

例

電源供給口のタイプ 01 10 11
家電のタイプ 00 11 10

この時は1番目(0-base)のボタンを一度押せば

01 10 11 これが

00 11 10 こうなる。

僕がこのフィーリングリーディングでなんとなく意味がつかめた時に考えたことは、

まず、ボタンは複数回押す必要がないことはすぐに分かる
(複数回押すと0,1しかないので今まできたことのある状態に確実に戻るから)。

次に、先頭から順に確かめて行って(ボタンを押したりして)途中で充電できなくなった段階でそれ以降、
どんなに頑張ってボタンをおしても"NOT POSSIBLE"になることもわかる。

毎回ソートする(ボタンを押すと1,0が反転するから)ことでいい感じに比較できるはず。

きっと先頭からボタンを押すか否か決めていく時に出来る限りボタンを押さずに行くほうがいいに決まっている(貪欲法でおｋ)。

という考察でコードを書いていきました。

　かなぁとか思ってsampleも通ったし提出したら間違ってて辛かった。

その時のコード

int main(){
	int T;
	scanf("%d",&T);
	rep(t,T){
		int ans = 0;
		int n,l;
		string de[160];
		string con[160];
		scanf("%d%d",&n,&l);
		rep(i,n){
			cin >> con[i];
		}
		rep(i,n){
			cin >> de[i];
		}
		sort(de,de+n);
		sort(con,con+n);
		int cnt = 0;
		rep(i,l){
			int fcnt = 0;
			rep(j,n){
				if(de[j][i] != con[j][i]){
					fcnt++;
				}
			}
			if(fcnt == 0)continue;
			else{
				rep(j,n){
					if(con[j][i] == '0')con[j][i] = '1';
					else con[j][i] = '0';
				}
				sort(con,con+n);
				bool f = false;
				rep(j,n){
					if(de[j][i] != con[j][i]){
						f =  true;
						break;
					}
				}
				if(f){
					cnt = -1;
					break;
				}
				cnt++;
			}
		}
		if(cnt == -1){
			printf("Case #%d: NOT POSSIBLE\n",t+1);	
		}
		else printf("Case #%d: %d\n",t+1,cnt);
	}
	return 0;
}

この時すでに、40分近く経過していた。

で、結局これは貪欲ではないのかもしれない。
と思い始めるのにこれから30分くらいまたかかったんですね(ここからつらみが増す)
なぜなら、具体的に反例が出たわけではないですが、提出したoutputみたら異常に"NOT POSSIBLE"多かったので

そして、ちょうど0と1の数が一致している時にボタンを押したほうがいい時もあれば、悪い時もあることがわかったのはそれから何分たったかわかりません。

そこでbfsみたいな感じで更に不安だったからpriority_queue使ってボタンを押した回数が少ない順に取り出しながら書いたら、通りますた。

class Data{
	public:
	int in;
	int cnt;
	string a[200];
	Data(){}
	Data(int _in,int _c,string x[200]){
		in = _in;
		cnt = _c;
		rep(i,200){
			a[i] = x[i];
		}
	}
	bool operator<(const Data &z)const{
		return cnt > z.cnt;
	}
};
int main(){
	int T;
	scanf("%d",&T);
	rep(t,T){
		int n,l;
		string de[200];
		string con[200];
		scanf("%d%d",&n,&l);
		rep(i,n){
			cin >> con[i];
		}
		rep(i,n){
			cin >> de[i];
		}
		sort(de,de+n);
		sort(con,con+n);
		priority_queue < Data > Q;
		Q.push(Data(0,0,con));
		int ans = -1;
		int cnt = 0;
		while(!Q.empty()){
			Data d = Q.top();Q.pop();
			if(d.in == l){
				ans = d.cnt;
				break;
			}
			bool f = false;
			rep(i,n){
				if(d.a[i][d.in] != de[i][d.in]){
					f = true;
				}
			}
			if(!f){
				Q.push(Data(d.in+1,d.cnt,d.a));
			}
			rep(i,n){
				if(d.a[i][d.in] == '1')d.a[i][d.in] = '0';
				else d.a[i][d.in] = '1';
			}
			sort(d.a,d.a + n);
			bool ff = false;
			rep(i,n){
				if(d.a[i][d.in] != de[i][d.in]){
					ff = true;
				}
			}
			if(f && ff){
				continue;
			}
			if(!ff){
				Q.push(Data(d.in+1,d.cnt+1,d.a));
			}
		}
		if(ans == -1){
			printf("Case #%d: NOT POSSIBLE\n",t+1);	
		}
		else printf("Case #%d: %d\n",t+1,ans);
	}
	return 0;
}

まぁ結局全探索みたいな事をしたわけですね。
つらみだなぁ。
ここで25 Point獲得するのになんと1時間40分かかった。(嘘貪欲提出から1時間)

けど、解いてみた感じは楽しかった。

問題B Full Binary Tree
あるグラフの状態が与えられるのでそれをFull Binary Treeにするにはいくつのノードを消せばいいですか？

問題があっさりわかって、木DPっぽいなーとか思いながら全探索書いてたらバグって終わった。

そのあと、もうちょい時間かけたら解けてしまったので辛い。

通ったコード

int N;
vi con[1000];
Pii solve(int p, int rt){
	int sz = 1;
	vector< Pii > child;
	rep(i,con[p].size()) {
		if(con[p][i] == rt) continue;
		Pii tmp = solve(con[p][i],p);
		child.PB(tmp);
		sz += tmp.second;
	}
	if(child.size() <= 1) {
		return make_pair(sz-1,sz);
	}
	int c1 = 0, c2 = 0, sum = sz - 1;
	rep(i,child.size()) {
		int d = child[i].second - child[i].first;
		if(c1 < d) {
			c2 = c1;
			c1 = d;
		} else if(c2 < d) {
			c2 = d;
		}
	}
	return make_pair(sum-c1-c2, sz);
}
int main(){
	int T;
	scanf("%d",&T);
	rep(t,T){
		scanf("%d",&N);
		rep(i,N-1) {
			int x, y;
			scanf("%d%d",&x,&y);
			x--; y--;
			con[x].PB(y);
			con[y].PB(x);
		}
		int ret = INF;
		rep(i,N) {
			ret = min(ret, solve(i,-1).first);
		}
		printf("Case #%d: %d\n",t+1,ret);
	}
	return 0;
}

結果的にかなり残念だった。nikollson先輩はちゃんとRound2へ進んでてやっぱつおいなぁと実感した。

それでも、あと2回チャンスはあるのでRound2へ進めるように頑張ろうと思う。