Hatena::Grouptopcoder

hogloid @ TopCoder

|

2011-05-20

TCO Algorithm Qual Round2

16:13

一昨日に続いて出ました。

夜8時!朝SRMの次に素晴らしい時間です

Easy

やるだけっぽいなー 両端からやってけば-1には成り得ない

count関数でエラー出たりちょっと面倒な実装したりして遅くなる。 221.24 pt

Medium

 -1じゃないときは探索でよさげ

打ち切る時間もKとCの最小公倍数*マスの数でいいとおも

ということでNをマスの数とするとO(N*N*K*C) のアルゴリズムでゴリゴリ書く

最初の時間を間違えたりで安定の遅実装。 346.98 pt

hard

難しいなー √Nのアルゴリズムとか探したけど見つからない

1~Nまでで考えると、最初は3割近くてだんだん少しずつ減っていく・・・ってのは分かったけどそこまで。

//25分もあったんだからなにか思いつけよ・・・

終わり

チャレンジも安定のチキン。

Systest通ったけどRating落ちるかなーとか思ってたが意外とMedium落ちてる人が多くて上昇。

Rating: 1616->1677

半月コーダーまでの道は長そうです

次からは夜1時と地獄時間なので出るかどうかは分かりません・・・

2011-05-18

SRM 504.5

16:24

出てました。夜0時と厳しい時間帯です。

始まる前

なんか昼寝に失敗するし直前の仮眠もしっぱいするしこりゃダメだなムード

1時間ぐらい前にRegisterしてコーヒーとか飲んで無理やり目を覚ます

Div1easyを1問解こうとするがWA地獄。 始まる少し前にようやく解けた

でもせっかくregisterしたので出る。

Coding Phase

Easy

16:24

まず読む。ねむい

最後の数が問題なんだから10とか100がいくつどこについても同じだな・・・

実装方法に迷う。 とりあえずn以下の最後の数が4か7の数から始めてだんだん小さくしていって

差を4と7だけで表せてかつ表す数が今までのより少ないとき更新・・・をやっていく

あれ、でもこれいつごろやめればいいんだ?一つできてもそれより小さいのがあった、ってのもあり気

とりあえず100回ぐらい回せばおkじゃね?

特に反例も見つからなかったのでSubmit. 172.61pt

Medium

16:24

なにこれ 普通にやってったら間に合わない

すべての数が同じならあとは平均的に足すだけだから・・・

とりあえずすべての数がおなじになるまでシュミレート。

(long longのオーバーフローとかでTLEかと勘違い accumulateをintで計算してたりとかで時間がかかる)

あ、普通にこれでいいみたいだ

でも10^18*47>long long int max じゃね・・・?

でもそんなテストケースないだろ→でもチャレンジされたらどうしようもない

じゃあ念のため余り求めつつうねうねやろう

Submit.306.53pt

Hard

16:24

なんか難しくなさげ。でも集中力の限界

最初mを無視して計算しちゃう その後適当に係数かければ通るかな、って思ってたけどSample通らない

時間切れ

その後

なんかコード超汚いし通る気がしない

3完率高いなーすごいなーあこがれちゃうなー

あ、2問両方通った

479.14 Mediumを本番で通せたのは嬉しい

Rating 1480->1616 黄色コーダー復帰

