Hatena::Grouptopcoder

hogloid @ TopCoder

2012-11-02

Bayan 2012-2013 Elimination Round

| 13:27

CFで開催されていました

20位以内でイランに招待されるのでちょっと緊張

A-Old Peykan

難易度順に並んでないことは知らされているので、短い問題文の問題から読む。

しかしどれも難しそうor問題文長いor面倒そう

そうこうしているうちにAが解かれ始める。Aが簡単なのかよ・・・・

読解にだいぶ苦しむ。蟻本のガソリンスタンドの問題だが、一つのガソリンスタンドからいくらでも給油できる、というだけ。

17分でAC.ACMルールなのに1問目で時間を食い死にたくなる

C-Mirror box

何人か解いてたのでやってみる。長方形があって、左の辺の点からレーザービームを打ち、上下の辺の鏡に反射させながら右の辺の点にぶつける

鏡->反射を展開して適当に、の鉄則

実装少し面倒だが頑張って書く

問題文のNoteの通りにならない・・・・が、バグどう見ても見つからないので出す。何故かAC.

!!!問題文の図・Noteが大嘘!!!

ACMルールなのに2問目で時間を食い死にたくなる。あと図が嘘ついてるコンテストは初めてだった

G-Challenging Balloons

バグ入りコード書いてる人いるからチャレンジケース書け。

怖いけどどう見てもこっちのほうが早く解ける問題だった。

ちなみに、この問題でWAがカウントされないバグとかがあったらしい。

F-Race

IOIの問題を思い出す

全然関係なかった。道・交差点があり、移動するのにかかる時間が決まっている。

始点・通る交差点の順番・終点が与えられて、最短路を取るよう動いたときk分経ったときどこにいるか

最短路って時間なのか通るグリッドなのか分からない、clar出すがno comments(絶望)

問題文とかから考えると、1回の交差点から交差点へ移動は道を使って一直線に必ず進める、と言いたいらしい。こんなの気づかないでしょ・・・

そうなると1回の移動のコストを調べて、合計がkを超えたところを普通に見つければよい

3WAだしてAC。この時21位。



終了

結局これ以上解けず。


最終的に結構抜かれて33位。イラン行けなかった・・・・

コンテスト自体は、全然解けなかった難しい問題が面白そうでよかったけど、問題文とかいろいろ不備多かった気がする。


Rating:2196->2260

ついにGrandmasterになっていた

CFは始めたのも1年前とみていいし、TCよりレートすぐ動くので赤になれてしまった

早く国際オンサイト出られるようになりたい(IOI以外で)

2012-05-06

X Programming Olympiads in Murcia (Spain) 2012

17:05

なんかUvaでコンテストやってたので出てみた。

解けた問題で、わりとむずいかしいE,Gのみ


E. Oh, my trees! (UVa 12458)

二分探索木から辺が消えたものが与えられる。

すなわち、各頂点に割り当てられた数字とその高さがわかっている。

このとき、元の二分探索木を復元せよ。


G. Careful teacher (UVa 12460)

20000 文字以下からなる辞書が与えられる。

二つの文字列 s, t が与えられる。

s の一文字を変化させることを繰り返して t に一致させられるか判定せよ。

ただし、変化後の文字列は辞書に入っていないといけない。

(fura2さんの記事から拝借しました)


Eは、オーダーがよくわからないけど、

それぞれのレベルでキーの大きさでノードをソートし、

あるノードの子孫に存在する可能性のある最も小さい値、最も大きい値

が分かっていれば、左の子はどれか、右の子はどれかが分かる。

これを再帰で表現すればおわり。根では最も小さい値を-INF,最も大きい値をINFにする

たぶんO(VlogV)

using namespace std;
static const int INF =INT_MAX-13;
typedef pair<int,int> pi;
int h;
vector<vector<int> > node;
char tmp[1000005];
stringstream ss;
int when;
map<int,int> conv;
int rev[1000005];
pi res[1000005];
void in(int lev){
	ss.clear();ss.str("");
	ss<<tmp;
	int a;
	while(ss>>a){
		rev[when]=a;
		conv[a]=when++;
		node[lev].push_back(a);
	}
};
void rec(int key,int lev,int lb,int ub){
	int nlb=lower_bound(node[lev+1].begin(),node[lev+1].end(),lb)-node[lev+1].begin(),
		nub=upper_bound(node[lev+1].begin(),node[lev+1].end(),ub)-node[lev+1].begin();
	if(nub-nlb==2){
		res[conv[key]]=make_pair(node[lev+1][nlb],node[lev+1][nlb+1]);
		rec(node[lev+1][nlb],lev+1,lb,key-1);
		rec(node[lev+1][nlb+1],lev+1,key+1,ub);
	}else if(nub-nlb==1){
		if(node[lev+1][nlb]<key){
			res[conv[key]]=make_pair(node[lev+1][nlb],INF);
			rec(node[lev+1][nlb],lev+1,lb,key-1);
		}else{
			res[conv[key]]=make_pair(INF,node[lev+1][nlb]);
			rec(node[lev+1][nlb],lev+1,key+1,ub);
		}
	}else{
		res[conv[key]]=make_pair(INF,INF);
	}
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		when=0;conv.clear();

		scanf("%d",&h);getchar();
		node.clear();node.resize(h+1);
		for(int i=0;i<h;++i){
			gets(tmp);
			in(i);
			sort(node[i].begin(),node[i].end());
		}
		rec(node[0][0],0,INT_MIN,INT_MAX);
		for(int i=0;i<when;++i){
			printf("%d:",rev[i]);
			if(res[i].first!=INF) printf("%d",res[i].first);
			putchar('-');
			if(res[i].second!=INF) printf("%d",res[i].second);
			putchar('\n');
		}
	}



	return 0;
}

