Hatena::Grouptopcoder

k_operafanのTopCoder日記

2011-11-17

[]TopCoder SRM 524 Div1 03:22

大敗北

Easy(250)

入力が合成数→1

入力がある程度大きい素数→1と偶数に分離して2

入力が2→2

入力が3→3

という感じに解いた.

ミラーラビンを使う必要は無かった.

Passed System Test(242.56)

Medium(450)

最大値が2000ぐらいであることには気づいたけど後はさっぱり…

Opened

Hard(1000)

Unopened

Challenge Part

3のケースのミスを一瞬で落とされて,他に落ちそうなコードも無いので終了

Result

得点:242.56

順位:208位

レート:2083(-20)

2011-11-04

[]Codeforces Beta Round #92 Div1 00:27

敗北

A問題

2の倍数と2で割ったら素数になる2の倍数の数を同じ色で塗るようにする.

貪欲法

B問題

座標を45度回転して,隣接移動及び斜め移動が出来ると考える.

オーバーフローによりWA

C問題

分からなかった

D問題

Suffix Arrayをごにょごにょすれば解けそうな気がしたけど…

結果

点数:936+0+0+0+0=936

順位:180位

レート:1874(-9)

RandhilRandhil2016/05/03 08:22Do you have a spam issue on this site; I also am a blogger, and I was wanting to know your situation; many of us have created some nice procedures and we are looking to trade methods with others, why not shoot me an e-mail if inerdestet.

FinchFinch2016/05/04 02:00that some of the Elders in this <a href="http://xwpgdj.com">pe#srn&o8217;s</a> district in Chile would be leaving their mission early so they could begin school on time. Found that interesting. Not sure how much longer they had to serve….I guess not too long.

CaeliiCaelii2016/05/08 12:25Fabrizio, come è andata l&rcs17;in8u#2ione nella tana di SeL?Tu sarai anche ateo, ma a me sembri un uomo di fede ferrea e incorruttibile (e guarda che non lo dico con tono ironico!) http://myahavx.com [url=http://afccsfw.com]afccsfw[/url] [link=http://dkckhfo.com]dkckhfo[/link]

2011-10-27

[]Codeforces #91 02:56

人権なんて無かったのです.

A問題

普通にやろうとすると10^9*11ぐらいになりそうだったので分割統治法を使って解いた.

intオーバーフローで2WA喰らった.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lli;
lli l,r;
set<lli> luckynumber;
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
vector<lli> lucky;
void dfs(lli now){
	lli f=now*10+4;
	lli s=now*10+7;
	if(now>1e11)return;
	if(luckynumber.find(f)==luckynumber.end()){
		luckynumber.insert(f);
		dfs(f);
	}
	if(luckynumber.find(s)==luckynumber.end()){
		luckynumber.insert(s);
		dfs(s);
	}
}
lli next(lli x){
	return *lower_bound(lucky.begin(),lucky.end(),x);
}
lli sum(lli l,lli r){
	lli t=next(l);
	if(l==r)return 0;
	if(t==next(r-1)){
		return t*(long long)(r-l);
	}else{
		return sum(l,(l+r)/2)+sum((l+r)/2,r);
	}
}
int main() {
	dfs(0);
	FOR(it,luckynumber){
		lucky.push_back(*it);
	}
	cin>>l>>r;
	cout<<sum(l,r+1)<<endl;
	return 0;
}

B問題

4477などがあるとループしそうだったのでループするまで回し,ループしたら残り回数mod2だけ回すという方針で解いた.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tr1/unordered_set>
using namespace std;
typedef long long lli;
#define set tr1::unordered_set
set<int> ac;
string data,back1,back2;
int n,k,v;
int main() {
	cin>>n>>k>>data;
	int seen=0;
	for(int i=0;i<k;i++){
		bool ok=false;
		for(int j=max(0,seen-1);j<n-1;j++){
			if(data[j]=='4'&&data[j+1]=='7'){
				if((j+1)%2==1){
					data[j]=data[j+1]='4';
				}else{
					data[j]=data[j+1]='7';
				}
				seen=j;
				ok=true;
				break;
			}
		}
		if(!ok)break;
		if(ac.find(seen)!=ac.end()&&v==0){
			v=1;
			i=k-2-(k-i)%2;
		}
		ac.insert(seen);
	}
	cout<<data<<endl;
	return 0;
}

