JAG 2015 spring

去年と同じICPCのチームSleep(18000000);で参加していました.
13:00 微妙に遅れたら開始遅延してイェイ.
13:30 開始 前から適当に割り振って読む.A,B,C,Dあたりを読んでも解けそうなのがなかったので順位表を見ると,Lを通してるチームが合ったので読む.自明なので通す(0:40,1完).
14:00 woがAを解き始める バグってつらそうだった wafrelkaがDを考えていた.適当に後ろのほうを読みながら他のチームが通していたFを見る.やるだけなので書く.
14:50 →全ケースTLE??? とりあえず交代してwoにAのデバグとIの実装を続けてもらう.
15:30 なんか初期化が遅いのではないか・・・? 3e6までの階乗のinvを毎回ex(x,mod-2)していたが,よく考えると3e6*log(1e9)結構遅いぞ・・・→nまでのinvを線形でうめるやつやってからかけると通った(ちょっとひどいがこれでTLEするのは今後気をつけるべきだなあ)　(2:00,2完)
PCがあいたのでwafrelkaがDの実装を始める.ここらへんで,
wo「コード印刷できないけどどうしよう」(図書館でやっていたので)
sigma「既にACした問題にコードを投げる一般的なテクがある」
wafrelka「そんなのあるの」
なる会話が行われて,その先Lがsubmit会場になる(キューを無駄に埋めてごめんなさい)
あと、読解で
し「G読めない・・・ 読んで」
を「これ読めないよね～」
し「("読めません"というclarを投げる)」
わ「何やってるの」
を「読めた」
「プロ」
ジャッジの皆さんすいませんでした(ちなみに返答は"Clarifications must be written in English.")
16:30 woのデバグと平行してwafrelkaのDがサンプル通る 投げる WA(デデドン).わ「3/4くらい通ってる」し「long longにした?(問題読んでない)」わ「う～ん あっ」→AC(3:20,3完)
その間にGを詰めていたので書き始める.なぜかサンプルが通らない・・・
17:30 wafrelkaとwoでAのバグを見つけていた→なおす→一発AC,プロ(4完,4:15)
17:50 あと40分でGのバグ取り・・・行けるでしょ とか言ってprintfデバッグをする なんか微妙にずれる?woがIが解けそうだと言っていたのでバグ見つける間実装してもらう.
この辺でチームのLが凍結される(ACした後でも提出すると青くなるっぽい?).
18:20 (ここでGのバグに気づく)さすがにIを通すよりはバグなおすほうが期待値高そうだったので代わってもらう.
18:26 サンプル通る 投げる WA(デ デ ド ン).WAになって踊っていた
18:28 一個改善策を見つけてそれを実装してみるがコンテスト終了(Ω＼ζ°)ﾁｰﾝ)
18:31 投げたらWAだった.はい.(ていうか既におかしな挙動してる時点でこっちのほうがまだましかもみたいな改善はだいたい無駄なんだよな).
twitterをしながら帰る 途中でGのミスに気づく(辞書順最小を求めるのにreverseの辞書順最大を求めていた,バカか(反例は{ACB,BAC}とか))
大絶望しながら3人で渋谷でぶやぶやする.最近kitayutaに連れてってもらって結構気に入った非ラーメン店に行った.うまい,おおい,やすい でとても良かった.

総括
7位でした.G通してても6位だったぽいしまあいいか(全然良くない).いつもどおり自分が自明問通して他の二人に難しそうな問題を通してもらう,みたいな感じにしたけどやっぱりバグがつらそうだった.後半wafrelkaが暇になったっぽいのがあまりよくなかったかもしれないけど難しそうなセットだったからしょうがないのかなあ)(でも簡単な問題もまあまああったし流石に4完は（◞‸◟）).
チーム練習もしたほうが良さそうだし自分の実力もあげないとまずい・・・.