Gも、文字列の長さとかクエリ数がよく分かんなくて困ったけど、

文字列の長さが辞書であるような常識的な長さと仮定すると、

文字列の長さでソートし、

それぞれの長さの文字列の集合について、

文字のk番目を無視して辞書順ソートする。

これで、文字のk番目を無視すると等しい文字列かどうかが高速に分かる。

k番目を無視したとき等しいなら、一文字しか違わなく、1文字変えてジャンプできるので、union-findか何かでマージする。

O(length^2 * N log N)ぐらい?

using namespace std;
static const int INF =500000000;
typedef long long int lint;
typedef pair<int,int> pi;
pair<string,int> strs[20005];
int deg[20005];
struct uf{
	int par[20005];
	uf(){
		memset(par,-1,sizeof(par));
	}
	int root(int a){
		if(par[a]==-1) return a;
		return par[a]=root(par[a]);
	}
	void unite(int a,int b){
		a=root(a);b=root(b);
		if(a==b) return;
		par[a]=b;
	}
	bool same(int a,int b){
		return root(a)==root(b);
	}
};
uf u;
bool cmp(const pair<string,int>& s,const pair<string,int>& s2){
	return s.first.size()<s2.first.size();
}
int except;
int compare(const string& s,const string& s2){
	for(int i=0;i<s.size();++i){
		if(i==except) continue;
		if(s[i]<s2[i]) return -1;
		if(s[i]>s2[i]) return 1;
	}
	return 0;
}
bool cmp2(const pair<string,int>& s,const pair<string,int>& s2){
	if(compare(s.first,s2.first)==-1) return true;
	return false;
}

int main(){
	string s;
	int n=0;
	while(getline(cin,s)){
		if(s=="--") break;
		strs[n]=make_pair(s,n);
		++n;
	}
	sort(strs,strs+n,cmp);
	for(int i=0;i<n;++i){
		int j=i,len=strs[i].first.size();
		while(j<n && strs[j].first.size()==len) ++j;
		if(j-i>1){
			for(int k=0;k<len;++k){
				except=k;
				sort(strs+i,strs+j,cmp2);
				for(int l=i;l<j;++l){
					int i2=l;
					while(i2<j && compare(strs[l].first,strs[i2].first)==0){
						u.unite(strs[l].second,strs[i2].second);
						++i2;
					}
					l=i2-1;
				}
			}
		}
		i=j-1;
	}
	sort(strs,strs+n);
	string a,b;
	stringstream ss;
	while(getline(cin,s)){
		int piv;
		ss.clear();ss.str("");
		ss<<s;
		ss>>a>>b;
		int A=lower_bound(strs,strs+n,make_pair(a,-1))->second,B=lower_bound(strs,strs+n,make_pair(b,-1))->second;
		if(u.same(A,B)) puts("Yes");
		else puts("No");
	}


	return 0;
}

trie木使えば、おそらくlog消える


結構面白い問題だったけど、やっぱり部分点ないのに最大ケース分からないというのはつらい

2012-04-05

VKCup 2012 wild-card round 2

15:28

マラソンマッチ風でした。round2寝落ち勢です。

たぶん17位で通過です。

実際にコンテストでマラソン参加するのは初めてでした

問題は、大体だと、w*hの枠が与えられて、長方形がN個与えられて、長方形はそのままor90度回転させて、0.1倍から2.0倍に大きさを変えて、マップ内に完全にはいって、

他の長方形と重ならないなら置ける(おかなくてもよい)

N<=100で、細長いマップの時はそれと似たような長方形が多い!!重要!!

回転させていない長方形と、回転させた長方形が接する長さを最大化せよ。回転させていないものどうし、回転させたもの同士が接するとその長さだけマイナス。

戦略

  • 1.横にして使うものと、縦にして使うもので分ける。横・縦の比が基準で、横に細長いのを作る。マップによって偏りがあるので、だんだん多いほうから少ないほうに移してゆく。
  • 2.マップが縦長になるよう必要ならば回転させて、何列かに分けて、列の大きさを決める。横に細長くて、列にうまくフィットするものから詰めまくる。細長いのは面積辺りの接する長さが多いので。
  • 3.あとは、同じ列では、幅が長いのから順に置いたほうがよいので、1列置き終わったらソートする。
  • 4.最後に、微妙に余ったスペースに余り物を詰めまくる。

