Hatena::Grouptopcoder

hirosegolf@競技プログラミング

2018-07-14

AGC026

| 00:42

成績:ABEを解いて100位

コンテストページ:https://beta.atcoder.jp/contests/agc026

とりあえず、Fから考え始めた。

Nが偶数の場合は、どちらかの端から取っていくのが最善であることがすぐ分かる。

Nが奇数の場合は、すぐには思いつかなかった。

Fは、配点的にも難しい可能性があるので、放置して次に進むことに。(ここで消費時間10分ほど)



Eを考え始める。

Eは、ある条件を満たす部分列であって、辞書式で最大のものを作る問題。

N=3000なので、O(N^2)解法まで許されるということを念頭において考察を開始した。

辞書式順序を考えているので、まず最初にbが幾つ並ぶかが重要。

そこで、その部分から考え始めることにした。

最初に選ぶbの場所の座標をxとして、またそれに対応するaの場所をyとする。

x>yは、aから始まるという酷いシチュエーションなので、とりあえず、x<yの場合を考えることにした。</ppp>

すると、xとyの中間の位置にあるbは全て回収していくのが最善となる。

よってスタート場所を指定すれば、最初にbが幾つ並ぶかが分かることになる。この個数が単独一位になっている箇所が1箇所だけであれば、それで開始箇所が分かるが、そんなに甘くないことはすぐに分かる。

よってb...baとなってから以降の箇所についても、ちゃんと考えないといけない。

このあたり、じっくり考えないとすぐに混乱するので、時間がかなり消費される。

ここを考えてると、aの個数とbの個数が一致するような切れ目(i番目までに含まれるaとbが一致するようなi)が重要になってくることに気づいた。

これに気づいた理由は正確には覚えてないが、丁寧に考えれば、どんな道筋を辿っても必然的に思いつくことで、非自明な箇所ではない。しかし、反射的に思いつく内容でもないので、少しは時間を消費した。


abが同数となる切れ目で分割しておくアイデアに気づいいてからは次の通り。

最初の文字がaとbで場合分けをする必要がありそうだと思う。

bから始まる場合はさっきの発想を延長させればいい。

aから始まる場合は、少し考えてabab交互に並べるのがよいと分かる。


実装については次のようになった。


string s;
vector<string> ss;
char a = 'a';
char b = 'b';

vector<int> make_jump(string s){
	int n = s.size()/2;
	vi jump(s.size(), -1);
	int ia = -1, ib=-1;
	rep(k,n){
		ia++;
		ib++;
		while(s[ia]==b)ia++;
		while(s[ib]==a)ib++;
		jump[ia] = ib;
		jump[ib] = ia;
	}
	return jump;

}

vector<string> find_kouho(string s){
	vector<string> ret;
	vi jump = make_jump(s);
	if(s[0]==a){
		int n = s.size()/2;
		int i=0;
		int cnt = 0;
		while(i<s.size()){
			assert(s[i]==a);
			cnt++;
			i = jump[i]+1;
			while(i<s.size() && s[i]==b )i++;
		}
		string ret_s;
		rep(j,cnt){
			ret_s.push_back(a);
			ret_s.push_back(b);
		}
		ret.push_back(ret_s);
	}
	if(s[0]==b){
		rep(start,s.size()) if(s[start]==b){
			string ret_s;
			FOR(i,start, s.size()){
				if(s[i]==b || (s[i]==a && i>=jump[start])  )ret_s.push_back(s[i]);
			}
			ret.push_back(ret_s);
		}
	}
	return ret;
}

void _main(istream &inp){

	int si;
	inp >> si >> s;
	assert(s.size()==2*si);
	int start = 0;
	int cnt = 0;
	for(int i=0; i<=s.size(); i++){
		if(i>0 && cnt==0){
			ss.push_back(string(s.begin()+start, s.begin()+i));
			start = i;
		}
		if(i<s.size()){
			if(s[i]==b)cnt++;
			else cnt--;
		}
	}
	//debug(ss);
	string cur;
	for(int k=ss.size()-1; k>=0; k--){
		string best = cur;
		for(string u:find_kouho(ss[k]) ){
			if(u+cur >= best){
				best = u+cur;
			}
		}
		cur = best;
	}
	cout << cur << endl;
}

実装自体は綺麗にできたと思うが、そもそも量が多いので、実装にもそれなりに時間がかかってしまった。バグには殆どハマっていない。慎重にやりすぎた可能性はある。


結局Eの消費時間は80分ほど。(合計で90分)

ここは、時間を使いすぎてる感があるが、今の所、改善方法は思いつかず。




残り時間やばいなと思いつつDを開く。

とりあえず、左から順に埋めてくdpを考える。

全ての数え上げと、右側部分が交互に並んでいる場合の数え上げと、2つ用意してdpすれば良さそうだと思って、漸化式を作り始める。

しかし、それだと駄目なことに気づく。

Dの配点は1100点でBCを解いたほうが配点が高い。それを思ってDをやめてBCに移ったが、結果的にCは解けなかったので、Dに時間を掛けたほうが良かったかもしれない。

何はともあれ、BをDを諦めた時点で残り時間は40分ほどだったように思う。


Cの問題を見る。

数え上げの問題。全ての場合の数は、C(2N,N)。また、Nは最大で18にもなる。だから、全探索じゃ間に合わない。全て同じ文字の場合はC(2N,N)になるので、枝刈りしても駄目で、適当にまとめ上げて数える必要がある。

これもすぐには思いつかなかったので、とりあえずBに移ることに。


Bの問題を見る。

これは、さっくり解けた。しかし、実装が多少面倒なので、おそらく15分ぐらい消費した?


この時点で実は残り時間が7分ぐらい。もう、Dを解くのは絶対に無理なのでAを開く。


Aは、すごく簡単。4分ほどで解く。



全体の反省点:

パフォーマンス2634でレートは微増した。すごく駄目な成績というわけではないが、よい成績でもない。Eは時間を掛けすぎたが、それなりに考察の重さがあったので、ちょっと厳しい。最速正解者は25分だが、それはちょっと手の届く領域という感じではない。

CDはそれなりに時間を使って解けなかったのはちょっと勿体なかった。一つの問題に時間を集中させた方が得策だったか?



追記:

CDの解説を読んだ。

Cは真ん中で切るという発想は、ちょっと非凡である。

