問題概要

有向全域木が与えられる。2つ頂点を選んで、そこからすべての頂点へ辺の向きに従って到達できるように辺の向きを変える。
変えなければいけない辺の数をコストとすると、最小のコストはいくらか。

頂点数<=3000

方針

2つの頂点で到達すればよいので、ある一つの辺で覆う範囲を分割できる。
分割した後は、
まずある頂点を選び、そこを始点としたとき分割したグラフ内で向きを変える辺の数(cost'と呼ぶ)を数える。
ここで、その選んだ頂点と隣接する頂点を始点とする向きを変える辺の数は、
最初に選んだ頂点が隣接する頂点に向いているなら、cost'+1
そうでないなら、cost'-1
となることが簡単に分かる。これはO(N)で実装できる

すべての辺で分割し、上の方針を繰り返す。O(N^2)

小さいケースに注意！

using namespace std;
static const int INF =500000000;

typedef pair<int,int> pi;
int n;
vector<pi> g[3005];
pi es[3005];
int dfs(int v,int p){
	int res=0;
	for(int i=0;i<g[v].size();++i){
		pi& e=g[v][i];
		if(e.first==p) continue;
		res+=e.second+dfs(e.first,v);
	}
	return res;
}
int move(int v,int p,int val){
	int res=val;
	for(int i=0;i<g[v].size();++i){
		pi& e=g[v][i];
		if(e.first==p) continue;
		res=min(res,move(e.first,v,val+1-e.second*2));
	}
	return res;
}

int main(){
	cin>>n;
	for(int i=0;i<n-1;++i){
		int a,b;cin>>a>>b;--a;--b;
		g[a].push_back(make_pair(b,0));
		g[b].push_back(make_pair(a,1));
		es[i]=make_pair(a,b);
	}
	int ans=INF;
	if(n<=2) ans=0;
	for(int i=0;i<n-1;++i){
		int A,B;
		A=es[i].first;B=es[i].second;

		int sum1=dfs(A,B),sum2=dfs(B,A);

		ans=min(ans,move(A,B,sum1)+move(B,A,sum2));
	}
	cout<<ans<<endl;


	return 0;
}

こういう回の場合、BよりCを先にやったほうが(解ける人にとっては)いいです

2012-12-14

Codeforces#148 div1B,div2D Boring Partition

URL:http://www.codeforces.com/contest/238/problem/B

問題概要

ある数列が与えられる。
これを、2つの部分列に分ける（どちらかが空でも良い）
ある2つの要素の間のコストを、2つが同じ部分列に分けられているならその和、そうでないなら和に+hしたもの(hは与えられる)と定義する。
すべての要素の間のコストの最大の差(つまり、一番大きいコスト-一番小さいコスト)の最小値はいくらか。
また、最小値を取るときどのように分けるかも出力せよ。
数列の長さ<=10^5、h<=10^8、数列の要素<=10^8

方針

貪欲
考えると、ソートしてから一番小さい要素の他を数列A,そこからいくらかまでを数列B,そのあとは再び数列A、
とするか、すべて同じ数列に入れるか、が最適
あとは、律儀に実装。
比較的頭悪い実装している・・・

using namespace std;

pair<int,int> a[100005];
int h;
int n;
int ans[100005];
int main(){
	cin>>n>>h;
	for(int i=0;i<n;++i) cin>>a[i].first,a[i].second=i;
	sort(a,a+n);

	if(n==2){
		printf("%d\n",0);
		printf("%d %d\n",1,1);
		return 0;
	}

	int res=INF;
	pair<int,int> range;
	{
		int minval=min(a[1].first+a[2].first,a[0].first+a[1].first+h),
			maxval=max(a[n-1].first+a[n-2].first,a[0].first+a[n-1].first+h);
		if(maxval-minval<res){
			res=maxval-minval;
			range=make_pair(1,n-1);
		}
	}
	{
		int minval=a[0].first+a[1].first,maxval=a[n-1].first+a[n-2].first;
		if(maxval-minval<res){
			res=maxval-minval;
			range=make_pair(0,n-1);
		}
	}

	for(int i=1;i<n-1;++i){
		int minval=min(a[0].first+a[1].first+h,a[0].first+a[i+1].first);
		if(i>=2) minval=min(minval,a[2].first+a[1].first);
		int maxval=-1;
		if(i<n-2) maxval=a[n-1].first+a[n-2].first;
		maxval=max(maxval,a[n-1].first+a[i].first+h);
		if(maxval-minval<res){
			range=make_pair(1,i);
			res=maxval-minval;
		}
	}

	printf("%d\n",res);
	for(int i=0;i<n;++i) ans[i]=1;
	for(int i=0;i<n;++i) if(range.first<=i && i<=range.second) ans[a[i].second]=2;

	for(int i=0;i<n;++i) printf("%d%c",ans[i],i==n-1?'\n':' ');

	return 0;
}

2012-12-14

Codeforces #148 div1A,div2C Not Wool Sequences

これからボチボチCodeforcesの和訳＆解説＆コードとかを公開していくかもしれません
基本的に、自分が受けたコンテストを1日後ぐらいに公開する予定です

URL: http://www.codeforces.com/contest/238/problem/A

問題概要

ある数列について、隣接した空でない部分列のxorを取ったものが0となる部分列があるとき、その数列はWool sequenceとする
長さNで要素が0から(2^m)-1でWool Sequenceでない数列の数を10^9+9で割ったあまりを求めよ。
1<=N,m<=10^5

方針

i番目まで決まったとすると、
[0,i)までの数列の部分列にxorして0となるものはない。
i番目をx(x!=0)という数にして、[j,i](0<=j

using namespace std;
static const int INF =500000000;
typedef pair<int,int> pi;
const long long mod=1000000009;
long long mpow(long long a,int k){
	long long res=1;
	while(k){
		if(k&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		k>>=1;
	}
	return res;
}

int main(){
	int n,m;
	cin>>n>>m;
	long long res=1;
	for(int i=0;i<n;++i){
		res*=mpow(2,m)-1-i;
		res%=mod;
	}
	cout<<res<<endl;

	return 0;
}

2012-11-30

うさこテスター

コンテスト系その他

USACOの最近2年ぐらいはジャッジに載ってないらしいので適当に使っているC++用のテスターをupします(需要あるのか・・・？)
USACO,解こう！（勧誘）　http://www.usaco.org/index.php?page=contests
Main内は、グローバル変数も初期化が必要なので注意
ちょっと（入力、解答ファイル名）変更すれば他のにも転用可能です
解のうちどれか一つを出力、任意の順番で出力、といった形式には対応していないので注意

int Main(){

}

const int TESTNUM=12;//THE NUMBER OF TEST CASES
int main(){
	Main();return 0;//DELETE THIS LINE WHEN TEST
	for(int i=1;i<=TESTNUM;++i){
		stringstream ss;ss<<i;
		string input="I."+ss.str(),output="O2."+ss.str(),answer="O."+ss.str();
		
		freopen(input.c_str(),"r",stdin);
		FILE* fp=freopen(output.c_str(),"w",stdout);
		
		Main();

		fclose(fp);

		ifstream cin1(output.c_str()),cin2(answer.c_str());
		string a,b;
		while(1){
			if(cin1.eof() && cin2.eof()) break;
			cin1>>a;
			cin2>>b;
			if(a!=b){
				fprintf(stderr,"FAIL in test %d\n",i);
				fflush(stderr);
				return 0;
			}
		}

	}
	fprintf(stderr,"Accepted\n");
	return 0;
}

2012-10-01

IOI2012-適当に

IOI2012

なんか大会中にちょくちょく書く予定でしたがかけなかったのでまとめて書きます

Day0-移動

朝は成田のホテルで。オリセンよりおいしい
空港に入る。写真とか取る。飛行機乗る。特にトラブルなし
時間的に、飛行機内では起きているべきな気がしたのでずっと起きてアニメ（なのはA's）を見る。映画見たので内容大体知ってた。面白かった
フランクフルト乗り継ぎ。厳しいという噂があったが全然そんなことなかった。
空港広い。商品がべらぼうに高い。
A's見終わって、StrikerSの4話ぐらいまで見る。
Arrows Tab,再起動すると30%充電が吹っ飛んだり、充電の残りが減らないまま3時間持ったりとよく分からない。(行きも帰りも9hrぐらいは持った)
ミラノ着く。百万都市とは思えない空港のショボさ。
バスに乗ってthe Garda Village（ガルビレ）へ。
隣の人と話す機会を伺っていたが2時間ぐらい掛けてようやく"Hello"を言えた。Slovakia人だった
適当に話す。 are you sure you'll get a gold medal?と聞いて、I hope I'll get itとか返された。
ガルビレ着く　部屋の案内とかされる。
飯を食って、寝る
部屋の2段ベッドの2階部分に柵がなかったりいろいろひどいので、部屋の改造する

Day1-Opening Ceremony&practice

朝飯食べて、montichiariへ。なぜか15分ぐらい同じ場所で待たされた。
opening ceremony イタリア英語なかなかひどかったので長い間寝ていた。
昼ご飯。バイキング形式なのだがハエが生えていた。
Belarusチームと交流とかする。取材の交流押し付けなかなかつらぽよで辛かった。
アゼルバイジャンの人が突然"合気道知ってますか"みたいなこと聞いてきて楽しかった
あとどこかの国の記者の取材に遭った
そのままハエが生えた状態でpractice。
practiceは普通に。別解の二分探索segtreeにかなり手こずり衰えを感じた。

Day2-Contest Day1

コンテストこわい＞＜
警察の車が道を少し封鎖していて、VIP的何かを感じた。
ハエがまだいる。
安定の遅延スタート。
なぜかこの日は問題文に目を通して計画を立てるということをせず、見た問題から解き始めてしまった。
おどめたのsubtask1,2の後ringsバグって死ぬ。3hr&30minぐらい使ったが20点しか取れなかった。
残りの時間で適当に部分点を集める。120点100位以下（絶望）
悲しくなりますよ〜ホント
金メダル絶望的

Day3-Gardaland

雨が降っている。semiexp[雨を感じるかは選択制にすべき]
怖そうなアトラクションに乗る。しばらくして危険組＆安全組に分かれる（自分は危険組）
Oh Oh Oh Gardaland~~（http://www.youtube.com/watch?v=bsRxQospbyk）
やばそうなアトラクションにたくさん乗る。たのしい。
夜寝るとき、アトラクションの乗りすぎで体がふわふわ感じられた。

Day4-Contest Day2

コンテストこわい＞＜
ハエ、少しは少なくなったがまだいる。
安定の遅延スタート
今回は一昨日の反省を生かし、まず全部読む。
tournament、やればできそう。ゴリゴリ。
2WAののち、2時間弱でAC。うれしい
cityの55点はやるだけなので書く。1WAののち55点取れた
supperで満点近く取れるとうれしいので頑張って考えるが分からん。
仕方ないので33点ぐらいの部分点狙う。意外と実相に手こずる。
頑張って32点ぐらい取る。ちょっとした改善を入れて40点にする。
そのまま終わり。195点
まあ、今日の結果には満足。day2では19位
合わせて38位で銀。day1くそぽよ杉って一番言われてるから（金は27位ぐらいまで）

Day5-Venezia

朝早く起きてバス->電車でveneziaに行く。
Iranの人に名刺を配る。havalizaさんが自分しっててうれしかった。
電車では寝る。
veneziaについた。中型船のようなものに乗る。
風景綺麗だった。
船から降り、次に入る建物の前でかなり待たされる
適当に観光をする。いろいろ回った後、昼食を食べ、芸術品が並んだ所に行く。
りんごさんが芸術品でいろいろな遊びをしていた。
AustralianとかKoreanとかGreekと交流とかする
よく分からない人の演説見たいなのを聞く。
帰る。italian queueがやばいし虫が多くてなかなか不快
名刺切れたなーと思って名刺ケース見たらなのは映画券が出てきて爆笑
帰りの船で、HAYATE YAGAMIという文字と人間系のイラストが書かれた台湾の人と話したりする。愉快な人だった。(映画券自慢した)
りんごさんによると、twitterでは髪型や髪の毛の色を変えただけのアイコンが大量に存在していて訳が分からないらしい

Day6-Sirmione&Closing Ceremony

ゆっくりSirmioneへ。
みかんさん湖に落ちました。鳥に触ったらしい
レーティング3950のサイ
ツアーを断るタイミングを失い、よく分からないツアーに付き合わされる。
城の解説を回避し、中心部への道を教えてもらう
この日も雨が降ってた。
アイスとか、ピザとか食べる。おいしい
昼食のためガルビレに戻る。
setというゲームをhosさんやother contestantsとする。
closing ceremony会場へ。メダルで席が分けられているらしい・w・
適当にceremonyをやり過ごし、メダルも難なくもらった。
突然拍手が何回も沸いた。"つまらん説明早く止めろ"と言わんとしている
touristかっこいい！！Hoさんもかっこよかった
Russia,USA,Singaporeとかと交流する。scott_wuさんが自分知っててうれしかった。
farewell partyかとおもったらfarewell dinnerで、ただのcrowded dinnerだった。
交流あまりしないで帰る。寝る

Day7-移動

バスでミラノへ。
適当に飯を食べて、飛行機に乗る。
今度はミュンヘン乗り継ぎ。ミュンヘンからの飛行機ではまたなのはを見ていた
StrikerS、semiexpさんにもらったのは全部見た。最後4話ぐらいが欠けてて悲しみ。
少し・・・頭冷やそうか
結局帰りもずっと起きてた。

Day8-移動＆表敬訪問

semiexp[飛行機に乗ってると物理的に腹が立つ]
成田空港を抜けて、成田expを使って東京へ。
内閣改造なので政務官か何かの人に会った。まあいい人だった。
帰る。ねむい

Day9-風邪をひいています

全体的に

停電起こる。壊れるなあ
belarus/russiaは全員イケメン
あせってはいけない（戒め）
うさぎさんがガルビレを闊歩していた。
魔法少女になりたい＆女装したくないとなると、全裸魔法少女か男装魔法少女しかない（レベル高すぎる・・・）
タバコ厳重に規制されるべき
来年は金メダル取るゾ〜〜

2012-09-22

直前合宿

IOI2012

適当に書きます

朝起きる。荷物の最後の詰め込みする
車で成田まで行く
着く。生徒・チューターではsemiexpさんしかまだいなかった
だんだん人が集まる。おすしさんがルールの翻訳を解説するPhase.有難いけどねむい
その後はチューターsがIOI系問題の解説
壮行会。ちょっとだけ緊張した。父兄で来てるの自分の父だけで草
飯。おいしかったけど天ぷらがえび2本だった、悲しみ（えび好きじゃない）しかししょうがないのでほぼ生まれて初めてえびの天ぷら食べた。意外と普通だったがやっぱり食感が・・・
解説続き
個室に戻る。りんごさんのWin7を使って無線を飛ばして集まってネットやってた
今22:43　そろそろ寝なきゃ

2012-09-20

IOI 2012に行ってきます

IOI2012

今年のIOIは9月23日から29日にかけて開催されます。
日本からは4人の代表が派遣されます。選手はsemiexpさん、hziwaraさん、tozangezanさんと僕です。
海外から出る強い人は、touristさん、yeputonsさん、sevenkplusさんなど。（RedCoder級でもごろごろいます）

IOIについての説明・出題内容はわかりやすいページがあるのでここを見てください(ちなみに、IOIは高校生の大会です)　->　
http://qnighy.hatenablog.com/entry/20110719/1311078076

抱負
- 金メダルをとること
  - 金メダル、約25人に配られますが、世界の代表が300人も来ているのでなかなか難しいです。ただへなちょこなミスを犯さなければ金メダルをとることは十分可能であると認識しています（まあへなちょこなミスを犯さないというのは相当難しいことですが・・・・）
  - ちなみに、銀すら取れなかったら日本帰れないぐらいでいい気がする
- 積極的に国際交流する
  - そもそも外国に行って外国人と話した経験ほとんどないのでかなり不安です。　まあでも自分から声かけていけばシカトされることはないと思うのでどうにかなるかなー、とも　あと、強い人を生で見てみたいです
  - どちらかというと名刺配りまくる感じより名前覚えてもらうぐらいの人を何人か作りたいです

競技がある日は25日、27日です。今年もcontest scoreboardが外部の人には公開されるようなので、是非観戦してください！！（日本時間夕方5時からで割と日本人にもうれしい時間）
scoreboardや速報・ライブ映像とかのURLとかも分かり次第貼っていきます

http://www.ioi2012.org/direct-video/　ここでライブ映像とかありそう？暇だったら流して見てるとｵﾓﾛｲかも。来年IOI行く予定の人にとってもいいかもしれません。
ニュースレター速報も今年はJOI公式ページに作られる予定ですが、まだページ作ってないみたいです
scoreboardもどこにあるのかまだよく分からないですが、http://www.ioi2012.org/competition/results/　ここ辺りに何かしらのannounceはされると思います

hogloidのブログ

へなちょこ

Codeforces#148 div1C,div2E World Eater Brothers

問題概要

方針

Codeforces#148 div1B,div2D Boring Partition

問題概要

方針

Codeforces #148 div1A,div2C Not Wool Sequences

問題概要

方針

うさこテスター

IOI2012-適当に

Day0-移動

Day1-Opening Ceremony&practice

Day2-Contest Day1

Day3-Gardaland

Day4-Contest Day2

Day5-Venezia

Day6-Sirmione&Closing Ceremony

Day7-移動

Day8-移動＆表敬訪問

Day9-風邪をひいています

全体的に

直前合宿

IOI 2012に行ってきます