細かい改善としては

  • 縦に細長い(ダメな)長方形は、縦の長さが同じだったらマージ。これをすると余り物が使い物になる(ただ同じなものはなかなかない、lcmをとるなども考えたがサイズ変更が制限される上実装が面倒)
  • 4番目の、最後に詰めまくるのが意外とスコアが大きいので、列の幅に完全にフィットするものは本来スコアが高かったが、列の幅*0.85ぐらいにフィットするものは完全にフィットするのと同等の評価にした
  • あとは各種パラメータを調整して、Run
  • 4番目の改善は実際に置いてみないと分からないので、パラメータごとに答えを出してもっともよいものを選ぶ、といった感じ

感想としては

  • 思いついたもののほとんど効果がない・実は勘違い、ということがかなりあって、実装する前にもっともっと考察すべきだなぁ、と感じた。
  • 時間が長いからといって(長いからこそ)すぐ実装するのではなく、それで本当によいのか考えるべきだと思った
  • まあ、初参加にしては、通過できたのでよかったぁ~と安心
  • 1日目1位になったりして、途中だいぶだらけていて、終盤1日で10位下がったのにはビックリした。巻き返し激しすぎw
  • 実は最後のほうのpretestでは26位で、だいぶ落ちたなーと思っていた。細長いケースがpretestでは少なく、それでやや助かった面もある(長方形のマージは細長いとき役に立つ)
  • コードがかなり長くなるので、こういうときは高機能なIDEもいいかもしれないな~と思いつつも、最近VisualStudio触ってないので使い方が分からない

↓適当なマップの画像

f:id:hogloid:20120405162940p:image

("phidnight"をジェネレータに投げると出るマップ)


f:id:hogloid:20120405162941p:image

("383129"をジェネレータに投げると出るマップ)

2012-03-25

CodeForces 113 Div2 問題B

19:15

JOI合宿の競技が終わったので、夜更かしして出てました。

Bの解法がちょっと面白かったので紹介します

Bの概要は、N頂点からなる凸多角形AとM頂点からなる交差しない多角形Bが与えられているので、BがAの完全に内側にあるかどうか判定。N<=10^5、M<=2*10^4

A,Bは時計回り順に並んでいる。どの3頂点も一直線上にない

AとBをごっちゃにして凸包して、凸包にある頂点に一つでもBの頂点があるなら申し訳ないがNGといった感じでやればあっさりOK

ですが、他の人々ズは、Bの点について、Aの内側でないものがあるかどうかすべて判定しているひとが多かったらしいです。一つの点についてはO(logN)でできるのでそれができればOKなのですが、

ライブラリが豊富すぎたりこれができるということを知りすぎているとかえってシンプルな解法から遠ざけられてしまうので怖いですね。柔軟な発想力大切


#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<deque>
#define REP(i,m) for(int i=0;i<(int)m;++i)
#define fr first
#define sc second
#define REPN(i,m,a) for(int i=a;i<(int)m;++i)
using namespace std;
typedef pair<int,int> pi;
#include<complex>
typedef long long int lint;
typedef complex<lint> P;
pair<P,int> p[200005];
int n,m;
bool cmp(const pair<P,int>& a,const pair<P,int>& b){
	if(a.fr.real()==b.fr.real()) return a.fr.imag()<b.fr.imag();
	return a.fr.real()<b.fr.real();
}
lint cross(P a,P b){
	return a.real()*b.imag()-a.imag()*b.real();
}
int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  return 0;
}
int main(){
	scanf("%d",&n);
	REP(i,n){
		cin>>p[i].fr.real()>>p[i].fr.imag();
		p[i].sc=1;
	}
	scanf("%d",&m);
	REP(i,m){
		cin>>p[i+n].fr.real()>>p[i+n].fr.imag();
		p[i+n].sc=0;
	}
	
	int n2=n+m;
	sort(p,p+n2,cmp);
	
  vector<pair<P,int> > ch(2*n2);
  int k=0;
  for (int i = 0; i < n2; ch[k++] = p[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2].fr, ch[k-1].fr, p[i].fr) < 0) --k;
  for (int i = n2-2, t = k+1; i >= 0; ch[k++] = p[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2].fr, ch[k-1].fr, p[i].fr) < 0) --k;
  ch.resize(k-1);
  REP(i,ch.size()){
		if(ch[i].sc==0){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}

2011-06-09

SRM 509

19:49

大失敗

やっぱりTCは怖いですね

Rating:1677->1461

またも青コーダー・・・・


ちなみに、最近SRMの感想ばっか書くようになってるので、(&需要ないと思うし書くのもやや面倒なので)これからは縮小運営の予定です