なぜなら問題自体には、中心部分という要素がないので。

結果論としては具体例を調べるのに時間を掛けるべきだったかもしれない。

Dについては下から埋めていくdpだった。思いつくのは十分可能だと思うが、左から埋めてくdpでも何とかなりそうだという気分の時に、このような方針転換をするのは勇気がいる。

rtaletixwprtaletixwp2018/07/31 08:52<a href="http://psychologytweets.com">cheap cialis prices</a> order cialis online canadian pharmacy http://psychologytweets.com

ataletawbxataletawbx2018/08/02 05:19<a href="http://rabbitinahat.com">cialis online</a> order cialis no prescription http://rabbitinahat.com

ytaletmqosytaletmqos2018/08/04 02:53<a href="http://mphasset.com">buy viagra online canada</a> order viagra air travel http://mphasset.com

ltaletnvwqltaletnvwq2018/08/06 16:31<a href="http://mphasset.com">cheap viagra tablets</a> female viagra pill http://mphasset.com

jtaletykvwjtaletykvw2018/08/07 19:22<a href="http://istanbulexpressonline.com">mail order viagra uk</a> ordering viagra online http://istanbulexpressonline.com

utaletcvsuutaletcvsu2018/08/18 06:46<a href="http://istanbulexpressonline.com">is 100mg viagra too much</a> viagra company http://istanbulexpressonline.com

italeteyqsitaleteyqs2018/08/18 09:36<a href="http://istanbulexpressonline.com">where do they sell viagra</a> viagra over the counter cvs http://istanbulexpressonline.com

htaletpeomhtaletpeom2018/08/18 12:08<a href="http://mphasset.com">viagra blue pill</a> bad effects of viagra http://mphasset.com

ctaletcatcctaletcatc2018/08/18 14:39<a href="http://mphasset.com">viagra alternative pills</a> canadian viagra sales http://mphasset.com

gtaletxmnegtaletxmne2018/08/18 16:35<a href="http://bakerssign.com">how long does it take levitra to work</a> levitra pills http://bakerssign.com

ytaletarzoytaletarzo2018/08/18 18:44<a href="http://mphasset.com">viagra results</a> can i get viagra over the counter http://mphasset.com

ftaletkuknftaletkukn2018/08/18 20:20<a href="http://gigawatt6.com">can you take cialis with high blood pressure</a> cialis 20mg side effects http://gigawatt6.com

qtaletmiluqtaletmilu2018/08/18 22:18<a href="http://baymontelreno.com">buying cialis in canada</a> canadian cialis cost http://baymontelreno.com

italetfbxzitaletfbxz2018/08/18 23:34<a href="http://gigawatt6.com">taking 4 5mg cialis</a> cialis for daily use cost http://gigawatt6.com

vtaletsouxvtaletsoux2018/08/19 01:30<a href="http://psychologytweets.com">is generic cialis available in canada</a> how to buy cialis with a prescription http://psychologytweets.com

ttaletgbvattaletgbva2018/08/19 02:47<a href="http://baymontelreno.com">what is a cialis</a> how long until cialis kicks in http://baymontelreno.com

htalethvykhtalethvyk2018/08/19 10:26<a href="http://psychologytweets.com">cialis or viagra</a> cialis sex http://psychologytweets.com

ktaletdnuwktaletdnuw2018/08/19 17:05<a href="http://bakerssign.com">levitra dosage instructions</a> www.levitra.com http://bakerssign.com

ataletwmhtataletwmht2018/08/19 22:55<a href="http://psychologytweets.com">cialis bph dosage</a> how long before cialis starts working http://psychologytweets.com

dtaletxceqdtaletxceq2018/08/20 00:43<a href="http://gigawatt6.com">daily cialis review</a> took too much cialis http://gigawatt6.com

ctaletmpxqctaletmpxq2018/08/20 01:51<a href="http://gigawatt6.com">us online pharmacy cialis</a> liquid cialis for sale http://gigawatt6.com

gtaletbvdugtaletbvdu2018/08/20 13:08<a href="http://psychologytweets.com">uses of cialis</a> generic cialis online india http://psychologytweets.com

xtaletimrrxtaletimrr2018/09/11 12:24<a href="http://missreplicawatches.com">how long before cialis daily starts working</a> cialis online us http://missreplicawatches.com

ftaletarjaftaletarja2018/09/11 13:40<a href="http://mphasset.com">viagra before and after pictures</a> where can u buy viagra http://mphasset.com

mtaletflbcmtaletflbc2018/09/11 15:46<a href="http://istanbulexpressonline.com">viagra before after</a> viagra dosage information http://istanbulexpressonline.com

ztaletulxfztaletulxf2018/09/11 18:15<a href="http://baymontelreno.com">cialis 5 mg tablet</a> cialis time to work http://baymontelreno.com

etaletxddyetaletxddy2018/09/12 05:23<a href="http://buycialisonl1ne.us">can i buy cialis over the counter</a> generic cialis online usa http://buycialisonl1ne.us

ttaletfdtkttaletfdtk2018/09/12 06:47<a href="http://viciolatino.com">viagra coupon</a> cheap pill viagra http://viciolatino.com

gtaletcselgtaletcsel2018/09/12 10:13<a href="http://canadian-pharmasale.com">order cialis australia</a> cheap cialis canadian http://canadian-pharmasale.com

mtaletxihomtaletxiho2018/09/12 14:52<a href="http://valladium.com">order cialis online cheap</a> buy cialis online canada http://valladium.com

ftaletiapsftaletiaps2018/09/12 15:15<a href="http://timsbmw.com">levitra definition</a> levitra canadian online pharmacy http://timsbmw.com

jtaletsjtsjtaletsjts2018/09/12 16:02<a href="http://usedrestaurantequipmentaz.com">buy cialis with prescription</a> cialis pills http://usedrestaurantequipmentaz.com

gtaletlvqpgtaletlvqp2018/09/12 18:25<a href="http://bullsac.com">free levitra</a> difference between viagra cialis levitra http://bullsac.com

ctaletjvazctaletjvaz2018/09/12 19:06<a href="http://h-m-j.com">viagra cheap prices</a> cheap generic viagra 100mg http://h-m-j.com

