Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

|

2015-06-05

SRM 660 Div1 250 Coversta

10:36 |  SRM 660 Div1 250 Coversta - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 660 Div1 250 Coversta - kojingharangの日記  SRM 660 Div1 250 Coversta - kojingharangの日記 のブックマークコメント

  • N*M のグリッドがあり、各マスに 0-9 の数字が書いてある。Pos[ ] も与えられ、あるマス p に駅を置くと p+P (P in Pos[ ]) なマスがカバーされる。
  • 異なる場所に2駅置いたとき、2駅がカバーするマスに書いてある数字の合計の最大値を求めよ。
  • 2≦N,M≦100, 1≦K=|Pos[]|≦10, -(N-1)≦Pos.x≦N-1, -(M-1)≦Pos.y≦M-1
  • カバー範囲が重なった時の処理がポイントっぽいぞ
  • naiveにやると置き方全てに対して Pos[] のとこを塗って確かめるので N^2 M^2 K -> 10^9 程度 -> むり
  • カバー範囲の重なり方は最大で K^2 個なことに気づく
  • なので「カバー範囲が重なるように2駅置いた時にカバーするマスのパターン」を最大10*10個持っておいて、
  • (1)カバー範囲が重なる2点を置いたときの最大値(N^2 M^2 K)と
  • (2)カバー範囲が重ならない2点を置いたときの最大値(事前にマス→カバー範囲の合計値をNMKで計算しておき重複かどうかをmapで覚えておくとN^2M^2logK)
  • の最大値が答え
  • (1)では、重なり方すべてK^2について最初の点から見た2点目の相対座標と最大K*2点(最初のカバー範囲∪ちょっとずらした範囲)のパターンを覚えておく
  • (2)では2点目の相対座標が(1)で計算した相対座標セットに含まれない=2点のカバー範囲が重ならない、という感じでチェックすればいい。
  • ていうことで N^2M^2logK なので良さそうではあるが、...
  • これで250か, 書いてピッタリ答えが合うとは思えない...
  • IN_RANGE(Value, Min, Max) マクロ大活躍の巻き
  • なぜかサンプルが合った → 3x3 で10ケースくらい手動テストしてOKそうなので 95pt くらいで提出
  • Accepted
  • おー通るのかよ
  • (あとで)K^2+α個で打ち切る NMK^2 解もあるのか。(そっちはなぜそれでいいか腑に落ちてない)
struct Pos {
	int x, y;
	bool operator<(const Pos v) const {
		return x*1000+y < v.x*1000+v.y;
	}
	bool operator==(const Pos v) const {
		return x==v.x && y==v.y;
	}
};
std::ostream& operator<<(std::ostream& os, const Pos& v) {
	os << "("<<v.x<<", "<<v.y<<") ";
	return os;
}

struct Pat {
	Pos ref;
	vector<Pos> pos;
};

class Coversta {
	public:
	int place(vector <string> a, vector <int> X, vector <int> Y) {
		int W=a.size(), H=a[0].size();
		int N=X.size();
		VVI one(W, VI(H));
		vector<Pat> pat;
		map<PII, int> ng;
		REP(x, W) REP(y, H) REP(i, N) {
			if(IN_RANGE(x+X[i], 0, W) && IN_RANGE(y+Y[i], 0, H)) {
				one[x][y]+=a[x+X[i]][y+Y[i]]-'0';
			}
		}
		REP(i, N) REP(j, N) if(i!=j) {
			// i-j
			int dx = X[i]-X[j];
			int dy = Y[i]-Y[j];
			auto key = MP(dx, dy);
			if(ng.count(key)) continue;
			if(dx==0 && dy==0) continue;
			ng[key] = 1;
			vector<Pos> v;
			REP(k, N) v.PB(Pos{X[k], Y[k]});
			REP(k, N) v.PB(Pos{X[k]+dx, Y[k]+dy});
			sort(ALL(v));
			v.erase(unique(ALL(v)), v.end());
			pat.PB({Pos{dx, dy}, v});
		}
		REP(i, pat.size()) {
//			cout<<pat[i].ref<<" -> "<<pat[i].pos<<endl;
//			cout<<pat[i].ref.x<<" "<<pat[i].ref.y<<endl;
		}
		ll ans = 0;
		REP(pi, pat.size()) {
			auto& p = pat[pi];
			REP(x0, W) REP(y0, H) {
				int xx = x0+p.ref.x;
				int yy = y0+p.ref.y;
				if(IN_RANGE(xx, 0, W) && IN_RANGE(yy, 0, H)) {
					ll lans = 0;
					REP(i, p.pos.size()) {
						int ex = x0 + p.pos[i].x;
						int ey = y0 + p.pos[i].y;
						if(IN_RANGE(ex, 0, W) && IN_RANGE(ey, 0, H)) {
							lans += a[ex][ey]-'0';
						}
					}
					ans = max(ans, lans);
				}
			}
		}
//		cout<<"one "<<one<<endl;
		REP(x0, W) REP(y0, H) REP(x1, W) REP(y1, H) if(!(x0==x1 && y0==y1)) {
			int dx = x0-x1;
			int dy = y0-y1;
			PII k = MP(dx, dy);
			if(!ng.count(k)) {
//				cout<<x0<<" "<<y0<<" "<<x1<<" "<<y1<<" -> "<<one[x0][y0]+one[x1][y1]<<endl;
				ans = max(ans, one[x0][y0]+one[x1][y1]);
			}
		}
		return ans;
	}
};

2015-05-13

SRM 659 Div1 250 ApplesAndOrangesEasy

