はっぴぃ☆わぁるど

思考垂れ流す肥溜め

CODE_THANKS_FESTIVAL_2015体験記

　本番に弱いことに定評のある人だったので予選で死亡、おそらく繰り上がりぐらいで感謝祭のほうにでることになった(気がする)。

　目標はとりあえずページワン(20位以内)に載ることでした。

　2014の問題も解いて準備は万端ですね。

こんなかんじで会場に着く前からかなりヤバい（スマホは会場に落としたので無事回収されました。ありがとうございます。）

お昼ご飯もそこそこにコンテストの始まりです。

・A　日本語がわからないが適当にぽいする。AC

・B　日本語が難しい。setで殴る。AC

・C　lower_boundおしまい。AC

・D　ちょっと考える。自分が知ってる情報以外は、対象者以外が0or100が最高最低点なのでmax(0,hoge),min(100,poi)で終了。FAだったらしい。

・E　同じ文字は全部取り除かなきゃいけないのを勘違いしていた。ちょっと時間かかったがTに出てこない文字全部除いてそこからfindすればおしまい。

 

ここまでは順調でたしかこの段階で3位くらいだったと思う。

 

・F　考察は10分くらいで終わった。が実装でミスっていた。考察でミスったのかとドはまりして死亡。ACになったのは1.5hぐらい。順位は20位を下回る。

ちなみにこの川柳が賞に選ばれてAmazonのギフト券をもらった。感謝。

 

・G　もうこれ解くしか焼肉はねえなと思って、うんうん唸る。ダイクストラなのはわかってたけど、しらず。試しにHをみる。

 

・H　ぱっとO(R^3C^3)で通らねえ。累積和で和が求まるのはわかったが、そこからが続かない。残り時間も10分。座して死を待つ。

 

E,Fで速度が落ちてしまってクソ。特にFがさくっと解けてれば5位以内に入れたんじゃないかなあという感じなので大変残念なミス。う〜ん焼肉。結果は27位でした。

 

 

このあとは懇親会。DDRとか太鼓の達人とか川柳とか書道コーディングとか。スタンプラリー効果で缶バッチをゲット。chokudaiさんに蟻本にサインしてもらう(すいませんでした)

 

今回のまとめ：

色々(物理的にも)得るものが多かったのでコードサンクスフェスティバル

に圧倒的感謝です。 ありがとうございました。

最後に

 

Codeforces #322 Div.2 C

CFR_C

　今回は早めに4完して+4:-2Hackしたのでめちゃくちゃ得点が高い。やっぱり引っかかりやすいテストケースを用意してHackすると得点が高くなるなあという印象。
　そして今回初めてDiv.1にあがることができた。1555->1741(+186)

問題はこちら　Problem - C - Codeforces
　kでシミュレーションすればいいかなと思ったが明らかに計算量が多い。貪欲に10-a%10が小さいものから順に能力を上げればいいとわかる。全部にあげ終わった後(ex: 10 20 40 20 10 10...)は、どれに10点ずつふりあてても変わらない。ただし得点の上限は10nであることに注意。
　以上のことから、
① k < ならすまでに必要な能力値
貪欲に割り振る
②それ以外
ならしおわった後,得点の上限に気をつけるだけ
とやればいい。

以下ソースコード

int n,k,agel,point;
int a[100010];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>k;
	REP(i,n) cin>>a[i];
	REP(i,n) agel += (a[i]%10==0 ? 0:10 - a[i]%10);
	if(agel <= k){
		k -= agel;
		int asum=0;
		REP(i,n){
			point += (a[i]+9)/10;
			a[i] += (a[i]%10==0 ? 0: 10 - a[i]%10 );
			asum += 10 - a[i]/10;
		}
		if(asum <= k/10) point += asum;
		else point += k/10;
		//point += k/10;
		cout<<point<<endl;
	}else{
		vector<pair<int,int> > p(n);
		REP(i,n) p[i] = mp((a[i]%10==0 ? 0:10 -a[i]%10), a[i]);
		sort(p.begin(),p.end());
		int i=0;
		REP(i,n){
			k -= p[i].first;
			if(k < 0) break;
			p[i].second += p[i].first;
		}
		REP(i,n) point += p[i].second/10;
		cout<<point<<endl;
	}

}