でも夜は集中できないし眠いし体調悪くなるしでいいことないです。もう出たくない(ぉ

コードは自分でも読めないぐらい汚いので見せられません><

2011-05-04

Member SRM 505 Div1

10:44

出ました。 昼型人間にやさしい時間です しおしおたさんと同じ部屋でした

黄色コーダー維持を目指して頑張ったつもりですが結果から言うと惨敗でした


Easy:

やばいこんなのEasyじゃない、英語で10分ぐらいかかる。

とりあえず同じ行・列が求まってればその比が求まるから・・・

X座標・Y座標で「別々に」UnionFindを作ってみる


んでこれからどうするんだ・・・?

分からない。Medium見る。

Medium:

数ゲー とりあえず全部試すコードを書いて規則をつかもうとする

Dの半分以下は含まれないな・・・

んでそれからは・・?と20分ぐらい考えるも分からず

もいちどEasyを考えるも結局分からず


Challange:

あ、UnionFind使うのはいいけどXとY一緒にやるのか・・・


0点でRating 1539->1490

早くも青コーダー落ち。高校生なのに青なんて・・・

次は必ず浮上します!!

Easy解きなおし

UnionFindやるだけ

struct uf{
	vi rank,p;
	uf(int n){
		rank.resize(n,1);p.resize(n,-1);
	}
	int root(int a){
		if(p[a]==-1) return a;
		return p[a]=root(p[a]);
	}
	bool same(int a,int b){
		return root(a)==root(b);
	}
	void unite(int a,int b){
		a=root(a);b=root(b);
		if(a==b) return;
		if(rank[a]>rank[b])
			p[b]=a;
		else{
			p[a]=b;
			if(rank[a]==rank[b])
				++rank[b];
		}
	}
};
class RectangleArea {
public:
	int minimumQueries(vector <string> known) {
		uf u(known.size()+known[0].size());
		REP(i,known.size()){
			REP(j,known[i].size()){
				if(known[i][j]=='N') continue;
				u.unite(i,j+known.size());
			}
		}
		int cnt=0;
		REP(i,known.size()+known[0].size()){
			if(u.root(i)==i) ++cnt;
		}
		return cnt-1;

	}
};

2011-04-08

SRM 502

12:25

出ました。

初のDiv1なので気を引き締めたつもりです。


Room:

日本人が一人しかいなくて悲しい気持ちになれた RedCoderが1人だけだったのはラッキー


Easy:

Easyです。くじの当たる確率を求めます。

	public:
	double find(vector <string> goodSuffixes) {
		vs g=goodSuffixes;
		REP(i,g.size()){
			if(g[i]=="") continue;
			REP(j,g.size()){
				if(i==j || g[j]=="" || g[i].size()>g[j].size()) continue;
				if(g[j].substr(g[j].size()-g[i].size(),string::npos)== g[i]) g[j]="";
			}
		}
		double res=0;
		REP(i,g.size()){
			if(g[i]=="") continue;
			res+=pow(0.1,(double)g[i].size());
		}
		return res;

	}

STLゲー、かと思って書きましたがSTL使って書いてる人は部屋で僕だけでした。

そのためChallangeでも何やってるのかよくわかんなかったです。

235.80点


Medium:

コンテストでの得点を最大化します。

DPなのは分かってナップザックにしようと思いましたがどうソートするかで悩み

結局requiredTimeの大きい順にやってみましたがダメでした


Hard:

難しい 無理ゲーにしか見えない


Challange:

人のコード見る時点で苦手。

僕のMediumは落とされました。


というわけで今回もEasyのみの235.80点

Rating 1328->1539

黄色コーダーになりました。

次は黄色コーダー維持目指して頑張ります!


Medium解きました

ir5さんのきゅうりさんへのリプライ・nai__さんの僕へのリプライを参考にしました

問題1を解いてから問題2を解くときにマイナスされてしまう得点は、pointsPerMinuteをpp、requiredTimeをrtとおくと、

pp[1]*rt[1]+pp[2]*rt[1]+pp[2]*rt[2]

問題2を解いてから問題1を解くときは、

pp[2]*rt[2]+pp[1]*rt[2]+pp[1]*rt[1]

この差は pp[2]*rt[1]-pp[1]*rt[2]

よって、問題1を先に解いた法がいい、つまり問題2を先にといたことにするとマイナスされてしまう得点が大きくなるときは

pp[2]*rt[1]-pp[1]*rt[2]>0

⇔pp[1]/rt[1]<pp[2]/rt[2]</ppp>

あとはナップザックするだけ

struct state{
	int mp,pp,rt;
	state(int sm=0,int sp=0,int sr=0){
		mp=sm;pp=sp;rt=sr;
	}
	bool operator <(const state &val)const{//形だけの演算子
		return false;
	}
};
class TheProgrammingContestDivOne {
	public:
	int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
		vi mpp=maxPoints,pp=pointsPerMinute,rt=requiredTime;
		vector<pair<double,state> > p(mpp.size());
		REP(i,p.size()){
			p[i].sc=state(mpp[i],pp[i],rt[i]);
			p[i].fr=(double)pp[i]/rt[i];
		}
		sort(ALL(p),greater<pair<double,state> >());
		vvi dp(p.size()+1,vi(T+1,-INF));
		dp[0][0]=0;
		REP(i,p.size()){
			REP(j,T+1){
				if(dp[i][j]==-INF) continue;
				dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
				if(j+p[i].sc.rt<=T && p[i].sc.mp-(lint)(j+p[i].sc.rt)*p[i].sc.pp>=0)
					dp[i+1][j+p[i].sc.rt]=max(dp[i+1][j+p[i].sc.rt],dp[i][j]+p[i].sc.mp-(j+p[i].sc.rt)*p[i].sc.pp);
			}
		}
		int res=0;
		REP(i,T+1){
			res=max(res,dp[p.size()][i]);
		}
		return res;
	}
}