23:19 |  SRM 659 Div1 250 ApplesAndOrangesEasy - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 659 Div1 250 ApplesAndOrangesEasy - kojingharangの日記  SRM 659 Div1 250 ApplesAndOrangesEasy - kojingharangの日記 のブックマークコメント

  • GarthがN個のりんごかオレンジをある順序で食べた。そのうちいくつかのリンゴに関しては食べた番目が与えられる。
  • 連続する K 個の中で K/2 以下のりんごしか食べてない場合、りんごの最大個数を求めよ。
  • 2≦K≦N≦2000
  • dp? いや最後の K 個のパターンをキーにするにしては K が大きすぎる
  • 左から置けるとこに貪欲に置いてだめな理由もなさそうだ
  • おけるところをどうやって覚えておくか...
  • 直近 K 個の和を計算しておいて、それを配ってmaxを取っておいたものが K/2 より小さければ置けそうだ
  • めっちゃはまる
  • 終了間際 あれこれN^3だだめだ
  • (あとで)
  • 冷静に考えると置けるかの判定は K 個の sum を見て良くて、置いた時の sum の更新も K 回、全体で O(N^2) にすればよかったのだ
  • 置けるかチェック O(1) 更新 O(N^2) にしてしまっていた。
  • それか BIT を使って置けるかの判定にO(NlogN)、更新にO(logN)でもいい。
  • うむー全然だめだ。
  • accepted in practice
class ApplesAndOrangesEasy {
	public:
	int maximumApples(int N, int K, vector <int> info) {
		VI w(N), sum(N); // sum of [i-K+1, i]
		REP(i, info.size()) w[info[i]-1]=1;
		REP(i, N) RANGE(j, max(0, i-K+1), i+1) sum[i]+=w[j];
		ll ans=info.size();
		REP(i, N) if(!w[i]) {
			bool ok=true;
			RANGE(j, i, min(N, i+K)) if(sum[j]>=K/2) ok=false;
			if(!ok) continue;
			ans++;
			RANGE(j, i, min(N, i+K)) sum[j]++;
		}
		return ans;
	}
};

2015-05-05

Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった)

18:27 |  Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった) - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった) - kojingharangの日記  Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった) - kojingharangの日記 のブックマークコメント

  • シカとヒトN人が単位円上を1方向に歩く。シカのスタート時のヒトの初期位置と周期(定速で周る)が与えられる。
  • シカは任意の正の速度で移動できるとき、シカが1周するまでにすれ違うヒトの最少人数を求めよ。
  • 周期≦10^9 +α
  • Small1: N≦2 Small2: N≦10 Large: N≦500000
  • Small1 だけ。
  • 各ヒトに対して、シカがすれ違わずにゴールできる時刻の範囲が決まる。
  • 具体的には、シカのスタート後、そのヒトがシカのスタート地点を1回通過する時刻〜2回通過する時刻まで。
  • ヒト2人に対するその範囲の共通部分があれば 0 人にできる。共通部分がなければ最低 1 人とすれ違う必要がある。
  • Small2 以降は謎。時刻を決め打ちして云々的な?
  • Small1: Accepted
int main() {
	int test_cases;
	cin>>test_cases;
	ll N, D, H, M;
	string s;
	REP(ttt, test_cases) {
		cin>>N;
		vector<PII> w;
		REP(i, N) {
			cin>>D>>H>>M;
			REP(j, H) w.PB(MP(M+j, D));
		}
		sort(ALL(w));
		ll ft = w[0].first * (360 + 360-w[0].second);
		ll st = w[1].first * (360-w[1].second);
		ll ans = st>=ft ? 1 : 0;
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

(追記)

  • Large も基本的にヒト毎にすれ違い回数は独立に足せることを利用する。
  • 各ヒトについてすれ違い回数が 0, 1, 2, ... になるような時刻の区間が定まるので、それらをソートしておいて、すれ違い回数が変化するとこで変化させていく。
  • ...書いたが WA がとれないので SnapDragon さんのを動かしたりするぢっと見たりする
  • そうだ -1, +1 おわり ではなく -1, +1, +1, ... とどんどん増えていくのだ
  • まとめると
  • すれ違い回数の初期値は t=0 でゴールするときなので全員分
  • まだ考慮していない変化データとその時刻を priority_queue で管理して、変化分を足し込んでいく。
  • 見たら次周のために +1 なデータを push
  • すれ違い回数はいずれ単調増加になるので、人数を超えたあたりで適当に終了。念のため人数*2にしとく
  • はまりどころ
  • push の前で top を見てた
  • -1 が人数分出るまでループを回すと -1 が長い周期になっててループが10^9回くらいになる可能性があるのですれ違い回数で打ち切る必要がある
  • Small1, Small2, Large: Accepted in practice
int main() {
	int test_cases;
	cin>>test_cases;
	ll N, D, H, M;
	string s;
	REP(ttt, test_cases) {
		cin>>N;
		priority_queue<pair<ll, pair<ll, ll>>> q;
		ll all = 0;
		REP(i, N) {
			cin>>D>>H>>M;
			REP(j, H) q.push(MP(-(M+j)*(360-D), MP(-1, (M+j)*360)));
			all+=H;
		}

		ll ans = 1LL<<60;
		ll cur=all;
		while(q.size() && cur < all*2) {
			ll t = -q.top().first;
			ll dn = q.top().second.first;
			ll dur = q.top().second.second;
			q.pop();
			cur+=dn;
			q.push(MP(-(t+dur), MP(1, dur)));
			if(t != -q.top().first) {
				ans = min(ans, cur);
			}
		}
		ans = min(ans, cur);
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

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;
	}
};
|