C問題

k<10^9ということに気づかず10^9!をどうやって求めるのかを永遠と考えていた.

要復習

結果

点数:364+806+0+0+0=1170点

順位:278位

レート:1883(-43)

[]TopCoder SRM 522 Div1 09:34

Mediumが久々に解けた気がして嬉しいです

Easy(250)

問題の制約を見た瞬間にMin-Max+メモ化だと思い込んでしまう。

VBで書くと面倒なことになりそうだったのでC++で書いた。

運良くバグ無く実装出来たのでちょっと見直してから提出。

Passed System Test(228.39/9分)

Medium(450)

問題の制約から必ずa≦bとすることが出来る。(そうじゃなかったらswapする)

また、A=B=C=1の時を考えると答えは必ず3×10^9未満になる。

このことからA<10^5になることが分かるのでAについて1から10^5まで全て試してみることにした。

Aを固定すると,差の絶対値の和は |A-a|+|B-b|+|AB-c|となり、Aは定数なので結局Bについての関数|B-b|+|AB-c|を最小化する問題になる。

この関数は一次式になりそうなので答えは明らかに1,b,c/Aの周辺にあることが分かる。

なのでBはこの3つの周辺を適当に(±3ぐらい)探索すればよい。


とかコンテスト中に考えていました。

Passed System Test(289.11/25分)

Hard(1050)

少し考えてみたものの、結局何も思いつかず。

Opened

Challenge Part

何も出来なかった。

Mediumが5人System Testで落ちていたので、もっと深く考えていれば…

Result

得点:517.50点

順位:49位

レート:2103(+61)

2011-10-05

[]TopCoder SRM 520 Div1 23:18

再びEasyを安定して解けるようになることが目標だった.

日本人が部屋に多い回

Easy

Luckは得点が大きい問題に使った方が得なので,どの問題を解くかを決めて,貪欲に解いた.

書くのが遅い

Passed System Test(224.11)

Medium

二次元DPに直せるということに気づいたが,ある数字を取る組み合わせを作る処理にかかる計算時間の予想をミスしてしまい,失敗

Opened

Hard

Unopened

Challenge Part

一通り見てみてどれも通りそうだったので放置

室内一位の人がミスをしてくれて,自分が室内一位に

+0/-0

Result

得点:224.11点

順位:168位

レート:2010(+25)

このMediumが解けなかったのは不味かったので精進したい.

2011-10-02

[]Google Code Jam Japan 予選 17:50

Largeを正解することを最優先に参加

あまり解く速度は気にしていなかったけど遅すぎた.

A問題

後ろから見るという頭が良い解法には気づけず,連続した数字の部分をまとめる解法で解いた.

C問題

出来るだけ個数が多くなるように貪欲に解いた.

B問題

priority_queueを使って後ろから見る.

自作のpriority_queueがバグっていて1WA.

仕方がないので,毎回Listをソートするという方法で通した.

結果

得点:54点(/54点)

順位:44位

CactusCactus2016/05/03 06:59A pleaginsly rational answer. Good to hear from you.

CadeCade2016/05/04 08:57Liquid diet. fifty cent recently lost 50+ in 9 weeks by working out three hours a day and only consnmiug liquids. But if you choose this method be sure to take vitamins and protein shakes and keep regular doctor visits. http://mcvwqukoct.com [url=http://yleupd.com]yleupd[/url] [link=http://zljccqftlj.com]zljccqftlj[/link]

MahaliaMahalia2016/05/06 22:32Well, thanks for <a href="http://tdhvqkdnmu.com">comnemting!</a> I’m glad you enjoy my blog. I certainly enjoy writing it. The Narnia books are amazing. I love the way they feed the imagination with other worlds. How did they change your life?