Hatena::Grouptopcoder

k_operafanのTopCoder日記

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?