自分のACコード
L:なんかstackoverflowしそうだったけどAtCoder出し大丈夫だろとか言ったら大丈夫だった

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) c.begin(),c.end()
using namespace std;
int H,W,g[21][21][21][21];
string s[20];
int calc(int a,int b,int c,int d){
	//printf("abcd=%d %d %d %d\n",a,b,c,d);
	if(g[a][b][c][d]>=0) return g[a][b][c][d];
	set<int> st;
	for(int x=a;x<c;x++) for(int y=b;y<d;y++){
		if(s[x][y]=='X') continue;
		int gr=calc(a,b,x,y)^calc(x+1,b,c,y)^calc(a,y+1,x,d)^calc(x+1,y+1,c,d);
		st.insert(gr);
	}
	int x=0;
	while(binary_search(all(st),x)) x++;
	return g[a][b][c][d]=x;
}
int main(){
	cin>>H>>W;
	rep(i,H) cin>>s[i];
	rep(i,21) rep(j,21) rep(k,21) rep(l,21) g[i][j][k][l]=-1;
	int d=calc(0,0,H,W);
	if(d==0) puts("Second");
	else puts("First");
}

G:包除するだけ(この前のSRMよりは気づきやすい),invはextgcdのほうがいいかなあ(たまに早くなるし)でもextgcdむずいんだよなあ(なんか負の数が帰ってきたりするのを忘れてしまう).

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define fs first
#define sc second
#define all(c) c.begin(),c.end()
#define show(x) cout<<#x<<" "<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll mod=1e9+9;
ll f[3000001],g[3000001],invp[3000001];
ll ex(ll x,ll p){
	ll a=1;
	while(p){
		if(p%2) a=a*x%mod;
		x=x*x%mod;
		p/=2;
	}
	return a;
}
ll inv(ll x){
	return ex(x,mod-2);
}
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
int par[36];
void init(int N){
	rep(i,N) par[i]=i;
}
int find(int x){
	if(x==par[x]) return x;
	return par[x]=find(par[x]);
}
void unite(int x,int y){
	x=find(x),y=find(y);
	par[x]=y;
}
int N,M;
vector<int> ash;
vector<P> good,bad;
ll ans;
//ll allcnt=0;
ll calc(){
	int K=ash.size();
//	show(K);
	int cnt[36]={};
	rep(i,K) cnt[find(i)]++;
	int a=0,b=0;
	rep(i,K){
//		allcnt++;
		if(i!=find(i)) continue;
		if(cnt[i]>3) return 0;
		if(cnt[i]==3) a++;
		if(cnt[i]==2) b++;
	}
//	show(a);
//	show(b);
	ll lef=3*N-3*a-2*b;
	ll val=f[lef]*invp[(lef-b)/3]%mod*g[(lef-b)/3]%mod;
	return val;
}
ll invs[3000001];
int main(){
	cin>>N>>M;
	invp[0]=1;
	ll inv6=inv(6);
	f[0]=1,g[0]=1;
	rep(i,3*N) f[i+1]=f[i]*(i+1)%mod;
	invs[1]=1;
	for(int i=2;i<=3000000;i++){
		ll a=mod/i+1;
		invs[i]=a*invs[a*i-mod]%mod;
		if(invs[i]<0) invs[i]+=mod;
//		show(invs[i]);
	}
//	show(invs[2]);
	rep(i,3*N) g[i+1]=g[i]*invs[i+1]%mod;
	rep(i,3*N) invp[i+1]=invp[i]*inv6%mod;
	rep(i,M){
		int a,b,c;
		cin>>a>>b>>c;
		ash.pb(a);
		ash.pb(b);
		if(c==0){
			good.pb(P(a,b));
		}else{
			bad.pb(P(a,b));
		}
	}
	sort(all(ash));
	ash.erase(unique(all(ash)),ash.end());
	rep(i,good.size()){
		good[i].fs=lower_bound(all(ash),good[i].fs)-ash.begin();
		good[i].sc=lower_bound(all(ash),good[i].sc)-ash.begin();
	}
	rep(i,bad.size()){
		bad[i].fs=lower_bound(all(ash),bad[i].fs)-ash.begin();
		bad[i].sc=lower_bound(all(ash),bad[i].sc)-ash.begin();
	}
	int K=bad.size();
	rep(i,1<<K){
		init(36);
		for(P p:good){
			unite(p.fs,p.sc);
		}
		int cnt=0;
		rep(j,K){
			if((i>>j)&1) unite(bad[j].fs,bad[j].sc),cnt++;
		}
		ll tmp=calc();
//		show(tmp);
		if(cnt%2==0) add(ans,tmp);
		else add(ans,-tmp);
	}
//	show(allcnt);
	cout<<(ans+mod)%mod<<endl;
}