SRM667 Div.2 Med

SRM TopCoder 競プロ

本番中は貪欲法で実装しテストに通ったのでそのままサブミットした。

貪欲法でだめなケースはこちら

{"0011","1100","1110"}　

逆に貪欲法で駄目なの気づいてれば大量虐殺できていい順位に慣れただろうなと。

じゃあ実際にはどうやるのかというとbitDPとかダイクストラ法とかをやる。今回はbitDPで実装した。計算量はO(2^m*n)くらい。

dp[i] = 0..0からiになるまでにかかるコストの最小値とすると、

bit[j] =  s[i]をbitで表したもの

dp[i | bit[j] ] = min(dp[ i | bit[j] ], dp[j] + __buildin_popcount( (i | bit[j] ) ^ i)の二乗 ;

という風になる。


class OrderOfOperationsDiv2{
	public:
	int dp[1<<20];
	int minTime(vector<string> s) {
		int n=s.size();
		int m=s[0].size();
		int bit[n];fill(bit,bit+n,0);
		REP(i,n)REP(j,m){
			if(s[i][j]=='1') bit[i] |= (1<<j);
		}
		fill(dp,dp+(1<<20),INF);
		dp[0]=0;
		REP(i,1<<m){
			REP(j,n){
				int nex=i|bit[j];
// 				DEBUG(bit[j]);
				bitset<20> bs((unsigned long)(nex^i));
				int cnt=bs.count();
				dp[nex] = min(dp[nex],dp[i] + cnt*cnt);
			}
		}
// 		REP(i,1<<m)DEBUG(dp[i]);
		int last=0;
		REP(i,n) last|=bit[i];
		return dp[last];
	}
	

};




天下一2015本戦(オープン)　感想

感想なので解説じゃないです。天下一はもう完投するの厳しそうと予選のころから思っていたので部分点を稼いでいこうと思ってた。実際はA,B完E,F部分点といった感じで26位(参加者が少ないため)

 

A,B はともにやるだけ全探索なのでやるだけ。

C といてる人ほとんどいない→やばそう撤退

D でた、三角形。やばそう

E 部分点はpermutationすればよさそう。n!*n^2ぐらいでも間に合うだろうから計算。

　水槽の面積を求める自体割と手間取って時間をとってしまった。

F どうみてもEulerTour。部分点なら毎回EulerTourすればいいとわかるのでそれで。

　昨日Yukicoderで木をやったのでわりとスムーズにかけた

G 見たけど時間的に無理そう、やめる

 

僕みたいな初心者でも部分点を狙っていけば点を取ることができるのはいいなと思った。さらに自分の成長の指標でもあるのでnヶ月後完投できたらいいなあと思う。

CFD2Cまとめ(CF300~)

CFR_C 競プロ CodeForces

解いた問題の類題が出たときに解けなければ問題を解いた意味がない。ので、解いた問題のちょっとしたメモ。(CFR300~)

・http://codeforces.com/contest/574/problem/C

　数論(簡単)

・http://codeforces.com/contest/572/problem/C

　数学、組み合わせ

・http://codeforces.com/problemset/problem/570/C

　分割統治的なあれ、データ構造

・http://codeforces.com/contest/568/problem/A

　ProjectEuler的

・http://codeforces.com/contest/567/problem/C

　三個選ぶやつ

・http://codeforces.com/contest/559/problem/A

　図形、思考系

・http://codeforces.com/contest/558/problem/C

　bit、全探索(のほうが楽？)

・http://codeforces.com/contest/557/problem/C

　EIGO,データ構造

・http://codeforces.com/contest/556/problem/C

　思考系

・http://codeforces.com/contest/554/problem/C

　組み合わせ, DP

・http://codeforces.com/contest/552/problem/C

　n進数

・http://codeforces.com/contest/551/problem/C

　二分探索

・http://codeforces.com/contest/550/problem/C

　数学

・http://codeforces.com/contest/546/problem/C

　シミュレーション

・http://codeforces.com/contest/545/problem/C

　思考系、貪欲法

・http://codeforces.com/contest/544/problem/C

　DP, メモリ節約

・http://codeforces.com/contest/540/problem/C

　経路探索、経路復元

・http://codeforces.com/contest/538/problem/C

　貪欲法

・http://codeforces.com/contest/538/problem/D

　全探索

 

 

結構量が多い…日々是精進

Codeforces#317Div.2 B - Order Book

CodeForces 競プロ CFR_B

問題文はこちら: Problem - B - Codeforces
レートが減少してついに緑に戻ってきてしまった。問題文を理解できず2WAが結構痛い。
orderをまとめるのも降順に取り出すのもmapを使えばできる。iteratorが若干めんどくさいだけでそこを気をつければできるはず。

今回からソースコードをのせるようにしてみた。参考になれば幸いである。

map<int,ll> buy;
map<int,ll> sell;
int cnt;
int main(){
	int n,s;cin>>n>>s;
	char d;int p,q;
	REP(i,n){
		cin>>d>>p>>q;
		if(d=='B') buy[p]+=q;
		if(d=='S') sell[p]+=q;
	}
	int sn=min(s,(int)sell.size());
	int bn=min(s,(int)buy.size());
	for(auto it=sell.rbegin();it!=sell.rend();it++){
		if(cnt++>=sell.size()-sn)
			cout<<"S "<<it->first<<" "<<it->second<<endl;
	}
	cnt=0;
	for(auto it=buy.rbegin();it!=buy.rend();it++){
		if(cnt++<bn)
			cout<<"B "<<it->first<<" "<<it->second<<endl;
	}
}

問題文がわかりにくかったしEIGO力が欲しい。

Codeforces #315 Div.2

CodeForces 競プロ

今回はまさかのAをHack,B,C遅解きになってしまい、振るわず。1601->1548(-53)

思うにAの問題が理解できず、Bでsetを使ってTLEしたことがキテる。

 

A. Problem - A - Codeforces

　問題文が理解しにくい。最初のS秒の再生でどこまでダウンロードできるかだけど再生してる実時間の(q-1)/q倍ダウンロードがされる（これをrとする）。つまり、最初にダウンロードが再生されるまで行くとrSされにダウンロードされており、さらにそこまで聞けて…

S+rS+r^2S+r^3S+r^4S+...= S/(1-r) = qS

となる(無限等比級数の総和公式を使用)。二回目の再生ではS=qSになったのとおなじなのでq^2Sまで再生できる。よって結局q^nS>Tとなるnをさがせばいい。対数をとってもできそうだけど怖いのでnを増やしていった(どうせO(log(T/S)))

 

B. Problem - B - Codeforces

　問題的にはAよりわかりやすい疑惑がある。Time limitが1secなのでnlognとかきつい？setを使ってたらTLEしてしまった(別にここでsetを使う意味はない)

　まず、どのIDが何回でてくるかカウントする。1~nのなかにあり一回も出てこないIDをvector<int>とかにpush_backしてメモっておく。舐めるようにまわして重複してたり、1~nの範囲でないのを見つけたらメモった中の数字に置き換える。

　といった感じ。

 

C. Problem - C - Codeforces

　あんまり見ないタイプ?の問題。nまでの回文数とnまでの素数どっちが大きいかって題材。

p,qが定められそのすべてのAについて適するnが存在する。

　という仮定を元にnを調べる。この仮説は結局正しい。ここでどうやって最大のnを求めるかだがnの最大値をNと決め打ちしてforをまわしてやってそれぞれで判定を行うだけ。まあ要するに愚直に試しまくる。nが最も大きくなるケースはp=42,q=1である。そのときのnは1179858なのでN=1200000ぐらいにしておけばいいとわかる。

・Nのオーダーをざっと見積もれないのかという話

素数の分布はnまでの素数は近似的にn/logn個になることが知られている。

一方回文数については

1桁では9個

2桁では9個

3桁では90個

という風になり、10^(logn/2)ぐらいというがばがばの憶測が立つ。

10^nまででは10^n/log(10^n) , 10^(n/2)

比較するとだいたいn=10^6ぐらいとあたりがつく。

 

Dは機会があれば