italetpebkitaletpebk2018/09/12 22:08<a href="http://usedrestaurantequipmentaz.com">cheap cialis in usa</a> generic cialis cheapest price http://usedrestaurantequipmentaz.com

dtaletbbrddtaletbbrd2018/09/12 23:06<a href="http://canadian-pharmasale.com">generic cialis pills</a> order cialis no prescription canada http://canadian-pharmasale.com

mtaletjsxpmtaletjsxp2018/09/12 23:22<a href="http://buycialisonlineglka.com">cheap cialis online canadian pharmacy</a> generic cialis online usa http://buycialisonlineglka.com

ltaletslkfltaletslkf2018/09/13 01:27<a href="http://timsbmw.com">buy levitra no prescription</a> how to make levitra work better http://timsbmw.com

italetskcoitaletskco2018/09/13 01:42<a href="http://viciolatino.com">canadian pharmacy generic viagra</a> order prescription viagra http://viciolatino.com

ltaletgnidltaletgnid2018/09/13 04:22<a href="http://missreplicawatches.com">cialis online canada</a> best site to order cialis http://missreplicawatches.com

ntaletxgprntaletxgpr2018/09/13 07:25<a href="http://missreplicawatches.com">cheap cialis in usa</a> order cialis with paypal http://missreplicawatches.com

btaletvsbmbtaletvsbm2018/09/13 14:36<a href="http://buycialisonl1ne.us">generic cialis</a> buy cialis cheap canada http://buycialisonl1ne.us

jtaletnktxjtaletnktx2018/09/13 17:29<a href="http://unishade.com">ordering cialis online</a> cheap cialis australia http://unishade.com

dtaletyegudtaletyegu2018/09/13 18:59<a href="http://waltzweekend.com">buy viagra online without</a> cheap 25mg viagra http://waltzweekend.com

rtaletbarertaletbare2018/09/13 22:02<a href="http://gigawatt6.com">generic cialis from india</a> cheap cialis online canadian pharmacy http://gigawatt6.com

ptaletytnpptaletytnp2018/09/14 01:08<a href="http://buycialisonl1ne.us">cialis 5 mg online</a> cheap cialis usa http://buycialisonl1ne.us

ftaletmtgtftaletmtgt2018/09/14 03:00<a href="http://canadian-pharmabuy.com">cheap viagra canada pharmacy</a> cheap generic viagra online pharmacy http://canadian-pharmabuy.com

ctaletwxqzctaletwxqz2018/09/14 03:26<a href="http://viciolatino.com">generic viagra online pharmacy</a> women viagra http://viciolatino.com

btaletwhtubtaletwhtu2018/09/14 04:34<a href="http://baymontelreno.com">cheap generic cialis canadian pharmacy</a> order cialis online us pharmacy http://baymontelreno.com

vtaletdhkvvtaletdhkv2018/09/14 06:46<a href="http://motechautomotive.com">order cialis paypal</a> cheap cialis online uk http://motechautomotive.com

ltaletvcgmltaletvcgm2018/09/14 10:44<a href="http://missreplicawatches.com">discount cialis pills</a> cheap brand cialis online http://missreplicawatches.com

dtaletfclxdtaletfclx2018/09/14 11:07<a href="http://canadian-pharmabuy.com">cheap viagra</a> cheap viagra pills http://canadian-pharmabuy.com

otaletttcsotaletttcs2018/09/14 15:39<a href="http://usedrestaurantequipmentaz.com">buy cheap cialis 20mg</a> cialis online bestellen http://usedrestaurantequipmentaz.com

ptaletvvrlptaletvvrl2018/09/14 20:58<a href="http://usedrestaurantequipmentaz.com">order cialis</a> buy generic cialis online safely http://usedrestaurantequipmentaz.com

ytaletqyqbytaletqyqb2018/09/14 22:47<a href="http://timsbmw.com">levitra 10mg reviews</a> free coupons for levitra http://timsbmw.com

ztaletekciztaletekci2018/09/14 23:41<a href="http://canadian-pharmaonline.com">buy viagra online canada</a> generic viagra price http://canadian-pharmaonline.com

ytaletqyrfytaletqyrf2018/09/15 00:03<a href="http://canadian-pharmasale.com">best online pharmacy for cialis</a> generic cialis online http://canadian-pharmasale.com

ytaletcvdtytaletcvdt2018/09/15 06:49<a href="http://valladium.com">cialis mail order india</a> generic cialis online canada http://valladium.com

ytaletldsnytaletldsn2018/09/15 08:45<a href="http://buycialisonlineglka.com">buy cialis</a> generic cialis pills http://buycialisonlineglka.com

etaletjwkeetaletjwke2018/09/15 17:43<a href="http://top-monterey-salinas-dentists.com">levitra indications</a> levitra vs cialis vs viagra reviews http://top-monterey-salinas-dentists.com

utaletikeyutaletikey2018/09/15 19:34<a href="http://gigawatt6.com">cialis for sale cheap</a> order cialis with no prescription http://gigawatt6.com

stalettsvgstalettsvg2018/09/16 01:37<a href="http://canadian-pharmabuy.com">cheap price viagra</a> buy viagra online http://canadian-pharmabuy.com

ntaletjelhntaletjelh2018/09/16 03:53<a href="http://usedrestaurantequipmentaz.com">cialis 100mg online</a> cialis 5 mg http://usedrestaurantequipmentaz.com

ktalethamlktalethaml2018/09/16 14:02<a href="http://missreplicawatches.com">order cialis</a> cheapest generic cialis http://missreplicawatches.com

xtaletttkvxtaletttkv2018/09/16 19:03<a href="http://missreplicawatches.com">buy cialis online with paypal</a> order cialis online with mastercard http://missreplicawatches.com

mtaletjmhpmtaletjmhp2018/09/16 21:47<a href="http://buyviagraonl1ne.us">canadian generic viagra</a> viagra online paypal http://buyviagraonl1ne.us

