Hatena::Grouptopcoder

zerokugi's contest memo

2014-12-31SRM643 Div1

oox +9/-1 1st

f:id:zerokugi:20141231225916p:image

部屋のMedが10個全部落ちて(1つ落とし逃した)+425点

レッドが他に二人いたのにMedのチャレンジを独占できたのはほんとに運が良かった(Easyもチャレンジ祭りだったからかもしれない)

部屋運が良かったのとHardが激ムズだったおかげで奇跡的に1位になることができた

2014-10-23ICPC2014 東京地区大会 参加記

ICPC2014 東京地区大会に参加しました

メンバーは @logicmachine @zerokugi @n_vip の3人です

結果は ABCDEFG の7完で全体6位、大学別順位5位でした

@logicmachine さんによる参加記も合わせてどうぞ http://d.hatena.ne.jp/logicmachine/20141020

基本的な方針はいつもどおり @zerokugi と @n_vip君 が問題を読んで解法を考える → @logicmachineさんに伝えて実装してもらう

という感じ

とりあえず最初は

  • A: @logicmachine
  • B: @n_vip
  • C: @zerokugi

から読むと打ち合わせてスタート

開始(00:00)

@logicmachine さんが環境設定をしてる間にAを読む(なぜかいきなり予定と違うことをやりだす)

そのまま概要と解法をパパっと伝えてBが大丈夫そうなことを確認しつつCを読む

A問題AC(00:08)
B問題AC(00:16)

B問題は俺の知らないうちに通ってました

Cはちょっと悩んだけど区間が重なってない時だけ引き返すようにしたら良さそう、って感じで伝える

すると依存関係が折り重なってる時にうまくいかない事を指摘される

あれーこれ難しくないかと思ってたら c_i < d_i という制約を見逃していたことに気づく(あまりにも杜撰すぎた)

C問題ならこのぐらいだろうという勝手な思い込みで解法を詰めていなかったので反省

C問題AC(00:30)

@n_vip君からDの様子を聞くと,式変形して解く感じの問題らしいのでとりあえずもう少し任せておくことに

D以降は適当に読んでいく予定だったので読みやすそうなGを読んでみる

カッコの平衡を取る問題だったのでとりあえず折れ線を書いてみたところ,一番左にある閉じカッコと、フリップした所に一番近い0を取ってこれれば解けそう

そう伝えると遅延セグツリーで解けると言われたのでとりあえず写経しといてもらい式を整理する

あらかた式を整理できたのでぼちぼちACが増えていたFを読んでみるとクラスカルしまくるだけだと判明

写経中のGを置いておいてFから解いてもらうことに

2回ほどミスでペナルティを出してしまったものの無事AC

F問題AC(01:03 +2)

Dが難航してたようなので先にEの読解を@n_vip君にお願いしつつIJらへんを読んでおく

するとGが書けたけどサンプルが通らないらしいのでコードを読んで,想定してたのと違う部分をいくつか指摘する

サンプルが一致,そのまま提出するもWA

いろいろケースを試した結果、一番近い0を探して来るのではなく一番近い1を探してくる必要があることに気づく

SegTreeの実装を変えてそのまま求めるのは難しいらしいので二分探索で求める方法を提案

O(nlog^2n)になってTLEがする恐れがあるが,TLEしたらSegTreeをもぐりながら二分探索する方法に変えればいいやーということでとりあえず提出 すると無事AC

G問題AC(01:53 +1)
E問題AC(02:31)

Eもほとんど関与してません DPっぽく状態まとめて探索すれば求まるんじゃない的なことを言った気がする

Dは聞いたところバウンド回数を固定して建物を全て超えられるギリギリの角度を二分探索で求めれば解けそう

そこらへんを伝えて実装してもらう

角度で二分探索するうまい方法が考えられなかったけど出来上がったソースを見るとvyで二分探索していてなるほどなーと思った

サンプル2だけ合わないので適当に図を書いて考えてみると答えより下を通ってるらしい事が分かる

よく考えたら45度が一番効率が良いことに気がついて二分探索の下限を45度にしてもらうとサンプルが合ったので提出してAC

D問題AC(02:59)

なんとか必須っぽい7問を解いて一安心

確かこの時点で全体4位国内2位(かなりテンション上がった)

あと10分耐えればColorful Jumbo Chickenに7完されてもペナルティで勝てる…と思ってたら2分間に合わず追いぬかれてしまう

気を取り直してとりあえず残り4問を全員共有して方針を考えることに

  • H: 実装重い幾何 @logicmachine さん曰く頑張ればできるらしい
  • I: DPっぽいゲーム探索 できそうな気はするがうまい方針が見当たらない
  • J: なんか三次元幾何に落とし込めそうな問題 凸包取ったり平面で切ったりするのかなーと思うもうまく落とし込めず
  • K: あまり考察してないけど見るからにヤバそうだしとりあえず放置しておくが吉?

