Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

|

2015-05-03

Google code jam 2015 Round1B B. Noisy Neighbors

15:45 |  Google code jam 2015 Round1B B. Noisy Neighbors  - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2015 Round1B B. Noisy Neighbors  - kojingharangの日記  Google code jam 2015 Round1B B. Noisy Neighbors  - kojingharangの日記 のブックマークコメント

  • 1セルに高々1人入れる R*C のグリッドがある。ここに住人を N 人いれたとき、住人が隣り合ってる辺数の最小値を求めよ。
  • small 1≦R*C≦16, large 1≦R*C≦10,000
  • smallは全探索
  • largeは、半分くらいまでは色が多い市松模様状に置いてくのがよいはずで、その後はやむなく影響の少ないところから置いてけばよさげ。
  • 具体的には、あるセルに置いた時すでに置いてあるセルとX辺で接するようなのがY個ある (X in [0, 4]) を求めておいて、X が小さい順に N から min(N, Y) を引いていく。
  • 4x4, N in [0, 16] の small 解を眺めたところそれでよさげなので実装開始。(証明できてないけど
  • R*Cが偶数のときは「置くと既に置いてあるとこと2辺と接する」ようなセルが 2 コ, 3辺はその他の外周で置いてない個数, 中は 4辺, R*Cが奇数なら云々, 1x? なら云々, ... (めんどくさい
  • 書いた
  • small解と比較してると、5x3, N=13 のときはもう1つの市松模様状に置かないといけないことに気づく
■■■■■
■□■□■
■■■■■
5x3, N=13→答え14

■□■□■
□■□■□
■□■□■
↑これ前提で9個目以降を□に置いて行くと答え15になってしまう

□■□■□
■□■□■
□■□■□
↑こっちだと14

  • 市松模様を2通り試して min をとる必要があるな...(めんどくさい
  • 手動で求めるとめんどくさいしこれはミス不可避だなぁ
  • R*C≦10,000だから実際に塗ってみて数えればよいのだ
  • 0辺と接するのがY個、も同様の仕組みで数えていけばいいのか。けっこうきれいになった。
  • 最大ケースとか入念にチェックして large download
  • 180ケース目で Bus error →ファッ!?
  • (ていうかテストケース1000個だったのか)
  • やばいまた 8 分デバッグだ.....
  • VVI を char[][] に変えてみる
  • gdb を付けてみる → command not found (◞‸◟)
  • ...
  • お、なぜか B-large.in に対してだけ small コードで実行していた
  • 落ち着いて再実行して提出
  • Accepted
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

char m[10010][10010]; // 無駄
ll large(ll W, ll H, ll N) {
	if(W>H) swap(W, H);
	// W<=H

	ll ans = 1LL<<60;
	REP(eo, 2) {
		ll NN=N;

		VI n(5);
		CLEAR(m, 0);
		REP(y,H)REP(x,W) if((x+y)%2==eo) m[y+1][x+1]=1;
		REP(y,H)REP(x,W) {
			int co=0;
			REP(dir, 4) if(m[y+dy[dir]+1][x+dx[dir]+1]) co++;
			n[co]++;
		}
		ll lans = 0;
		REP(i, 5) {
			ll use = min(NN, n[i]);
			lans += use * i;
			NN -= use;
		}
		if(NN) cout<<"ERR "<<W<<" "<<H<<" "<<N<<" eo "<<eo<<endl;
		assert(NN==0);
		ans = min(ans, lans);
	}
	return ans;
}

int main() {
	int test_cases;
	cin>>test_cases;
	ll W,H,N;
	string s;
	
	REP(ttt, test_cases) {
		cin>>H>>W>>N;
		ll ans = large(W, H, N);
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

  • おまけ: おっちょこちょいな command line history
  766  G++ -O2 Bs.cpp && ./a.out < a.txt
  767  G++ -O2 Bs.cpp && ./a.out < a.txt
  768  G++ -O2 Bs.cpp && ./a.out < B-small-attempt0.in > try_bs.txt 
  769  diff b try_bs.txt                                              ← small解と一致確認、よかった
  770  G++ -O2 BsRef.cpp && ./a.out < B-small-attempt0.in > b         ← b が古くなってたら困るので念のため small 解の出力を更新しておこう
  771  diff b try_bs.txt                                              ← small解と一致確認、よかった
  772  G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt            ← largeをsmallコードで実行! ROCK! (Bus error)
  773  G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt            ← (Bus error) (つд⊂)ゴシゴシ
  774  G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt            ← (Bus error) ...???
  775  gdb ./a.out < B-large.in > obl.txt                             ← -bash: gdb: command not found (カッコわるい)
  776  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  777  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  778  G++ -O2 BsRef.cpp && ./a.out < a.txt                           ← cout<<"ok"<<endl; を入れてどこまで実行できてるか見るなど
  779  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  780  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  781  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  782  G++ -O2 Bs.cpp && ./a.out < a.txt                              ← やっと気づいた(´・ω・`)
  783  G++ -O2 Bs.cpp && ./a.out < a.txt 
  784  G++ -O2 Bs.cpp && ./a.out < B-large.in                             ← 動くじゃ〜ん
  785  G++ -O2 Bs.cpp && ./a.out < B-large.in > obl.txt 
  786  G++ -O2 Bs.cpp && ./a.out < B-small-attempt0.in > try_bs.txt 
  787  diff b try_bs.txt                                              ← 念のため念のためsmall解と一致確認、よかった 

2015-04-19

SRM 656 Div1 250 RandomPancakeStack

01:18 |  SRM 656 Div1 250 RandomPancakeStack - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 656 Div1 250 RandomPancakeStack - kojingharangの日記  SRM 656 Div1 250 RandomPancakeStack - kojingharangの日記 のブックマークコメント

  • パンケーキが N 個あり、パンケーキ i の直径は i+1 でおいしさは d[i] である。残ってるパンケーキから等確率で 1 個選びある皿に乗せていく。
  • 皿に乗ってる一番上のパンケーキの直径より大きなのが選ばれた時点で終了。取るやつがなくなっても終了。おいしさの期待値を求めよ。
  • 1≦N≦250, 1≦d[i]≦1000
  • DPが思いつかないので...
  • 1/N! の確率で [1, N] の permutation p が選ばれることになる。これを p[i-1]>p[i] である最大の i までについて Σd をとったものがその場合のおいしさ。
  • 縦に N! 通り、横に permutation を書いていってどうにか規則的に足せないか考えていると...
  • m+1 番目が X でありそれがおいしさにカウントされるような permutation の数は O(1) で求められることに気づく。
  • ? ? ? X ? ?
  • 前半は X より大きな N-x 個の数から m 個選び、後半は残りの N-m-1 個の順列なので Combination(N-x, m) * (N-m-1)!
  • というわけで、全 m, X についてその場合の数 * d[X] を足して最後に N! で割ったものが答え。
  • Accepted
  • dp でやる場合は dp[Topの直径][今まで何個使ったか], dp[N][0]=1, 配った時パンケーキごとに使った数を覚えていくとよい模様。
#define D long double

class RandomPancakeStack {
	public:
	D fac(int x) {
		D v = 1;
		REP(i, x) v*=i+1;
		return v;
	}
	D f(int x, int m, int N) {
		int k = N-m-1;
		if(N-x<m) return 0;
		return fac(N-x)*fac(k)/(fac(m)*fac(N-x-m));
	}
	double expectedDeliciousness(vector <int> d) {
		int N = d.size();
		D ans = 0;
		REP(v, N) {
			D lans = 0;
			REP(di, N) {
				D z = f(v+1, di, N);
				lans += z;
			}
			lans *= d[v];
			ans += lans;
		}
		D div = fac(N);
		return ans / div;
	}
};

2015-04-18

Google code jam 2015 Round1A B. Haircut

19:29 |  Google code jam 2015 Round1A B. Haircut  - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2015 Round1A B. Haircut  - kojingharangの日記  Google code jam 2015 Round1A B. Haircut  - kojingharangの日記 のブックマークコメント

  • B個の1人用床屋があり床屋 i は 1 人切るのに M[i] 分(整数)かかる。行列ができており、同時に複数の店が空いたら i が小さい店にすぐ入る。N人目の人は何番の床屋で切ることになるか?
  • (Large) 1≦テストケースの数≦100, 1≦N≦10^9, 1≦B≦1000, 0≦M[i]≦100000
  • small はとりあえず LCM(M) を求めて N % その時間までに切り終わった人数までシミュレート。
  • ぱっと思いつかなかったので、C small 解いて戻ってきたところ、時刻を決めると切り終わった人数が O(B) で分かることに気づく
  • そんな感じで二分探索して Bl.cpp を書く → Bs.cpp で解いた B-small の結果と一致 → large download, 実行
  • Bl.cpp と思っていたビルド&実行ソースは Bs.cpp だった....。Bl.cpp はただの 1 回も実行されてなくてバグりまくり → 8分デバッグ → 死
  • (あとで)
  • N 人目が始まる最小の時刻は簡単には求められないんじゃないかと思って累計 N-1 人終わったあたりをぐにぐにしてたが、
  • t が終わった時点で始まってる人数は Σ t/M[i]+1 と終了人数 + B で簡単に求まるのだった。終わったらすぐ始まるのだから、そりゃそうだ。
  • N 人目が始まった時刻には実際のところ複数の人が始まってる可能性があるので、B を後ろからみてって割り切れるとこをカウントして N になったとこが答え。
  • 終わった人数基準でやるなら、N 人目が始まる時刻の下限であるのべ N-B 人が終わった時刻からシミュレートすればよい。(10^8 なのでOK)
  • コマンドライン安全標語: 一、自分を信用するべからず
  • Accepted in practice
int main() {
	int test_cases;
	cin>>test_cases;
	ll B,Nth;
	string s;
	REP(ttt, test_cases) {
		cin>>B>>Nth;
		VI w(B);
		REP(i, B) cin>>w[i];
		ll lo=-1, hi=1LL<<60; // hi ... began at least N
		while(lo+1<hi) {
			ll mid = (lo+hi)/2;
			ll began = 0;
			REP(i, B) began += mid / w[i] + 1;
			if(began<Nth) lo=mid; else hi=mid;
		}
		ll t = hi;
		ll began = 0;
		REP(i, B) began += t / w[i] + 1;
		ll beganP = 0;
		REP(i, B) beganP += (t-1) / w[i] + 1;
		assert(beganP<Nth);
		assert(Nth<=began);
		int ans = 0;
		for(int i=B-1;i>=0;i--) {
			if(t%w[i]==0) {
				if(began--==Nth) {ans = i+1; break;}
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

2015-04-14

2015 TCO Round1A 1000 Revmatching

10:38 |  2015 TCO Round1A 1000 Revmatching - kojingharangの日記 を含むブックマーク はてなブックマーク -  2015 TCO Round1A 1000 Revmatching - kojingharangの日記  2015 TCO Round1A 1000 Revmatching - kojingharangの日記 のブックマークコメント

  • N頂点-N頂点 の重み付き2部グラフが与えられる。完全マッチングにならないように辺を減らしたい。消す辺の重みの合計の最小値を求めよ。
  • 1≦N≦20, 0≦重み≦9
  • 左右のどれかの頂点を完全に孤立させれば少なくとも完全マッチングにはならんだろう
  • 十分か分からないけど他に思いつかないので書いてみる→最後のサンプルでだめ
  • ググるもいまいちそれっぽいのが出ず。
  • フロー?
  • 片側の頂点数 20 だから部分集合総当り?
  • (あとで)
  • Hall の定理を使うらしい。
  • 任意の左の頂点部分集合 L に対応する右の頂点集合 R が |L|≦|R| ←→完全マッチングが存在する
  • ある L について |L|>|R| になればいいので、
  • 部分集合それぞれについて、|L|>|R|になるように R につながる辺を消した時の最小コストを求めてその最小値を返せばよい。
  • ほー、覚えておこう。
  • Accepted in practice
class Revmatching {
public: 
	int smallest( vector <string> A ) { 
		ll N = A.size(); 
		ll ans = 1000000; 

		RANGE(b, 1, 1<<N) {
			VI rmCosts(N); 
			// li ... left index  ri ... right index
			REP(li, N) if(b>>li&1) REP(ri, N) rmCosts[ri] += A[li][ri]-'0'; 
			sort(ALL(rmCosts));
			ll nL = POPCOUNT(b); 
			ll rmCost = 0;
			// rm R nodes as little as possible so that |L|>|R|, which means |L|-1 = |R|
			REP(i, N - (nL-1)) rmCost += rmCosts[i];
			ans = min(ans, rmCost); 
		} 
		return ans; 
	}
}; 

2015-04-11

2015 TCO Round1A 500 Autogame

03:34 |  2015 TCO Round1A 500 Autogame - kojingharangの日記 を含むブックマーク はてなブックマーク -  2015 TCO Round1A 500 Autogame - kojingharangの日記  2015 TCO Round1A 500 Autogame - kojingharangの日記 のブックマークコメント

  • N個の場所がありそれぞれにどこかの場所を指す矢印の根元がある。各場所に最大1個のトークンを置き一斉に矢印の通りに動かすのを K 回やる。
  • 同じ場所にトークンが2つになってしまったら負け。負けないようなトークンの置き方は何通りあるか。mod 10^9+7で。
  • 1≦N≦50, 1≦K≦10^9
  • 全場所にトークンを置いたとして、K回動かしてトークンの位置を追跡する。
  • 枝分かれしないので、1回合流したら合流しっぱなし。
  • なので、最終的に場所が違う→独立に選べる
  • 各場所について、最終的に集まったトークンの中から1個選ぶor0個選ぶ、ということで場所ごとに個数+1を掛ければよさげ。
  • トークンIDの集合になるから vector<int> かとおもったけど単に個数でいいのだ。
  • 最初 50 回くらいやれば収束するだろうからと 1000 回まわしたが K が小さいときもあるんだったということで min(K, 1000) に変更。あぶない。
  • Accepted
class Autogame {
	public:
	int wayscnt(vector <int> a, int K) {
		int N=a.size();
		VI w(N);
		REP(i, N) w[i]=1;
		REP(loop, min(K, 1000)) {
			VI nw(N);
			REP(i, N) nw[a[i]-1]+=w[i];
			w = nw;
		}
//		cout<<w<<endl;
		ll ans=1;
		REP(i, N) {
			ans*=w[i]+1;
			ans %= 1000000007LL;
		}
		return ans;
	}
};
|