dtaletypomdtaletypom2018/09/16 22:42[url=http://canadian-pharmasale.com]order cheap cialis[/url] order cialis overnight delivery http://canadian-pharmasale.com

rtalettwucrtalettwuc2018/09/17 00:01<a href="http://buycialisonl1ne.us">order cialis online safe</a> buy cialis online cheap http://buycialisonl1ne.us

wtaletxryzwtaletxryz2018/09/17 07:15<a href="http://usedrestaurantequipmentaz.com">order cialis online in canada</a> order 5mg cialis online http://usedrestaurantequipmentaz.com

wtaletkavtwtaletkavt2018/09/17 07:47<a href="http://buyviagraonl1ne.us">mail order viagra uk</a> viagra online canada http://buyviagraonl1ne.us

staletzfbustaletzfbu2018/09/17 09:40<a href="http://bullsac.com">picture of levitra</a> difference between viagra cialis levitra http://bullsac.com

ytaletcawdytaletcawd2018/09/17 16:10<a href="http://buyviagraonl1ne.us">best online pharmacy for viagra</a> order viagra online india http://buyviagraonl1ne.us

otaletgimzotaletgimz2018/09/17 21:46<a href="http://missreplicawatches.com">cheap viagra cialis uk</a> cheap cialis pills online http://missreplicawatches.com

mtaletvtksmtaletvtks2018/09/18 00:53<a href="http://waltzweekend.com">discount viagra</a> order viagra today http://waltzweekend.com

gtaletqboygtaletqboy2018/09/18 02:09<a href="http://bullsac.com">levitra 10 mg</a> levitra used for http://bullsac.com

gtaletlzdlgtaletlzdl2018/09/18 12:32<a href="http://timsbmw.com">what do levitra pills look like</a> how much does levitra cost http://timsbmw.com

ataletiydqataletiydq2018/09/18 13:53<a href="http://canadian-pharmabuy.com">cheap viagra online</a> viagra online canadian pharmacy http://canadian-pharmabuy.com

ztaletmlwoztaletmlwo2018/09/18 17:30<a href="http://missreplicawatches.com">order cialis online safe</a> order cialis online cheap http://missreplicawatches.com

xtaleteagoxtaleteago2018/09/18 18:39<a href="http://vico4me.com">buy viagra in canada</a> generic viagra 100mg http://vico4me.com

ztaletfclaztaletfcla2018/09/18 23:05<a href="http://buycialisonl1ne.us">very cheap cialis</a> purchase cialis online http://buycialisonl1ne.us

2013-03-24Marathon Matchで上位目指すときの心構え

もうすぐ2013TCO marathonの予選が始まります。予選は全部で3roundあり、そのうち1回でも4位以内に入ればアメリカでのFinalに参加することができます(旅費も支給されます)。プログラム経験の少ない初心者でも、思考力さえあれば十分上位を狙えると思うので、是非参加してみるのがいいと思います。

以下はmarathon matchで上位を目指すための心構えについて、自分なりに現時点での考え方をまとめた物です。

勿論、人によってベストな参加方法は違うと思うので参考程度です。何か意見とかあれば教えてくれると嬉しいです。

1.問題の最も本質的な部分では妥協しない。

問題の根幹に関わるような部分で妥協すると、上位を目指すのが難しくなることが多いです。

例えば、2011 TCO Marathon Round1の問題(ImageScanner)を例に説明します。

リンク→ http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14502&pm=11367

方針は大きく二通りあると思います。

  1. スキャンする行は最初から決め手しまう。全て開いてしまってから、アルファベットを推測する。
  2. 最初は部分的にスキャンをして、その結果から、次にどこをスキャンするのが最適か順次考えてスキャンしていく。

実装するのも考えるのも、方法1が圧倒的に楽です。実際、本番でも方法2をとったのは1位のcolunさんだけだったと思います。

ついつい楽な方に逃げてしまいがちですが、肝心な部分で妥協すると1位とかを目指すのは厳しいと思います。

2・よく考える。無駄な実装をしない。慎重になる。焦らない。

「方針を思いついたら、何も考えずすぐに実装」というのはやりがちですが、時間の無駄遣いになりやすいです。

実装する前に、「この方針の長所と短所は何か?」、「この方針が失敗する可能性としては、どんなものが考えられるか?」、

といったことについてよく考えておくと、実装した後の次のステップにも移りやすいです。

特に短所(となる可能性のある部分)について、よくよく考察しておくのは大事だと思います。

3.根を詰めてやらない。気合と根性で乗り切ろうとしない。

この項目は2週間フル参加しようと思っている人以外は多分関係ないです。

コンテスト中は冷静さが大事です。

ついつい「コンテスト期間中は一秒たりとも無駄にしないぞ」とか意気込んだりしがちですが、

そんな緊迫した精神状態では判断ミスをしやすいです。

ただ闇雲に「実装したけど、やっぱり駄目だった」を繰り返すと、無駄に時間が過ぎていってしまいます。

それが原因でさらに自己嫌悪に陥ったりすると最悪です。

致命的なミスさえしなければ、2週間は結構長いです。マイペースで取り組むのがいいと思います。

睡眠不足でも思考力が鈍らないよって人以外は、睡眠も十分にとったほうがいいです。

utmathutmath2013/03/25 08:37気を付けます!

LiaCypeLiaCype2018/02/06 01:55Overnight Shipping On Viagra Pills <a href=http://tadalafbuy.com>cialis</a> Buying Cheap Flagyl Wholesale Kamagras Linea

LiaCypeLiaCype2018/02/17 04:12Acheter Viagra 50 Donde Comprar Cialis Sin Receta <a href=http://ciali5mg.com>online pharmacy</a> Find isotretinoin best website Propecia Male Fertility Baldness Viagra Online Australia

ColInenLyColInenLy2018/04/24 18:07Levitra Canada Price <a href=http://cialiviag.com>cialis for sale</a> Buy Discount Viagra Online

2012-07-07

SRM460Div1HARD(TheCitiesAndRoadsDivOne)

| 20:52

最初bit-dpかと思って苦労した。実際は20の分割数があまり大きくないことをつかうパターン。その意味で、TCO11WildCardのHardと似ている。http://topcoder.g.hatena.ne.jp/hirosegolf/20120612#1339488542。実行時間は適当に組んでも最悪ケースで100m程でかなり余裕がある。


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;

ll mod=1234567891;
struct mint{
	ll value;
	mint():value(0){}
	mint(ll v):value((v%mod+mod)%mod){}
};
mint& operator+=(mint&a, mint b){return a=a.value+b.value;}
mint& operator-=(mint&a, mint b){return a=a.value-b.value;}
mint& operator*=(mint&a, mint b){return a=a.value*b.value;}
mint operator+(mint a, mint b){return a+=b;}
mint operator-(mint a, mint b){return a-=b;}
mint operator*(mint a, mint b){return a*=b;}
mint operator-(mint a){return 0-a;}
bool operator==(mint a, mint b){return a.value==b.value;}
bool operator!=(mint a, mint b){return a.value!=b.value;}
 
 
std::ostream& operator<<(std::ostream& os, const mint& m){
return ( os << m.value );}
ll extgcd(ll a, ll b, ll &x, ll &y){
	ll d=a;
	if(b!=0){
		d=extgcd(b, a%b, y, x);
		y-=(a/b)*x;
	}
	else{
		x=1,y=0;
	}
	return d;
}
ll modinverse(ll a, ll b){
	ll x,y;
	ll d=extgcd(a,b, x, y);
	assert(d==1);
	return (x%b+b)%b;
}
mint& operator/=(mint&a, mint b){return a=a.value*modinverse(b.value,mod);}
mint operator/(mint a, mint b){return a/=b;}

mint p1, p2;

int n;
map<vi, mint> memo;
mint rec(vi a, int b){
	vi aa=a;
	aa.pb(b);
	if(EXIST(memo, aa)){
		return memo[aa];
	}
	mint &ret=memo[aa];
	mint ans=0;
	if(b==0){
		REP(i,a.size()) ans+=(a[i]-1)*(a[i]-2)/2*rec(a, 1);
	}
	REP(i1,a.size()) FOR(i2, i1+1, a.size()){
		vi na;
		REP(i,a.size()) if(i!=i1 && i!=i2) na.pb(a[i]);
		na.pb(a[i1]+a[i2]);
		sort(na.begin(), na.end());
		ans+=rec(na, b)*a[i1]*a[i2];
	}
	if(a.size()==1){
		if(b==0){
			ans+=p1;
		}
		else ans+=p2;
	}
	return ret=ans;
}

class TheCitiesAndRoadsDivOne {
public:
	int find(vector <string> m) {
		n=m.size();
		vi u;
		int b=0;
		int tot=0;
		{
	 
			vi par(n);
			REP(i,n)par[i]=i;
			REP(i,n) FOR(j,i+1,n) if(m[i][j]=='Y'){
				tot++;
				int t=par[j];
				if(t==par[i])b=1;
				REP(x,n) if(par[x]==t)par[x]=par[i];
			}
			map<int,int> z;
			REP(i,n) z[par[i]]++;
			EACH(pp,z){
				u.pb(pp->second);
			}
		}
		p1=1, p2=1;
		for(int k=1; k<=n-1-tot; k++) p1/=k;
		for(int k=1; k<=n-tot; k++) p2/=k;
		//deb(p1);
		//deb(p2);
		if(tot==n)p1=0;
		sort(u.begin(), u.end());
		//debug(b);
		//debug(u);
		memo.clear();
		int ans=rec(u,b).value;
		
		return ans;
	}
	

};

SRM519Div1HARD(VerySmoothDecomposition)

| 19:11

まず、最初に16以下の素数で割りまくる。この過程で既に計算量が2500^2を超えるので、定数倍に気をつけて実装しなくてはいけない問題だと気づく。この手の問題は16以下の素数にどんなものが存在するかきちんと調べることが必要。最悪ケースのテストを作りにくいので、定数倍に細心の注意を払いながら実装する。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;

int mod=1000000009;
int b[2600];

class VerySmoothDecompositions {
public:
	int solve(vector <string> digits) {
		vi bs;		
		REP(i,digits.size()){
			REP(j,digits[i].size()){
				bs.pb(digits[i][j]-'0');
			}
		}
		int ps[6]={2,3,5,7,11,13};
		vi cnt(6);
		vi nbs(bs.size());
		REP(ip,6){
			int p=ps[ip], rem=0;
			while(true){
				REP(i,bs.size()){
					nbs[i]=(rem+bs[i])/p;
					rem=(rem+bs[i])%p*10;
				}
				if(rem!=0)break;
				REP(i,bs.size()) bs[i]=nbs[i];
				cnt[ip]++;
			}
		}
		{
			int tot=0;
			REP(i,bs.size()) tot+=bs[i];
			if(tot!=1)return 0;
		}
		//debug(cnt);
		int m2=cnt[0], m3=cnt[1];
		vvi g(m2+1, vi(m3+1));
		g[m2][m3]=1;
		int d[8]={2,3,4,6,8,9,12,16};
		REP(ii,8){
			int n=d[ii];
			int c2=0, c3=0;
			while(n%2==0){
				n/=2;
				c2++;
			}
			while(n%3==0){
				n/=3;
				c3++;
			}
			for(int i2=m2; i2>=c2; i2--){
				for(int i3=m3; i3>=c3; i3--){
					g[i2-c2][i3-c3]+=g[i2][i3];
					if(g[i2-c2][i3-c3]>=mod)g[i2-c2][i3-c3]-=mod;
				}
			}
		}
		ll ans=0;
		for(int i2=0; i2<=m2; i2++) for(int i3=0; i3<=m3 && i3<=cnt[2]; i3++){
				int n5=cnt[2]-i3, n7=cnt[3];
				if(n5+n7<i2)break;
				ans+=(ll)(min(n5, i2) - max(0,i2-n7) + 1) * g[i2][i3];
				ans%=mod;
			}
		
		return ans;
	}
	

};

SRM523Div1HARD(AlphabetPaths)

| 11:14

各マスを中心に両側探索を行う。最悪計算量の見積もりが難しい。

441*3^10なので時間的に結構ぎりぎり。このようなタイプの問題だと、最悪のケースをテストしながら高速化していくのが定石だと思っているが、最悪ケースを作るのが難しいのでとてもやっかい。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;



int maze[30][30];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int ind;
int cnt[1<<21];
int hist[1<<21];
ll ans;
int target;
void rec(int x, int y, int rem, int b){
	//deb(x);deb(y);deb(rem);deb(b);debl;
	if(rem==0){
		if(hist[b]!=ind){
			hist[b]=ind;
			cnt[b]=0;
		}
		cnt[b]++;
		int rev_b=target^b;
		//debug(rev_b);
		if(hist[rev_b]==ind){
			ans+=cnt[rev_b];
		}
		return;
	}
	REP(r,4){
		int nx=x+dx[r], ny=y+dy[r];
		if((b|maze[nx][ny])!=b){
			rec(nx,ny,rem-1,b|maze[nx][ny]);
		}
	}
	return;
}

class AlphabetPaths {
public:
	long long count(vector <string> letterMaze) {
		int mx=letterMaze.size();
		int my=letterMaze[0].size();
		string s="ABCDEFZHIKLMNOPQRSTVX";
		clr(maze);
		clr(hist);
		ind=1;		
		REP(x, mx){
			REP(y,my){
				REP(i, s.size()){
					if(letterMaze[x][y]==s[i])maze[x+1][y+1]=1<<i;
				}
			}
		}
		ans=0;
		REP(x,mx+1) REP(y, my+1){
			ind++;
			if(maze[x][y]){
				target=(1<<21)-1-maze[x][y];
				rec(x,y,10,maze[x][y]);
			}
		}
		return 2*ans;
	}
	

};

2012-07-06

SRM526.5(MagicMatchGame)

| 12:19

単に合計を最大にするだけなら、普通に貪欲法を使えばいいが、R*Bを最大化したいので工夫が必要。正の数x,yに対して、x*R+y*Bを最大化すれば、(x,y)の値によってはR*Bが最大となるようなR,Bが得られる。(x,y)の組み合わせを全て確かめるのは不可能だが、実際には(x,y)によって選択肢が分かれるような境界でだけ調べればいいので、実際に調べる必要(x,y)の組は高々50^2だけ。これ以外の問題でもR*R+B*Bを最大化したい場合とか、考え方自体は応用が広そう。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define pb push_back


using namespace std;


typedef vector<int> vi;
typedef long long ll;

int n;
bool ind(vi &z){
	int r=0;
	for(int i=0;i<20;i++){
		int v=-1;
		for(int k=0;k<z.size();k++){
			if((z[k]>>i)%2==1){
				if(v==-1){
					v=z[k];
					r++;
				}
				z[k]^=v;
			}
		}
	}
	//debug(z);
	//debug(r);
	return r==z.size();
}

vi red, blue;
ll wr,wb;
bool cmp(int i, int j){
	return wr*red[i]+wb*blue[i]<wr*red[j]+wb*blue[j];
}

class MagicMatchesGame {
public:
	long long minimumArea(vector <int> matches, vector <int> _red, vector <int> _blue) {
		long long ans=-1;
		red=_red, blue=_blue;
		vi z;
		for(int c=0;;c++){
			bool ok=false;
			for(int i=0;i<matches.size();i++){
				vi nz(z.begin(), z.end());
				nz.pb(matches[i]);
				if(ind(nz)){
					ok=true;
					z.pb(matches[i]);
					break;
				}
			}
			//debug(z);
			if(!ok){
				n=z.size();
				break;
			}
		}
		//debug(n);
		vi wrs, wbs;
		for(int i1=0;i1<red.size(); i1++){
			for(int i2=i1;i2<red.size();i2++){
				wbs.pb(abs(red[i2]-red[i1]));
				wrs.pb(abs(blue[i2]-blue[i1]));
			}
		}
		wbs.pb(1);wrs.pb(0);
		wbs.pb(0);wrs.pb(1);
	
		if(1){
			for(int iw=0;iw<wrs.size();iw++){
				wr=wrs[iw];
				wb=wbs[iw];
				z.clear();
				vi prio(matches.size());
				for(int i=0;i<matches.size();i++)prio[i]=i;
				sort(prio.begin(), prio.end(),cmp);
				int sr=0, sb=0;
				for(int ip=0;ip<matches.size();ip++){
					int i=prio[ip];
					vi nz(z.begin(), z.end());
					nz.pb(matches[i]);
					if(ind(nz)){
						z.pb(matches[i]);
						sr+=red[i];
						sb+=blue[i];
					}
				}
				ll nans=(ll)sr*sb;
				if(ans==-1 || nans<ans){
					ans=nans;
				}
			}
		}
		return ans;
	}
};

SRM535Div1HARD(FoxAndGreed)

| 11:42

母関数を使って紙の上で計算すれば、計算量は相当落ちる。やってみないと解けるかどうか分からない感じの問題。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// BEGIN CUT HERE
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE


typedef long long ll;

// BEGIN CUT HERE

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

ll mod=10007;

ll extgcd(ll a, ll b, ll &x, ll &y){
  ll d=a;
  if(b!=0){
    d=extgcd(b, a%b, y, x);
    y-=(a/b)*x;
  }
  else{
    x=1,y=0;
  }
  return d;
}
 
ll modinverse(ll a, ll b){
  ll x,y;
  extgcd(a,b, x, y);
  return (x%b+b)%b;
}
 
 
struct modular{
  ll value;
  modular(){
    value=0;
  }
  modular(ll v){
    value=(v%mod+mod)%mod;
  }
  modular operator+(const modular b){
    return modular(value+b.value);
  }
  modular operator-(const modular b){
    return modular( value-b.value );
  }
  modular operator*(const modular b){
    return modular( value*b.value );
  }
  modular operator/(const modular b){
    return modular( value*modinverse(b.value, mod) );
  }
};
 
modular operator+(ll a, modular b){
  return modular(a)+b;
}
modular operator-(ll a, modular b){
  return modular(a)-b;
}
modular operator*(ll a, modular b){
  return modular(a)*b;
}
modular operator/(ll a, modular b){
  return modular(a)/b;
}

typedef vector<modular> vm;
ll H, W, S;

vm fact;
modular powm(modular a, ll n){
	if(n==0)return 1;
	if(n%2==0)return powm(a*a,n/2);
	return a*powm(a*a, n/2);
}

modular calA(ll m, ll n){
	if(n<0)return 0;
	assert(m>=0);
	if(m==0)return(n==0 ? 1 : 0);
	return fact[n+m-1]/fact[n]/fact[m-1];
}

modular cal(ll x,ll y){
	return calA(H+W-2+x+y, S-x) * powm(S+1, H*W-(H+W-1)-(x+y));
}

class FoxAndGreed {
public:
	int count(int _H, int _W, int _S) {
	fact=vm(10000);
	fact[0]=1;
	FOR(i,1,fact.size()){
		fact[i]=fact[i-1]*i;
	}
	H=_H;
	W=_W;
	S=_S;
	if(H==1 && W==1){
		if(S==0)return 1;
		else return 0;
	}
	modular ans=0;
	//deb(H);deb(W);debl;
	vector<vm> a(H,vm(W));
	a[0][0]=1;
	REP(x,H-1) REP(y,W-1){
		a[x+1][y]=a[x+1][y]+a[x][y];
		a[x][y+1]=a[x][y+1]+a[x][y];
	}
	REP(x,H) REP(y,W) if(x!=H-1 || y!=W-1) if(x==H-1 || y==W-1){
		//deb(x);deb(y);deb(a[x][y].value);debl;
		ans=ans+a[x][y]*cal(x,y);
	}

    return ans.value;
  }
}

SRM536Div1HARD(BinaryPolynomialDivOne)

| 11:34

多項式をmod pでp乗したときの振る舞いを知っていれば難しくない。

本番ではバグを出して再提出になってしまった。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// BEGIN CUT HERE
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
// BEGIN CUT HERE

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

class BinaryPolynomialDivOne {
public:
	int findCoefficient(vector <int> a, long long m, long long k) {
		map<ll,ll> z;
		z[0]=1;
		REP(i,62){
			if((m>>i)%2==1){
				map<ll,ll> nz;
				EACH(p,z){
					for(ll j=0; j<a.size(); j++){
						if(a[j]){
							ll t=p->first+(j<<i);
							if(t<=k && (k-t)%(1LL<<(i+1))==0){
								nz[t]+=p->second;
								nz[t]%=2;
							}
						}
					}
				}
				z=nz;
				//debug(z);
			}
		}
		//debug(z);
		int ans=z[k]%2;
		
		return ans;
	}
}

SRM537Div1HARD(PrinceXDominoes)

| 11:25

有向グラフ上で元の場所に戻る一筆書きを行うためには各頂点の入次数と出次数が等しくなくてはいけない(あと連結性)。各頂点の入次数と出次数が等しくなるように辺を取り除く行為は、出次数が多い頂点から入次数が多い頂点へフローを流す行為と対応することが分かる。なので最小費用流を用いれば答えが得られる。

nt

SRM539Div1HARD(FoxBomb)

| 11:11

本番とおした人のコードを参考に書いた。貪欲的な方法で解ける。

『まずフィールド全体を爆弾で埋める。問題文からフィールドは木構造になっているので、葉のほうから順に取り除き可能な爆弾を取り除いていく。』

言葉で適当にいうとたったこれだけの解法。シンプルかつ実装が簡単で一般性もある、かなり強力な解法だと思う。Editorial見る限り模範解答はdpでこの解法じゃなかったのが少し驚き。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define nclr(a) memset((a),-1,sizeof(a))
#define clr(a) memset((a),0,sizeof(a))
#define pb push_back
// BEGIN CUT HERE

#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
// BEGIN CUT HERE
typedef long long ll;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE


int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

class FoxBomb {
public:
vi xs,ys;
vvi g;
int check[60][60];
int cnt[60][60];

	void put(int x, int y, int v){
		cnt[x][y]+=v;
		REP(r,4){
			for(int k=1;;k++){
				int x2=x+k*dx[r], y2=y+k*dy[r];
				if(g[x2][y2]==0)break;
				cnt[x2][y2]+=v;
			}
		}
	}
	
	bool pullable(int x, int y){
		if(cnt[x][y]==1)return false;
		REP(r,4){
			for(int k=1;;k++){
				int x2=x+k*dx[r], y2=y+k*dy[r];
				if(g[x2][y2]==0)break;
				if(cnt[x2][y2]==1)return false;
			}
		}
		return true;
	}

	void dfs(int x, int y){
		if(g[x][y]==0 || check[x][y]==1)return;
		check[x][y]=1;
		REP(r,4){
			int x2=x+dx[r], y2=y+dy[r];
			dfs(x2,y2);
		}
		xs.pb(x);
		ys.pb(y);
	}
	
	int getMinimumCost(vector <string> grid) {
		clr(check);
		clr(cnt);
		xs.clear(), ys.clear();
		g.clear();
		{
			int n=grid.size();
			int m=grid[0].size();
			g=vvi(n+2, vi(m+2));
			REP(i,n) REP(j,m){
				if(grid[i][j]=='.')g[i+1][j+1]=1;
			}
		}
		pii root;
		REP(i,g.size()) REP(j,g[i].size()){
			if(g[i][j]==1)root=pii(i,j);
		}

		dfs(root.first, root.second);
		int ans=0;
		REP(i,xs.size()){
			put(xs[i], ys[i], 1);
			ans++;
		}
		REP(i,xs.size()){
			if(pullable(xs[i], ys[i])){
				ans--;
				put(xs[i], ys[i], -1);
			}
		}
		
		return ans;
	}

SRM540Div1HARD(ProductQuery)

| 11:02

考え方自体はさほど難しいものではないけど、複数の要素が絡んでいて実装に苦労する。

stant

SRM541Div1HARD(XorLife)

| 10:52

時間が2ステップ進む時の様子をみると繰り返し二乗法が使えることが分かる。アイデアが殆ど全ての問題。5倍していくイメージの解法の誘惑が結構強くて正しい解法にたどり着くのに時間がかかってしまう。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// BEGIN CUT HERE
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
// BEGIN CUT HERE

typedef pair<int,int> pii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

map<pair<vvi,ll>, ll> memo;

ll f(const vvi &field, ll m){
	//debug(m);
	//debug(field);
	pair<vvi,ll> a(field,m);
	if(EXIST(memo,a)){
		return memo[a];
	}
	ll &ret=memo[a];
	if(field.size()==0)return 0;
	if(field[0].size()==0)return 0;

	if(m==0){
		ll cnt=0;
		REP(i,field.size()) REP(j,field[i].size())cnt+=field[i][j];
		//debug(field);
		//debug(cnt);
		return ret=cnt;
	}
	if(m%2==1){
		int xs,ys;
		xs=field.size()+2;
		ys=field[0].size()+2;
		vvi new_field(xs,vi(ys));
		REP(x,xs-2) REP(y,ys-2) if(field[x][y]==1){
			new_field[x][y+1]++;
			new_field[x+1][y]++;
			new_field[x+2][y+1]++;
			new_field[x+1][y+2]++;
			new_field[x+1][y+1]++;
		}
		REP(x,xs) REP(y,ys) new_field[x][y]%=2;
		return ret=f(new_field, m-1);
	}
	else{
		int xs=field.size();
		int ys=field[0].size();
		vvi new_field[2][2];
		REP(i,2) REP(j,2) new_field[i][j]=vvi( (xs+1)/2, vi( (ys+1)/2) );
		REP(x,xs) REP(y,ys) if(field[x][y]){
			new_field[x%2][y%2][x/2][y/2]=1;
		}
		ll ans=0;
		REP(i,2) REP(j,2) ans+=f(new_field[i][j], m/2);
		return ret=ans;
	}
	return 0;
	
}

class XorLife {
public:
	long long countAliveCells(vector <string> _field, int K) {
		memo.clear();
		vvi field(_field.size(), vi(_field[0].size()));
		REP(x,field.size()) REP(y,field[x].size()) if(_field[x][y]=='o')field[x][y]=1;
		//debug(field);
		//debug(K);
		long long ans=f(field,K);
		
		return ans;
	}

SRM544Div1HARD(SplittingFoxes)

| 10:40

行列冪乗タイプの問題。

違う方向を向いているFoxも同等に扱えるのが実装を簡潔にする最大のポイント。

次のような式をノートに書くと分かりやすいかなと思った。

(→, x, y) ⇒
S(→, x+1, y) + L(↑, x, y) + R(↓, x, y)
= S(→, x+1, y) - L(→, y, -x) - R(→, -y, x)

N: 1の和(総数)
X: xの和
Y: yの和
XY: xyの和 として(N,X,Y,XY)を並べたものを考えると
next(N)  = (S-L-R)N
next(X)  = S(x+1) - Ly + Ry = SN + SX + (-L+R)Y
next(Y)  = S(y+1) + Lx - Rx = SN + (L-R)X + SY
next(XY) = S(x+1)y + Lxy + Rxy = SY + (S+L+R)XY

あと、enum{N,X,Y,XY}; って書くと順に0,1,2,3が入るらしい。よく分かってないけど。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;

ll S,L,R;

ll mod=1000000007;
struct mint{
	ll value;
	mint():value(0){}
	mint(ll v):value((v%mod+mod)%mod){}
};
mint& operator+=(mint&a, mint b){return a=a.value+b.value;}
mint& operator-=(mint&a, mint b){return a=a.value-b.value;}
mint& operator*=(mint&a, mint b){return a=a.value*b.value;}
mint operator+(mint a, mint b){return a+=b;}
mint operator-(mint a, mint b){return a-=b;}
mint operator*(mint a, mint b){return a*=b;}
mint operator-(mint a){return 0-a;}
//bool operator==(mint a, mint b){return a.value==b.value;}
//bool operator!=(mint a, mint b){return a.value!=b.value;}

/*
std::ostream& operator<<(std::ostream& os, const mint& m){
return ( os << m.value );}
ll extgcd(ll a, ll b, ll &x, ll &y){
	ll d=a;
	if(b!=0){
		d=extgcd(b, a%b, y, x);
		y-=(a/b)*x;
	}
	else{
		x=1,y=0;
	}
	return d;
}
ll modinverse(ll a, ll b){
	ll x,y;
	extgcd(a,b, x, y);
	return (x%b+b)%b;
}
mint& operator/=(mint&a, mint b){return a=a.value*modinverse(b.value,mod);}
mint operator/(mint a, mint b){return a/=b;}
*/


template <typename T> struct matrix : vector<vector<T > >{
	matrix(int n){
		vector<vector<T> >::clear();
		resize(n, vector<T>(n) );
		REP(i,n) (*this)[i][i]=1;
	}
	matrix(int n, int m){
		vector<vector<T> >::clear();
		resize(n, vector<T>(m) ); 
	}
	matrix<T> operator*(const matrix<T> &b){
		int n1=this->size(), n2=b.size(), n3=b[0].size();
		assert(this->size()==n2);
		matrix<T> ret(n1,n3);
		REP(i,n1) REP(j,n3) REP(k,n2) ret[i][j]=ret[i][j]+(*this)[i][k]*b[k][j];
		return ret;
	}
	matrix<T> pow(ll n){
		int m=this->size();
		assert((*this)[0].size()==m);
		return pow2(matrix<T>(m) ,n);
	}
	matrix<T> pow2(matrix t, ll n){
		if(n==0)return t;
		if(n%2==0)return ((*this)*(*this)).pow2( t, n/2);
		else return ((*this)*(*this)).pow2 ((*this)*t, n/2);
	}
	/*T det(){
		int n=this->size();
		vector<vector<T> >x;
		REP(i,n) x.pb((*this)[i]);
		T h=1;
		REP(i,n){
			FOR(j,i,n){
				if(x[j][i]!=0 && j!=i){
					REP(k,n)swap(x[j][k], x[i][k]);
					h*=-1;
					break;
				}
			}
			if(x[i][i]==0)return 0;
			T v=1/x[i][i];
			h=h*x[i][i];
			FOR(j,i+1,n){
				T v2=v*x[j][i];
				REP(k,n) x[j][k]=x[j][k]-x[i][k]*v2;
			}
		}
		return h;
	}*/
};

class SplittingFoxes {
public:
	int sum(long long n, ll _S, ll _L, ll _R) {
		mint S=_S, L=_L, R=_R;
		matrix<mint> a(4,4);
		enum{N,X,Y,XY};
		a[N][N]=S-L-R;
		
		a[XY][XY]=S+L+R;
		a[XY][Y]=S;
		
		a[X][N]=S;
		a[X][X]=S;
		a[X][Y]=-L+R;
		
		a[Y][Y]=S;
		a[Y][X]=L-R;
		//debug(a);
		//debug(a.pow(n));
		int ans=a.pow(n)[XY][N].value;
		
		return ans;
	}
};

2012-06-12

TCO11WildCardHARD(PermutationBias)

| 17:09

置換の状態数は分割数に一致するが、35番目の分割数が意外と小さく(20000程度)、愚直なdpでも何とかなる事に気付けるかどうかがポイント。計算を工夫しないとTLEしてしまう。このような計算量を把握しにくい解法で解く時は、普段の「要求される計算量→解法を考える」から、「計算速度をとにかく早くする」に発想を切り替えたほうがいい気がしている。この種の問題、あんまり見ないから練習が難しい。