FloraFlora2011/07/22 16:12I'm so glad that the itenrent allows free info like this!

fstftwikfstftwik2011/07/22 22:46chU2Tj <a href="http://edaydfngelea.com/">edaydfngelea</a>

nmzmgxbhnmzmgxbh2011/07/23 22:15jzNHLR , [url=http://rhxthhlsjtkq.com/]rhxthhlsjtkq[/url], [link=http://bgffjnxgpvvb.com/]bgffjnxgpvvb[/link], http://ofpiuyjasald.com/

drftbexbxmdrftbexbxm2011/07/24 21:337C6ZN1 <a href="http://aetmsnkjaupf.com/">aetmsnkjaupf</a>

mwfynadqvdmwfynadqvd2011/07/26 00:39aSqDzm , [url=http://rooxnovxrjda.com/]rooxnovxrjda[/url], [link=http://pmbchocofzfw.com/]pmbchocofzfw[/link], http://qmfmxjddxtml.com/

2011-04-01

SRM501 Div2 Hard

18:35

折角解いたのでペタッと

これから毎回こんなことするのかといわれるとするかどうかは分かりませんがお許しください

id:JAPLJ さんの方に解説が書いてあるのでまずはそちらを

ちなみに一工夫してない方の解法です。

dpvectorでとったらstd::bad_allocになったのでグローバルで生配列にしてます

int dp[41][1601][41][2];
class FoxAverageSequence {
	public:
	static const int mod=1000000007;
	int theCount(vector <int> seq) {
		memset(dp,0,sizeof(dp));
		dp[0][0][0][0]=1;
		REP(ind,seq.size()+1){
			if(ind<1) continue;
			REP(sum,1601){
				REP(bef,41){
					REP(l,2){
						if(dp[ind-1][sum][bef][l]==0) continue;
						double div=(double)sum/(ind-1);
						if(seq[ind-1]==-1){
						if(l){
							REPN(i,41,bef){
								if(i>div) break;
								dp[ind][sum+i][i][0]+=dp[ind-1][sum][bef][l];
								dp[ind][sum+i][i][0]%=mod;
							}
						}else{
							REP(i,41){
								if(i>div) break;
								if(i<bef){
									dp[ind][sum+i][i][1]+=dp[ind-1][sum][bef][l];
									dp[ind][sum+i][i][1]%=mod;
								}
								else {
									dp[ind][sum+i][i][0]+=dp[ind-1][sum][bef][l];
									dp[ind][sum+i][i][0]%=mod;
								}
							}
						}
						}else{
							if(seq[ind-1]>div) continue;
							if(l){
								if(bef>seq[ind-1]) continue;
								dp[ind][sum+seq[ind-1]][seq[ind-1]][0]+=dp[ind-1][sum][bef][l];
								dp[ind][sum+seq[ind-1]][seq[ind-1]][0]%=mod;
							}else{
								if(bef>seq[ind-1]){
									dp[ind][sum+seq[ind-1]][seq[ind-1]][1]+=dp[ind-1][sum][bef][l];
									dp[ind][sum+seq[ind-1]][seq[ind-1]][1]%=mod;
								}else{
									dp[ind][sum+seq[ind-1]][seq[ind-1]][0]+=dp[ind-1][sum][bef][l];
									dp[ind][sum+seq[ind-1]][seq[ind-1]][0]%=mod;
								}

							}
						}
					}
				}
			}
		}
		int res=0;
		REP(bef,41){
			REP(sum,1601){
				REP(l,2){
					res+=dp[seq.size()][sum][bef][l];
					res%=mod;
				}
			}
		}
		return res;	
	}
}
|