HIJ をそれぞれ一人ずつ担当することに決定

おなか空いたので休憩室に行きご飯を食べながらIを考える

dp[A or B][n][おいしさの総和] = min(必要な相手との栄養価の差)

というdpで解けそうだなーと思って紙上で再帰したりループしたりいろいろ試すもなぜかうまくいかない

もしかしてもっと複雑なことしないといけないのかなーとか若干諦め気味になる

ずっと悩んでたけど残り40分ごろであたらしい解法を思いつく

(http://topcoder.g.hatena.ne.jp/zerokugi/20141020)

方針は思いついたもののメモ化部分の実装をどうすればいいか迷う

この時ものすごい勢いでHを実装中の@logicmachine さんに変わる?と聞かれたもののH問題ACの芽を潰してPCを奪い取る勇気がなくて断ってしまう

その後残り20分ごろでHのコードが完成しサンプルを走らせるものの答えが合わず,デバッグも絶望的とのことだったので交代してIを書いてみることに

残り2分でとりあえず書き終わったもののサンプルでセグフォが出てデバッグが間に合わずに7完のまま終了・・・

コンテスト終了

Iは解法も実装の方針も間違っていなかったのでもうちょい時間があれば通せていたかもしれず、ものすごい後悔に襲われる

あと予定になかったとはいえ自分が実装する準備を何一つしてなかったのも問題だった

Trial Useでの練習とか自分用テンプレの印刷すらしてなかったのは論外

5時間コンテストになると流石にコーダー一人じゃ疲労がヤバいし、今後はもう少し自分が実装することも想定しておいた方がいいかもしれないなーと思った

個人としての課題はかなり残ったものの、チームとしてはとても良い結果を残せたのでそっちは満足です

イマイチ選抜ルールがわかっていないのですがとりあえずWF参加の可能性は高そうなので発表を期待してます

あと、台湾大会ではColorful Jumbo Chickenへのリベンジを目指してがんばりたいと思います

みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!

2014-10-20ACM-ICPC 2014 Asia Tokyo Regional I: Sweet War

I: Sweet War

問題

美味しさ  r_i と栄養価  s_i をパラメータに持つチョコレートがN個並んでいる

AliceとBriannaは先頭のチョコから交互に取っていくが,エネルギーを1以上持っている場合に限りパスすることができる

初めAliceとBriannaのエネルギーはA, Bであり,チョコを食べるとそのチョコが持つ栄養価の値だけエネルギーが増加する

AliceとBriannaはそれぞれ自分が食べたチョコのおいしさの総和を最大化したい.

二人が最適に行動した時のそれぞれが食べたチョコの美味しさの総和を求めよ

  •  1 < N < 150
  •  0 < A, B, r_i < 10^9
  •  0 < s_i
  •  \sum s_i < 150
解法

AとBが持つエネルギーは差だけ見て以下のように考えればよい

  • 自分のエネルギーが相手のエネルギーよりも同じか少ないならパス不可能(相手もパスをし続けて結局自分が食べることになるため)

こうすると2連続でパスが起きることがなくなる

これを使って貪欲に書くと以下のようなコードになる

int n, A, B;
ll r[200], s[200];
ll sum[200];

// i個目のチョコが先頭にあり
// playerのターンで
// playerの栄養価が相手よりも nut 多い時
// playerが取得できるi個目以降のチョコのおいしさの総和の最大値を返す
int dfs(int player, int i, ll nut){
	if(i == n) return 0;

	// eat
	int res = s[i] + sum[n] - sum[i+1] - dfs(!player, i+1, -(nut + r[i]));

	// pass
	if(nut > 0) res = max(res, dfs(player, i+1, (nut - r[i] - 1)));
	return res;
}

main(){
	ios::sync_with_stdio(false);
	cin >> n >> A >> B;
	REP(i, n){
		cin >> r[i] >> s[i];
		sum[i+1] = sum[i] + s[i];
	}
	int res = dfs(0, 0, A-B);
	cout << res << " " << sum[n] - res << endl;
	return 0;
}


このコードは O(2^n) かかるためTLEするのでこれをメモ化することを考える

単純に考えると memo[player][i][nut] というメモ化が考えられるが,

nutが -75*10^9~75*10^9 ぐらいまで値の範囲を持つのでメモ化できない

しかし,この関数の返り値は0~150までの値のみを取り,player, i を固定するとnutに比例して(広義)単調増加するため,

各player, iに対して返り値が変化する nut の値だけ調べておけば全てのnutに対して正しい値を返すことができる

なので最初に二分探索で変化点を求めておくことでメモ化を実現することができる

以下コード

const ll INF = 1ll<<40;
int n, A, B;
ll r[200], s[200];
ll sum[200];

int solve(int player, int i, ll nut);

// i個目のチョコが先頭にあり
// playerのターンで
// playerの栄養価が相手よりも nut 多い時
// i個目以降のチョコのplayerが取得できるおいしさの総和の最大値を返す
int dfs(int player, int i, ll nut){
	if(i == n) return 0;
	int res = s[i] + sum[n] - sum[i+1] - solve(!player, i+1, -(nut + r[i]));
	if(nut > 0) res = max(res, solve(player, i+1, (nut - r[i] - 1)));
	return res;
}

map<ll, int> memo[2][200];

void fillTable(int player, int i){
	map<ll, int> &tar = memo[player][i];
	int low = tar[-INF] = dfs(player, i, -INF/2);
	int hi = tar[INF] = dfs(player, i, INF/2)+1;
	for(int j=low+1;j<hi;j++){
		ll l=-INF, r = INF;
		while(l<r-1){
			ll med = (l+r)/2;
			if(dfs(player, i, med) < j) l = med;
			else r = med;
		}
		j = tar[r] = dfs(player, i, r);
	}
}

int solve(int player, int i, ll nut){
	if(i == n) return 0;
	if(memo[player][i].empty()) fillTable(player, i);
	auto it = (memo[player][i].upper_bound(nut));
	return (--it)->second;
}

main(){
	ios::sync_with_stdio(false);
	cin >> n >> A >> B;
	REP(i, n){
		cin >> r[i] >> s[i];
		sum[i+1] = sum[i] + s[i];
	}
	int res = solve(0, 0, A-B);
	cout << res << " " << sum[n] - res << endl;
	return 0;
}

本番中、最初はおいしさの総和を固定した時の最小の栄養価の差分を求めるDPを考えてたけど混乱してまとまらず残り40分程度でこのアプローチを思いつく.

残り15分でHが絶望的だったので交代し実装を始めるも間に合わずに終了という悔しい結果に.

戦略次第では通せてた可能性もあったのでなかなか悔しい

2014-09-19Codeforces Round #267 (Div. 2) E

E - Alex and Complicated Task

問題

数列が与えられるので以下の条件を満たす最長の部分列を作れ

・長さは4の倍数

・a[4k]==a[4k+2] && a[4k+1]==a[4k+3]

abab cdcd efef ghgh みたいな数列

解法

とりあえず先頭から見て行って1セット作れたら貪欲に作っていく

作れるかどうかの判定は

・なんらかの数字に挟まれてる区間を覚えておきながら,先頭から見て行く

・各数字について最後に出現した位置を覚えておく

・読み込んだ数字(y)の前回出現位置がなんらかの数字(x)に挟まれていたら x y x y が作れる

こんな感じ

0 1 0 0 3 3 0 0 5 5 5 5 0  ←その位置がなんの数字に挟まれてるか

1 2 1 3 4 4 3 5 6 7 8 9 5 4 ←入力の数列

→4の前回出現位置は3に挟まれてるので3434が作れる

挟まれてるフラグの更新はSegTree使って範囲に対してlognでセット、一点の値をlognで取得できるようにしてやる

x x x x みたいな同じ数字4つのパターンは別途検出してやる


class SegTree{
	typedef int SegT;
	private:
		vector<SegT> val;
		int n;
		
	public:
		SegTree(int size){
			n=1;
			while(n<size)n<<=1;
			val=vector<SegT>(2*n, 0);
		}
		//i 番目の要素を取得する
		SegT get(int i){
			SegT ret;
			i+=n-1;
			ret = val[i];
			while(i>0){
				i=(i-1)/2;
				ret = max(ret, val[i]);
			}
			return ret;
		}
		//[a, b) にxをセットする
		void set(int a,int b, SegT x,int k=0,int l=0,int r=-1){
			if(r==-1)r=n;
			if(r<=a||b<=l) return;
			if(a<=l&&r<=b){
				val[k] = x;
			}else{
				set(a,b,x,k*2+1,l,(l+r)/2);
				set(a,b,x,k*2+2,(l+r)/2,r);
			}
		}
};


int n;
main(){
	map<int, int> prev;
	map<int, int> cnt;
	scanf("%d", &n);
	SegTree seg(n+1);
	vi ans;
	int end = 1;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d", &x);
		cnt[x] ++;
		if(cnt[x] == 4){
			REP(j, 4) ans.push_back(x);
			prev.clear();
			cnt.clear();
		}else{
			if(!prev[x]) prev[x] = i;
			else{
				int t = seg.get(prev[x]);
				if(!t){
					seg.set(prev[x]+1, i, x);
					prev[x] = i;
				}else{
					REP(j, 2){
						ans.push_back(t);
						ans.push_back(x);
					}
					prev.clear();
					cnt.clear();
				}
			}
		}
	}
	printf("%d\n", ans.size());
	FOR(it, ans) printf("%d ", *it);
	return 0;
}


解法みんな結構バラバラだったから書いてみたけどすごい分かりにくい説明になってしまった

Segtreeクエリ部分はかなり適当にやってる(その点をカバーする区間のうち最大のものを返す)