tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

2019年の目標

"一年は目標に始まり反省に終わる。"
  ーー Tozan Southerpacks

書きなぐりと言われても否定できませんが、今年の目標も書いていきましょう。全然意識してないから達成できないんだという話はしてはいけません。

競技プログラミング

枠の数が正常のオンサイトに出る

これは毎年の目標。

なんか大会で優勝する

これも毎年の目標。

writerだったりtesterだったり、選手以外としての活動をもっと幅広くやってお金儲けす

ついにこういう目標を立ててしまうくらい歳をとった。廃れたTopCoderは狙いどきだろうからやっていきたい所存。

お勉強

研究

がんばろう(論文を書け)

言語

英語

TOEFL, GREを困らない程度に。今年はYoutubeチャンネルくらいしかやらないと思う

タタール

タタール語オリンピック、本選いけたら賞を狙う

フランス語

DELF B2になんとか合格できそうなレベルを目指す

他の言語

アメリカ先住民言語を何かしら(たぶんクリー語)真面目にやる。アゼルバイジャン語を街を歩ける程度にやる。

市町村系

都道府県到達コンプリート

秋田県富山県、石川県、福井県和歌山県鳥取県島根県長崎県が残り。案外厳しいね

23区街歩き

都バス、町名めぐり

その他

Youtubeチャンネル

チャンネル再開予定というビデオをこの前投稿したけど、もっといろいろなものを投稿する

オタク活動🐺

お金に困ってないからもっと積極的に外に出よう。これは英語を練習する一環でもある。2018年のペースで絵を描く

2018年の反省

"一年は、目標に始まり、反省に終わる。"
  ーー Tozan Southerpacks

冗談はさておき、半ば無茶振りのような今年の目標を一つ一つ振り返っていきましょう。

競技プログラミング

枠の数が正常のオンサイトに出る

二流プログラマーでした、今年はDよりGの方がオンサイトが近かった。Fは例によって運ゲーすぎるな。

なんか大会で優勝する

(え、DPC?) そもそも企業コンに出られた回数が少ない時点で結構厳しかったのですが、未だに企業コンの問題の質はあれなので狙いようはまだまだありますね。

天才以外お断り問題たちに光明を見つける

多分ズルテク磨いたほうが早くて、開幕即実験コードやOEIS探索はためらわずにバンバンやるべき。既出論文サーチはだいたい無意味なのでやらないのがよい。他は常人にどうにかなるものではない。私からは以上です。

お勉強

研究

全然進んでないんですよね。でもいろいろ持ち帰るものは持ち帰れそうなので慌てて論文書く人になります。
Math Biol. がやりたいです(それか数え上げ的なアルゴリズム)

英語

一年間毎日 #毎日Awoo をやり続けた。というかあと1回。
ひとまず研究生活は困らなさそうね。TOEFLの点数稼ぎは全くもって別のゲームなので心して取り掛かる必要性はあると思う(じゃあ大学は何を見るためにTOEFLの点数を提出させているんだ?)
writingは練習のしようがないのがかなり難しい。見てくれる人もいないしなあ。どうすりゃいいんだろう。

他の言語

タタール語オリンピック、本選いけるかな?*1 予選は相当点数取れたんだけども。
フランス語はもっと頑張りたいな

市町村系

また変な場所を目指して旅に出る

東北・北海道・九州・エドモントンウィニペグに行った。奈良に行くついでに帰りにまた在来線に乗って豊橋とか行ってみた。
いいかげんもう札幌は見るものがなくなってきた。けどあのただひたすら大量の信号が並んでいる街並みが好き。

🐺

🐺

これに関しては、日本国内外に世界が広がる一年だった。特に日本国内のぶんは大きい。

まとめ

なんかスキルセットがオールラウンダーみたいになってきてしまっている。マズイ老化だ。

*1:本選いけたら今度はロシア語が全くわからないのにロシアのイベントに参加する変な人になってしまう

ロシア語を知らずにタタール語を勉強するには

*1

これの24日目

Исәнмесез, みなさんこんにちは、tozangezanです。競技プログラマーとしての存在ばかり知られていますが、言語も好きなので言語の話をします。というかタタール語の話をします。

先日、タタール語オリンピックのオンライン予選に参加しました。本当はこの大会の問題についてとかを書きたかったんですけど、残念ながらまだこの記事を公開するときもコンテスト期間中なので、残念ながらできません。しかしどうやって勉強したかとかなら問題なく書けるので、そんなことにしたいと思います。

よくこういう話があります。タタール語を勉強したいけど、ロシア語がわからないから無理!」 はい。タタール語に関しては多くの場合ロシア語で書かれているので、ロシア語を知らない場合はタタール語を勉強する難易度が跳ね上がります(言語の習得難易度というのは、言語そのものの難易度だけではなくその言語を勉強するための媒体のアクセスしやすさなどもかなり大きい要素です)。しかし、ロシア語がわからないと無理か?と言われると、そうでもないようです。まあこれは必死に調べた結果の産物みたいなところはあるんですけども。

入門編

以下に挙げるものは、タタール語に入門する上でかなり有用なもので、なおかつロシア語を知らずとも使えるものです。

tat-inform-aqbars.blogspot.com
日本語で書かれたタタール語入門記事ですが、かなり細かいところまで触れられているので、一度通して勉強した後もなんども見返すのにいいサイトです。
文法の概要をつかむのに一番良いと思います。

https://anatele.ef.comanatele.ef.com
有名でかなり大規模な対話型のタタール語学習サイトです。英語で進めることができます。おそらく本来この手のサイトは有料で、それを代わりに共和国政府かどこかが肩代わりしているような気がします。そのため、登録できれば無料で使い放題なんですが、時々登録する枠がなくなります。
例によって言語に慣れるのにはかなり適していますが、分量が多すぎるのでずっとやってると飽きます。
スピーキング練習としてオンラインで先生と会話できるみたいな機能もついていたのですが、最近停止してしまい使えません。

https://et2.ef-cdn.com/EtownResources/anat-tele-grammar/1.4/en/index.htmlet2.ef-cdn.com
↑のサイトからたどり着ける場所で本当は外から見れたらまずいと思うんですが、見えるので仕方がありません。
英語で書かれた文法の説明でもっとも詳しいです。例文が大量にあり、暗記して使えます。

辞書

以下、ロシア語のものもありますが、Google 翻訳だけで十分対処できます。ただし、日本語に翻訳しても英語の結果をカタカナ転写しただけのものばかりが得られるので、英語に翻訳するに止めたほうが無難です。

https://tatar_russian.academic.ru/tatar_russian.academic.ru
かなり大きい辞書です。他にもロシア語→タタール語やタタール語→ロシア語があります。ただし、多義語のどの意味かを探すには候補が多すぎて困ります。
動詞を引くときは動名詞の形で

ロシア語版Wiktionary
こっちのほうがお手軽に使えます。コンパクトなので用例とかはないです。
動詞を引くときは不定形で

tt.oxforddictionaries.com
英語→タタール語が結構使えます。ロシア語を介さなくてよいので便利です。逆は、収録語数が少なすぎて入門者にも向いていません。

メディア

インプットの練習に。知らない単語を調べ次第ankiに追加するのが良いでしょう。

tatar-inform.tatar
記事が短い上、ロシア語からの借用語を遠慮せずに使っているので読みやすいです。地元のニュースが多めです。

www.azatliq.org
長めの記事が多めで、記事としてはもっと高度な話をしています。ロシア語からの借用語がかなり少なく、難しいです。

http://tnv.ru/tat/tnv.ru
タタール語のテレビ局です。ニュースもあればドキュメンタリーもあれば多分子供向け番組とかもあります。スポーツ実況もやっています(が、このサイトから見ることができなかったりします)。
タタール語のリスニングのいい練習になるかと思います。日本からのタタール語オリンピック参加者が出演したことがあるようです。
リンクを押すと急に設定がロシア語に戻ったりするのでサイト内で迷子にならないよう気をつけてください。

その他

話には聞くけどあまり積極的に使ってないソース。

play.google.com
実は、ANA TELEの代わりにこれが一番練習になるかもしれません。Google Playストアで買える(東京のロシア書籍専門店、ナウカでも買える?)本ですが、これはコンテンツの立派さと英語・ロシア語併記が徹底されているにもかかわらず激安なので、とりあえずこれを最初に買ってみて勉強してはいかがでしょうか。

www.azatliq.org
画像にロシア語が入っているとどうしようもないというのが困りどころです。しかし、文章を読む練習記事みたいなのは、勉強になると思います。

Nicholas Poppe: Tatar Manual
英語で書かれたタタール語の文法書は、実は本になっているものがあります。先日アルバータ大学で実物を見つけましたが、ANA TELEのGrammar Labより詳しくはなさそうでした。

tat-inform-aqbars.blogspot.com
ここも参考にしてください。

実践練習

VK
タタール語を使う人は結構たくさんいます。

自分の日課

ANA TELE文法の例文集をAnkiに詰めて、英語→タタール語を毎日しています。
出会った知らない単語を調べたらこれもAnkiに追加しています。
単語に出会うために、tatar-informやazatliqの記事を読んだりしています。
ANA TELEの練習もニュースとは方向性の違う日常生活向けの語彙が手に入っていいと思います。

まとめ

タタール語を勉強するのは難しくありません。
ロシア語を知らずとも十分資料はあるのです。


いろいろな言語に手を出してみたいみなさん、
とりあえず音楽や動画に触れてみてください。

Сау булыгыз!

*1:The 言語 Advent Calendar 2018

海外のICPC練習会とは

これの24日目

こんにちは。tozangezanです。みなさんご存知ですか? あの典型問題の多いコンテストではいつも序盤で上位にくるにもかかわらず、AGCになった途端に全然問題が解けなくなる人です。そんなことはどうでもいいんですが、今回は無気力で書ける記事を目指していきたいので、読者の皆様は辛抱してご解読ください。

今、ブログ記事をアルバータ州エドモントンから書いています(寒い...)。下書き保存して、投稿するときにはマニトバ州ウィニペグにいると思います(もっと寒いっぽい...)。
Twitterのみなさんは変な活動時間から気づいているかもしれませんが、実ば9月からカナダに来ています。*1L'Université de la Colombie-Britannique、もといUniversity of British Columbiaとかいうところに交換留学に来ています。そろそろ帰ります。

実はこの学校、北米の Pacific Northwest Regional で今年優勝しています*2。知っていましたか? いや知らないですよね。NEERCならまだしも、アメリカのRegional事情をわざわざ調べるような日本のICPC参加者がいるとは到底思えません。今回は、そんな大学でどんな練習会が行われているかを取り上げていきたいと思います。

練習会がどういう感じなのか手っ取り早く知る方法は、ここにアクセスすることです。

そもそもどうやって練習会の存在を知ったの

ググったら出てきました。もう現役ですらないのに乱入しました。

どんな練習をしてるの

だいたい週に2回、水曜日と土曜日に練習会があります。水曜日は3時間くらいの個人参加のバーチャルコンテストで、難易度はかなりまちまちです。たまにRegionalとかPetrozavodskとかある一方CFのDiv3とかがあります(30分くらいで全完したあと暇だった)。土曜日はチーム練習ということになっていて、だいたいRegionalを5時間でやっています。一方ICPC現役を引退して日本から遊びに来た人は個人で3人チームに立ち向かいます。
この練習会のもっとも大事なこととして、ピザが無料で食べられます。多分結構な人数は無料でピザを食べるために練習会に来ています。無論僕も例外ではない。
結構な頻度でハワイアンピザがありますが、ハワイアンピザは実はカナダ発祥なんですね。どうりでよく見るわけです。(参考)
一通り終わったら誰かが解いた問題を順に解説していく感じです。これはどこもそうなんじゃないですかね。

レベルは如何に

問題は、だいたいRegionalみたいなものが選ばれます。このRegionalの質というのもかなり地域によるっぽくて、正直アメリカのセットはつまらないです。これでよくあれだけの参加者を確保できているなあと関心するレベルです。
参加者のレベルは、CFのオレンジが少しいて、紫が結構いるような感じで、僕のレベルと上位チームのレベルが同じくらいとかだと思います。

チームの決め方

ICPCのチームを決めるのに独自のコンテストを開いていて、そこでの上位をうまく選んでチームを作っているらしく、testerをすることになりました。間違いを2箇所指摘し、writerがsolを作るのを放棄して僕のコードをそのまま写したようなものにしたら僕のコードも間違っててリジャッジとかいう意味不明な事態になったので、問題を準備する人はこんなことにはならないよう気をつけてください。
ICPCに出てない人たちがどうしているのかは不明です。そもそも初心者みたいな人もよく来るのですが、そういう人たちがいきなりRegionalやって何を解くのかも不明です。

ところで僕は何をしていたのか

普通に一人で参加してました。たいていの場合は一人でやっても勝てるけど、そこはあまり重要ではなくて、解ける問題の集合が同じことはかなり多いんですね。あの典型問題の多いコンテストではいつも序盤で上位にくるにもかかわらず、AGCになった途端に全然問題が解けなくなる人の再来です。僕はやる気もないしもう参加できるICPCも残ってないのでわざわざ練習後に各自で何時間もデバッグしたり嘘解法を無理やり通そうとする気力はないんですけど、やってる人はやってました。あとピザをたくさん食べました。
問題の解説に関しては、たいてい他の人が誰も解けなかった難問を解説しました。ホワイトボードで解法を説明するのは結構難しいです。プログラミングコンテストの問題で使われる英語と、プログラミングコンテストの解説で使われる英語が違うことは、片方やったことない人(さらには両方ともやったことない人)でもわかると思います。問題設定は大概の場合は比較的単純な説明でできるんですよね、だって問題文だってよほどクソでない限りストーリーをつけて現実っぽく見せたりできるじゃないですか。反面解説は数学的な言葉を使うだけなので、別の慣れが要求されます。まあ、いずれにせよなんとかなったと思います。

その他

結局のところ、週2回練習をしてたら相当な時間になると思うのですが*3、それでもやっぱり紫とかオレンジくらいなんですよね。(オレンジコーダーの人は中国からの留学生です)。日本でも同じような傾向だとは思うのですが、大学から始める人をかなりいい環境で積極的に育てても、よほどの大当たりみたいな人材でもない限りIOIの人たちがわんさかいる場所に追いつくのは困難です。今回のいい例はMITで、彼らは間違いなく今年の北米最強チームですが、そんな彼らも以前からの超有名人たちがたまたまその大学に入っただけみたいな感じです。
これは特に東大に関して言えるのかもしれませんが、特に行くことそのものに対する利益がないと、上位の人たちにとってはたいして面白くもない問題セットをやらされて解法を説明するボランティア活動をすることになって行かなくなって、それに従って上位ではない人たちもわざわざそういう環境で練習する意味がなくなるという悪循環を生むのではないかと思います。そこでピザを毎週支給するのはかなりいいアイデアだと思いますね*4。ちなみにこのピザは研究費の予算から出ています。東京大学さん!!!!!!聞こえてますか!!!!!!

写真

f:id:tozangezan:20181121181719j:plain
f:id:tozangezan:20181212181301j:plain
f:id:tozangezan:20181121190838j:plain

*1:正確には8/31

*2:どうでもいいけど、IOI界隈では有名な Richard Peng 氏が唐突に僕にICPC関連のメール送ってきて、東大の代表だと思われてんのかな?と思ってたら違って、「今年強いから君がUBCのコーチやってんのかと思ってたわw!」みたいな感じだった。ICPCの参加者たちでそんな話をしてたらしい

*3:ここまで本格的に練習会を頻繁に開く大学もあまり多くはないそうです。が、お隣アルバータ州でもやけに賞金の高い($1500とかだったと思う)大学主催コンテストが開かれているらしいです。

*4:カレー味のハワイアンピザは普通に不評だからやめろ

ひとり地区予選 2018-2019 ACM-ICPC Southeastern European Regional

嫌いな問題ばっかりでやる気が失せた。

B: Broken Watch
やるだけ問題に時間を使うな

int main(){
	long long a,b,c,n;
	scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&n);
	if(n==2){
		printf("0\n");return 0;
	}
	unsigned long long ret=1;

	ret=n*(n-1);
	if(ret%6==0){
		ret/=6;ret*=n-2;
	}else if(ret%3==0){
		ret/=3;ret*=(n-2)/2;
	}else if(ret%2==0){
		ret/=2;ret*=(n-2)/3;
	}else ret*=(n-2)/6;
	
	long long tmp=n*((n-1)/2);
	if(tmp%2==0){
		tmp/=2;ret-=tmp*((n-1)/2-1);
	}else{
		ret-=tmp*(((n-1)/2-1)/2);
	}
	
	if(a!=b&&b!=c&&c!=a){
		ret*=6;
	}else if(a!=b||b!=c||c!=a){
		ret*=3;
	}else{
		;
	}

	printf("%I64u\n",ret);
}

C: Tree
虚無

int p[110];
vector<int>g[110];
int x[110];
int y[110];
vector<int>f;
void dfs(int a,int b,int c){
	if(p[a]==1){
		f.push_back(c);
	}
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		dfs(g[a][i],a,c+1);
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<a-1;i++){
		int s,t;scanf("%d%d",&s,&t);
		s--;t--;g[s].push_back(t);
		g[t].push_back(s);
		x[i]=s;y[i]=t;
	}
	int ret=mod;
	for(int i=0;i<a;i++){
		f.clear();
		dfs(i,-1,0);
		std::sort(f.begin(),f.end());
		ret=min(ret,f[b-1]*2);
	}
	for(int i=0;i<a-1;i++){
		f.clear();
		dfs(x[i],y[i],0);
		dfs(y[i],x[i],0);
		std::sort(f.begin(),f.end());
		ret=min(ret,f[b-1]*2+1);
	}
	printf("%d\n",ret);
}

E: Fishermen
実家。

int X[210000];
int Y[210000];
int z[210000];
int q[210000];
int bit[210000];
vector<pair<pair<int,int> ,int > >ev;
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<210000;a|=a+1)bit[a]+=b;
}
int ans[210000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%d%d",X+i,Y+i);
		z[i]=X[i]-Y[i];
		ev.push_back(make_pair(make_pair(X[i]+Y[i],-1),X[i]-Y[i]));
	}
	std::sort(z,z+a);
	for(int i=0;i<b;i++){
		scanf("%d",q+i);
		ev.push_back(make_pair(make_pair(q[i]+c,i),q[i]-c));
	}
	std::sort(ev.begin(),ev.end());
	for(int i=0;i<ev.size();i++){
		if(ev[i].first.second==-1){
			add(lower_bound(z,z+a,ev[i].second)-z,1);
		}else{
			ans[ev[i].first.second]=sum(lower_bound(z,z+a,ev[i].second)-z,201000);
		}
	}
	for(int i=0;i<b;i++)printf("%d\n",ans[i]);
}

F: Min Max Convert
手前まで全部変えて1対1にすればやりたい方にできる。
面倒すぎる。

int A[110000];
int B[110000];
int fr[110000];
int m[210000];
int L[210000];
int R[210000];
int segtree[524288];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return -mod;
	if(c<=a&&b<=d)return segtree[e];
	return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void update(int a,int b){
	a+=262144;
	while(a){
		segtree[a]=max(segtree[a],b);
		a/=2;
	}
}
vector<pair<pair<int,int> ,int> >qu;
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",A+i);
	for(int i=0;i<a;i++)scanf("%d",B+i);
	int at=0;

	for(int i=0;i<a;i++){
		while(at<a&&A[at]!=B[i]){
			at++;
		}
		fr[i]=at;
	//	printf("%d\n",fr[i]);
	}

	if(at==a){
		printf("-1\n");return 0;
	}
	for(int i=0;i<a;i++)update(i,A[i]);
	int sz=0;
	int lL=mod;
	int lv=0;
	for(int i=a-1;i>=0;i--){
		if(fr[i]<i){
			L[sz]=fr[i]+1;
			R[sz]=i;
			m[sz]=1;
			int val=0;
			if(lL<=i)val=lv;
			val=max(val,query(0,262143,fr[i]+1,min(lL-1,i),1));
			sz++;
			L[sz]=fr[i];
			R[sz]=i;
			if(val<B[i])m[sz]=1;
			lv=B[i];
			sz++;
			lL=fr[i];
		}
	}
	for(int i=0;i<524288;i++)segtree[i]=0;
	reverse(qu.begin(),qu.end());
	at=0;
	for(int i=0;i<qu.size();i++){
		while(at<a&&at<qu[i].first.first){
			update(at,A[at]);at++;
		}
		while(at<=qu[i].first.second){
			update(at,qu[i].second);
			at++;
		}
	}
	while(at<a){
		update(at,A[at]);
		at++;
	}

	lL=-mod;
	lv=0;
	for(int i=0;i<a;i++){
		if(fr[i]>i){
			L[sz]=i;
			R[sz]=fr[i]-1;

			m[sz]=1;
			int val=0;
			if(i<=lL)val=lv;
			val=max(val,query(0,262143,max(lL+1,i),R[sz],1));
		
			sz++;
			L[sz]=i;
			R[sz]=fr[i];
			if(val<B[i])m[sz]=1;
			lv=B[i];
			sz++;
			lL=fr[i];
		}
	}
	printf("%d\n",sz);
	for(int i=0;i<sz;i++){
		if(m[i]==0)printf("m ");
		else printf("M ");
		printf("%d %d\n",L[i]+1,R[i]+1);
	}
}

G: Matrix Queues
見るからに独立

int segtree[2][1<<21];
int t[2][21];
int cur[2][1<<20];
long long v[21];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<=a;i++)t[0][i]=t[1][i]=(1<<i);

	while(b--){
		int p,q;scanf("%d%d",&p,&q);q--;
		int ad=1;
		if(segtree[p][q+(1<<a)])ad=-1;
		int at=q+(1<<a);
		int lv=a;
		while(at){
			if(segtree[p][at]==0||segtree[p][at]==(1<<(a-lv))){
				t[p][lv]--;
			}
			segtree[p][at]+=ad;
			if(segtree[p][at]==0||segtree[p][at]==(1<<(a-lv))){
				t[p][lv]++;
			}
			at/=2;lv--;
		}
		for(int i=0;i<=a;i++)v[i]=0;
		long long X=0;
		long long Y=0;
		long long ng=0;
		for(int i=0;i<=a;i++){
			X=t[0][i];
			Y=t[1][i];
			v[i]=X*Y-ng;
			ng+=v[i];
			ng*=4;
		}
		
		long long ret=0;
		long long tmp=0;
		for(int i=a;i>=0;i--){
			tmp+=v[i];
			ret+=tmp;
			tmp/=4;
		}
		printf("%I64d\n",ret);
	}	
}

H: Modern Djinn
問題文が意味不明。せっかく考えてどうせ乱択でしょってなると気が抜ける。

vector<pair<int,int> >g[110000];
int t[120000];
int at[2][220000];
int cnt[2];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int a,b;scanf("%d%d",&a,&b);
		for(int i=0;i<a;i++){
			g[i].clear();
		}
		for(int i=0;i<b;i++){
			int p,q;scanf("%d%d",&p,&q);p--;q--;
			g[p].push_back(make_pair(q,i));
		}
		while(1){
			for(int i=0;i<a;i++)t[i]=rand()%2;
	//		for(int i=0;i<a;i++)printf("%d",t[i]);printf("\n");
			cnt[0]=cnt[1]=0;
			for(int i=0;i<a;i++){
				for(int j=0;j<g[i].size();j++){
					if(t[i]!=t[g[i][j].first]){
						at[t[i]][cnt[t[i]]++]=g[i][j].second;
					}
				}
			}
			if(cnt[0]>b/4){
				printf("%d\n",cnt[0]);
				for(int i=0;i<cnt[0];i++){
					if(i)printf(" ");
					printf("%d",at[0][i]+1);
				}printf("\n");
				break;
			}else if(cnt[1]>b/4){
				printf("%d\n",cnt[1]);
				for(int i=0;i<cnt[1];i++){
					if(i)printf(" ");
					printf("%d",at[1][i]+1);
				}printf("\n");
				break;
			}
		}
	}
}

I: 枝刈り探索だと思ってTLEばっかり出して完全にやる気が消えた。普通に順列が決まってDPも普通だがWAが続くともうやる気になれない。
D: 木DPするだけなんだけど細部が複雑すぎる。

単純にこのセットは一人でやるには重すぎる。

ひとり地区予選 ACPC 2018

まあそうだとは思っていたけどかなりくだらないコンテストだなあ

D: Wooden Fence
問題文をよく見ると白黒白黒...はできないらしい。

int main(){
	int T;scanf("%d",&T);
	while(T--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(c>=a/2&&b>=(a+1)/2){
			printf("YES\n");
		}else printf("NO\n");
	}
}

C: Shortest Path!
これも問題文が難しい。

int main(){
	int T;scanf("%d",&T);
	while(T--){
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		double ret=0;
		ret+=sqrt((double)a*a+((double)b+c+c)*((double)b+c+c));
		double tmp=sqrt((long long)a*a+(long long)b*b);
		//printf("%.12f\n",ret);
		ret+=tmp*d/100;
		//printf("%.12f\n",ret);
		double X=(double)b*(d)/100;
		double Y=(double)a*(100-d)/100;
		ret+=sqrt((double)Y*Y+((double)c+(b+c-X))*((double)c+(b+c-X)));
		printf("%.12f\n",ret);
	}
}

F: I'm Bored!
問題文が不十分でわかりにくい。全部0やめろし

int p[30];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		for(int i=0;i<26;i++)scanf("%d",p+i);
		int o=0;
		int t=0;
		for(int i=0;i<26;i++){
			if(p[i]>=2)t++;
			if(p[i]==1)o++;
		}
		printf("%d ",t*2+!!o);
		int ret=mod;
		for(int i=0;i<26;i++){
			if(p[i]>=2){
				ret=min(ret,p[i]/2);
			}
		}
		if(t==0&&o==0)ret=0;
		if(o)ret=min(ret,o);
		printf("%d\n",ret);
	}
}

H: Beautiful Substrings
まあ普通。

char S[110000];
char T[110000];
int t[26][26];
int cnt[26];
int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		scanf("%s%s",S,T);
		long long ret=0;
		for(int i=0;i<26;i++)for(int j=0;j<26;j++)t[i][j]=0;
		for(int i=0;i+c-1<a;i++){
			t[S[i]-'a'][S[i+c-1]-'a']=1;
		}
		for(int i=0;i<26;i++)cnt[i]=0;
		for(int i=0;i<b;i++){
			cnt[T[i]-'a']++;
			for(int j=0;j<26;j++){
				if(t[j][T[i]-'a']){
					ret+=cnt[j];
				}
			}
		}
		printf("%I64d\n",ret);
	}
}

K: Cyclic Shift
これも文字列bをaにするという不自然さが

char S[110000];
char T[110000];
char u[110000];
char v[110000];
int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
		int a;scanf("%d",&a);
		scanf("%s%s",S,T);
		int ind=0;
		for(int i=0;i<a;i++){
			if(S[i]!=T[i]){
				u[ind]=S[i];
				v[ind]=T[i];
				ind++;
			}
		}
		if(ind==0){
			printf("YES\n");continue;
		}
		bool ok=true;
		for(int i=0;i<ind;i++){
			if(v[i]!=u[(i+1)%ind])ok=false;
		}
		if(ok)printf("YES\n");else printf("NO\n");
	}
}

E: Stupid Submissions
言われた通りにやる。

char in[2];
char s[11000];
int sum[11000];
int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		int ret=0;
		for(int i=0;i<11000;i++)sum[i]=0;

		for(int i=0;i<a;i++){
			scanf("%s",s+i);
		}
		for(int i=0;i<a;i++){
			if(s[i]=='S')sum[i+1]=sum[i]+1;
			else sum[i+1]=sum[i];
		}
		while(b--){
			scanf("%s",in);
			if(in[0]=='A'){
				c=a;continue;
			}
			int x;scanf("%d",&x);
			if(s[x-1]=='S'&&c>=x)ret++;
			c=max(c,x);
		}
		printf("%d\n",ret);
	}
}

A: Multiplication Dilemma
問題文は無視する。0の個数間違えた。

int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
	 	int a,b;scanf("%d%d",&a,&b);
		long long ans=(long long)a*b;
		bool fi=true;
		if(ans<0){
			fi=false;
			printf("1000000000 x -1000000000");
			ans=1000000000000000000LL+ans;
		}
		int cnt=0;
		while(ans){
			if(ans%10){
				if(!fi)printf(" + ");
				printf("%d",(int)(ans%10));
				for(int i=0;i<cnt/2;i++)printf("0");
				printf(" x ");
				printf("1");
				for(int i=0;i<cnt-cnt/2;i++)printf("0");
				fi=false;
			}
			ans/=10;
			cnt++;
		}
		printf("\n");
	}
}

J: Even Numbers
パスカルmod2を眺める。

int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
		long long a;scanf("%I64d",&a);
		if(a<2)printf("0\n");
		else{
			printf("%I64d\n",a+1-(1LL<<__builtin_popcountll(a)));
		}
	}
}

G: Minimax
やる。

int p[510][510];
int t[4][510][510];
int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
		int a,b;scanf("%d%d",&a,&b);
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)scanf("%d",&p[i][j]);
		for(int i=0;i<4;i++)for(int j=0;j<a;j++)for(int k=0;k<b;k++)
			t[i][j][k]=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				t[0][i][j]=p[i][j];
				if(i)t[0][i][j]=max(t[0][i][j],t[0][i-1][j]);
				if(j)t[0][i][j]=max(t[0][i][j],t[0][i][j-1]);
			}
		}
		for(int i=0;i<a;i++){
			for(int j=b-1;j>=0;j--){
				t[1][i][j]=p[i][j];
				if(i)t[1][i][j]=max(t[1][i][j],t[1][i-1][j]);
				if(j<b-1)t[1][i][j]=max(t[1][i][j],t[1][i][j+1]);
			}
		}
		for(int i=a-1;i>=0;i--){
			for(int j=0;j<b;j++){
				t[2][i][j]=p[i][j];
				if(i<a-1)t[2][i][j]=max(t[2][i][j],t[2][i+1][j]);
				if(j)t[2][i][j]=max(t[2][i][j],t[2][i][j-1]);
			}
		}
		for(int i=a-1;i>=0;i--){
			for(int j=b-1;j>=0;j--){
				t[3][i][j]=p[i][j];
				if(i<a-1)t[3][i][j]=max(t[3][i][j],t[3][i+1][j]);
				if(j<b-1)t[3][i][j]=max(t[3][i][j],t[3][i][j+1]);
			}
		}
		int ret=mod;
		for(int i=1;i<a-1;i++){
			for(int j=1;j<b-1;j++){
				int R=max(max(t[0][i-1][j-1],t[1][i-1][j+1]),max(t[2][i+1][j-1],t[3][i+1][j+1]));
				int L=min(min(t[0][i-1][j-1],t[1][i-1][j+1]),min(t[2][i+1][j-1],t[3][i+1][j+1]));
				
				ret=min(ret,R-L);
			}
		}
		printf("%d\n",ret);
	}
}

B: Updating the Tree
ここからようやく中身がある。枝分かれがない場所で 値-深さ, 値+深さの最頻値が何回出てくるかわかればよくて、頑張ってmapで管理する。
データ間違ってると思っていろいろassertしてWAを稼いだらmap消すのの判定間違ってた(草)

int p[110000];
vector<int>g[110000];
int ans[110000];
int sz[110000];
int L[110000];
int R[110000];
map<int,int>lm;
map<int,int>rm;
int sh;
int sc;
void dfs2(int a,int b,map<int,int> &ML,map<int,int> &MR,int ordL,int ordR){
	ML[L[a]+ordL]++;
	MR[R[a]+ordR]++;
	sc=max(sc,ML[L[a]+ordL]);
	sc=max(sc,MR[R[a]+ordR]);
	//printf("%d: %d %d\n",a,L[a]+ordL,R[a]+ordR);
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		dfs2(g[a][i],a,ML,MR,ordL,ordR);
	}
}
int dfs(int a,int b,int c){
	int ko=0;
	sz[a]=1;
	L[a]=p[a]-c;
	R[a]=p[a]+c;
	bool dame=false;
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		if(ko>=1){
			lm.clear();
			rm.clear();
			sh=0;
		}
		int tmp=dfs(g[a][i],a,c+1);
		ko++;
		if(tmp==-1)dame=true;
		sz[a]+=sz[g[a][i]];

	}
	if(ko>1){
		lm.clear();
		rm.clear();
		sh=0;
	}
	if(ko>2)dame=true;
	if(dame)ans[a]=-1;
	if(ko>2||dame)return -1;
	if(ko==0){
		ans[a]=0;
		lm[L[a]]++;
		sh=max(sh,lm[L[a]]);
		rm[R[a]]++;
		sh=max(sh,rm[R[a]]);
	//	printf("%d: %d %d\n",a,L[a],R[a]);
	}else if(ko==2){
		map<int,int>lc;
		map<int,int>rc;

		sc=1;
		lc[L[a]]=1;
		rc[R[a]]=1;
		int fi=0;
		for(int i=0;i<g[a].size();i++){
			if(g[a][i]==b)continue;
			if(fi==0){
				dfs2(g[a][i],a,lc,rc,0,0);
			}else{
				dfs2(g[a][i],a,rc,lc,R[a]-L[a],L[a]-R[a]);
			}
			fi++;
		}
	//	assert(sz[a]>=sc);
		ans[a]=sz[a]-sc;
		return -1;
	}else{
		lm[L[a]]++;
		sh=max(sh,lm[L[a]]);
		rm[R[a]]++;
		sh=max(sh,rm[R[a]]);
	//	assert(sz[a]>=sh);
	//	assert(sz[a]>=lm.size());
		ans[a]=sz[a]-sh;
	//	printf("%d: %d %d %d\n",a,L[a],R[a],sh);
	}
	return 1;
}
int UF[110000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return ;UF[a]+=UF[b];UF[b]=a;
}
int main(){
	int Test;scanf("%d",&Test);
	while(Test--){
		int a;scanf("%d",&a);

		for(int i=0;i<a;i++)UF[i]=-1;
		for(int i=0;i<a;i++)g[i].clear();
		for(int i=0;i<a;i++)scanf("%d",p+i);
		for(int i=0;i<a;i++)sz[i]=0;
		for(int i=0;i<a-1;i++){
			int p,q;scanf("%d%d",&p,&q);p--;q--;
			g[p].push_back(q);
			g[q].push_back(p);
			UNION(p,q);
		}
		//assert(-UF[FIND(0)]==a);
		lm.clear();
		rm.clear();
		sh=sc=0;
		assert(lm.size()==0);
		assert(rm.size()==0);
		assert(sh==0);
		
		dfs(0,-1,0);
		for(int i=0;i<a;i++){
			if(i)printf(" ");
			printf("%d",ans[i]);
		}
		printf("\n");
	}
}

I: Secret Project
年齢当てるカードの問題の簡易版。

long long fact[110000];
long long inv[110000];
long long finv[110000];
long long C(int a,int b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
int main(){
	int Test;scanf("%d",&Test);
	fact[0]=finv[0]=1;
	inv[1]=1;
	for(int i=2;i<110000;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<110000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
	while(Test--){
		int a,b;scanf("%d%d",&a,&b);
		printf("%I64d %I64d\n",C(a,a-b+1),C(a,a-b+1)*(a-b+1)%mod*inv[a]%mod);
	}
}

まとめ:
Bが酷い
問題文が読みにくすぎる
無を身につけた

皆さんACPCで練習するのはやめましょう。

ひとり地区予選 2018-2019 ACM-ICPC Southeast USA Regional

これはつまらん(確信)。3時間強の練習会。

B: Count the Bits
5万回見た。ところで間違えてAに提出してWA出した

long long dp[140][140][1100];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	dp[0][0][0]=1;
	for(int i=0;i<b;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<a;k++){
				if(dp[i][j][k]==0)continue;
				dp[i+1][j][k*2%a]=(dp[i+1][j][k*2%a]+dp[i][j][k])%mod;
				dp[i+1][j+1][(k*2+1)%a]=(dp[i+1][j+1][(k*2+1)%a]+dp[i][j][k])%mod;
			}
		}
	}
	long long ret=0;
	for(int i=0;i<=b;i++){
		ret=(ret+i*dp[b][i][0])%mod;
	}
	printf("%lld\n",ret);
}

C: Exam
無。

char in[2][1100];
int main(){
	int a;scanf("%d",&a);
	scanf("%s%s",in[0],in[1]);
	int n=strlen(in[0]);
	int ret=0;
	for(int i=0;i<n;i++){
		if(in[0][i]==in[1][i]&&a){
			a--;ret++;
		}
	}
		int cn=0;
		for(int i=0;i<n;i++){
			if(in[0][i]!=in[1][i])cn++;
		}
		ret+=cn-a;
	printf("%d\n",ret);
}

F: Knockout
簡単な問題が全く見つからないからうだうだしてたら他の人が解いたので自分もやった

char in[110];
int r[110];
double dp[2][1<<10];
double calc(int a,int b){
	if(dp[a][b]>=-0.5)return dp[a][b];
	double ret=0;
	for(int i=2;i<=12;i++){
		double p=1.0/36;
		p*=min(12-i,i-2)+1;
		double tmp=-1;
		bool ok=false;
		int val=0;
		for(int j=0;j<10;j++){
			if(b&(1<<j)){
				val*=10;val+=j;
			}
		}
		if(a==0)tmp=val;
		for(int j=0;j<(1<<10);j++){
			if((b&j)!=j)continue;
			int cur=0;
			for(int k=0;k<10;k++)if(j&(1<<k))cur+=k;
			if(cur!=i)continue;
			ok=true;
			double tt=calc(a,b-j);
			if(a==0&&tt<tmp){
				tmp=tt;
			}
			if(a==1&&tt>tmp){
				tmp=tt;
			}
		}
		if(a==1&&ok==false){
			tmp=val;
		}
		ret+=p*tmp;
	}
//	printf("%d %d: %f\n",a,b,ret);
	return dp[a][b]=ret;
}
int main(){
	scanf("%s",in);
	int a,b;scanf("%d%d",&a,&b);
	int n=a+b;
	int st=0;
	int v=0;
	for(int i=0;in[i];i++){
		r[in[i]-'0']=1;
		v*=10;
		v+=in[i]-'0';
		st+=(1<<(in[i]-'0'));
	}
	for(int i=0;i<2;i++)for(int j=0;j<(1<<10);j++)dp[i][j]=-1;
	
	int mv1=0;
	double b1=v;
	int mv2=0;
	double b2=-1;
	for(int i=0;i<(1<<10);i++){
		if((i&st)!=i)continue;
		int St=0;
		for(int j=0;j<10;j++){
			if(i&(1<<j))St+=j;
		}
		if(St!=n)continue;
	//	printf("%d %d\n",st,i);
		double tmp1=calc(0,st-i);
		double tmp2=calc(1,st-i);
		if(tmp1<b1){
			b1=tmp1;mv1=i;
		}
		if(tmp2>b2){
			b2=tmp2;mv2=i;
		}
		
	}
	if(mv1==0){
		printf("-1");
	}else{
		for(int i=0;i<10;i++)if(mv1&(1<<i))printf("%d",i);
	}
	printf(" %.5f\n",b1);
	if(mv2==0){
		printf("-1");
		b2=v;
	}else{
		for(int i=0;i<10;i++)if(mv2&(1<<i))printf("%d",i);
	}
	printf(" %.5f\n",b2);
	
}

J: Area Rug
5万回見た。

char in[1100][1100];
int sum[1100][1100];
int ans[11000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",in[i]);
	for(int i=0;i<a;i++)for(int j=0;j<a;j++){
		if(in[i][j]=='D')sum[i+1][j+1]++;
	}
	for(int i=0;i<=a;i++)for(int j=0;j<=a;j++){
		sum[i+1][j]+=sum[i][j];
	}
	for(int i=0;i<=a;i++)for(int j=0;j<=a;j++){
		sum[i][j+1]+=sum[i][j];
	}
	for(int i=0;i<=a-b;i++){
		for(int j=0;j<=a-b;j++){
			ans[sum[i+b][j+b]-sum[i+b][j]-sum[i][j+b]+sum[i][j]]++;
		}
	}
	for(int i=0;i<=b*b;i++){
		if(ans[i]){
			printf("%d %d\n",i,ans[i]);
		}
	}
}

I: Rectangles
Fortune Telling。

int segtree[524288];
int laz[524288];
int z[210000];
pair<pair<int,int>,pair<int,int> > ev[210000];
void update(int a,int b,int c,int d,int e){
	if(laz[e]){
		laz[e]=0;
		segtree[e]=(z[b+1]-z[a])-segtree[e];
		if(a!=b){
			laz[e*2]=!laz[e*2];
			laz[e*2+1]=!laz[e*2+1];
		}
	}
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		laz[e]=!laz[e];
	}else{
		update(a,(a+b)/2,c,d,e*2);
		update((a+b)/2+1,b,c,d,e*2+1);
		segtree[e]=segtree[e*2]+segtree[e*2+1];
	}
	if(laz[e]){
		laz[e]=0;
		segtree[e]=(z[b+1]-z[a])-segtree[e];
		if(a!=b){
			laz[e*2]=!laz[e*2];
			laz[e*2+1]=!laz[e*2+1];
		}
	}
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		int X1,Y1,X2,Y2;
		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		ev[i*2]=make_pair(make_pair(X1,0),make_pair(Y1,Y2));
		ev[i*2+1]=make_pair(make_pair(X2,1),make_pair(Y1,Y2));
		z[i*2]=Y1;
		z[i*2+1]=Y2;
	}
	std::sort(z,z+a*2);
	std::sort(ev,ev+a*2);
	z[a*2]=mod;
	long long ret=0;
	for(int i=0;i<a*2;i++){
		int at=ev[i].first.first;
		int ty=ev[i].first.second;
		int YL=ev[i].second.first;
		int YR=ev[i].second.second;
		int Y1=lower_bound(z,z+a*2,YL)-z;
		int Y2=lower_bound(z,z+a*2,YR)-z;
		if(i){
			long long ks=ev[i].first.first-ev[i-1].first.first;
			ret+=ks*segtree[1];
		}
		update(0,262143,Y1,Y2-1,1);
	}
	printf("%lld\n",ret);
}

K: To Tell the Truth
問題文の意味を推測する。

int L[1100];
int R[1100];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d%d",L+i,R+i);
	int ret=-1;
	for(int i=0;i<=a;i++){
		int cur=0;
		for(int j=0;j<a;j++){
			if(L[j]<=i&&i<=R[j])cur++;
		}
		if(cur==i)ret=i;
	}
	printf("%d\n",ret);
}

D: Illiteracy
クソゲー(問題文が読みにくくて条件を見落としまくる)。

int bfs[2000000];
char in[2][10];
int t[10];
int v[10];
int main(){
	scanf("%s%s",in[0],in[1]);
	for(int i=0;i<2000000;i++)bfs[i]=-1;
	int now=0;
	for(int i=0;i<8;i++){
		now*=6;
		now+=in[0][i]-'A';
	}
	int goal=0;
	for(int i=0;i<8;i++){
		goal*=6;
		goal+=in[1][i]-'A';
	}
	queue<int>Q;
	Q.push(now);
	bfs[now]=0;
	while(Q.size()){
		int at=Q.front();
		Q.pop();
		int tmp=at;
		for(int i=7;i>=0;i--){
			t[i]=tmp%6;tmp/=6;
		}

		for(int i=0;i<8;i++){
			if(t[i]==0){
				for(int j=0;j<8;j++)v[j]=t[j];
				if(i)v[i-1]=(v[i-1]+1)%6;
				if(i<7)v[i+1]=(v[i+1]+1)%6;
			}else if(t[i]==1){
				for(int j=0;j<8;j++)v[j]=t[j];
				if(i&&i<7)v[i+1]=v[i-1];
			}else if(t[i]==2){
				for(int j=0;j<8;j++)v[j]=t[j];
				v[7-i]=(v[7-i]+1)%6;
			}else if(t[i]==3){
				for(int j=0;j<8;j++)v[j]=t[j];
				if(i<4){
					for(int j=0;j<i;j++)v[j]=(v[j]+1)%6;
				}else{
					for(int j=i+1;j<8;j++)v[j]=(v[j]+1)%6;
				}
			}else if(t[i]==4){
				for(int j=0;j<8;j++)v[j]=t[j];
				if(i&&i<4){
					v[0]=(v[0]+1)%6;
					v[i*2]=(v[i*2]+1)%6;
				}else if(i>=4&&i<7){
					v[7]=(v[7]+1)%6;
					v[i-(7-i)]=(v[i-(7-i)]+1)%6;
				}
			}else{
				for(int j=0;j<8;j++)v[j]=t[j];
				if(i%2==0){
					v[i/2+4]=(v[i/2+4]+1)%6;
				}else{
					v[i/2]=(v[i/2]+1)%6;
				}
			}
			int to=0;
			for(int j=0;j<8;j++){
				to*=6;
				to+=v[j];
			}
			if(bfs[to]==-1){
				bfs[to]=bfs[at]+1;
				Q.push(to);
			}
		}
	}
	printf("%d\n",bfs[goal]);
}

E: Inversions
(どこかで見たことがあるような気もする)。計算量からしてどうせ凸なので頑張って凸性DPを書く。様々なものをO(1)で求めるために前計算しないといけなくて苦痛。

long long dp[110][210000];
int p[210000];
vector<int>v;
int bit[120];
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<120;a|=a+1)bit[a]+=b;
}
int cnt[110][210000];
long long stf[110][210000];
int cnt2[110][210000];
long long stf2[110][210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<a;i++){
		if(p[i])v.push_back(p[i]);
	}
	long long ret=0;
	for(int i=0;i<v.size();i++){
		ret+=sum(v[i]+1,110);
		add(v[i],1);
	}
	for(int i=0;i<a;i++){
		if(p[i]){
			cnt[p[i]-1][i]++;
		}
	}
	for(int i=b;i>0;i--)for(int j=0;j<=a;j++){
		cnt[i-1][j]+=cnt[i][j];
	}
	for(int i=0;i<=b;i++)for(int j=0;j<=a;j++){
		cnt[i][j+1]+=cnt[i][j];
	}
	for(int i=0;i<a;i++){
		if(p[i]==0){
			stf[0][i+1]++;
			for(int j=1;j<=b;j++){
				stf[j][i+1]=cnt[j][i];
			}
		}
	}
	for(int i=0;i<=b;i++){
		for(int j=0;j<=a;j++){
			stf[i][j+1]+=stf[i][j];
		}
	}

//	for(int i=0;i<=b;i++){
//		for(int j=0;j<=a;j++)printf("%lld ",stf[i][j]);printf("\n");
//	}
	for(int i=0;i<a;i++){
		if(p[i]){
			cnt2[p[i]+1][i]++;
		}
	}
	for(int i=0;i<=b;i++)for(int j=0;j<=a;j++){
		cnt2[i+1][j]+=cnt2[i][j];
	}
	for(int i=0;i<=b;i++)for(int j=a;j>0;j--){
		cnt2[i][j-1]+=cnt2[i][j];
	}
	for(int i=0;i<a;i++){
		if(p[i]==0){
			stf2[0][i+1]++;
			for(int j=1;j<=b;j++){
				stf2[j][i+1]=cnt2[j][i];
			}
		}
	}
	for(int i=0;i<=b;i++){
		for(int j=0;j<=a;j++){
			stf2[i][j+1]+=stf2[i][j];
		}
	}

	for(int i=0;i<=b+1;i++)for(int j=0;j<=a;j++)dp[i][j]=-inf;
	dp[b+1][0]=0;
	vector<int>ind;
	ind.push_back(0);
	for(int i=0;i<a;i++)if(p[i]==0)ind.push_back(i+1);
	for(int i=b;i>=1;i--){
		int at=0;
		for(int j=0;j<=ind.size();j++)dp[i][j]=dp[i+1][j];
		for(int j=0;j<ind.size();j++){
			long long prev=-1;
			long long kk=0;

			while(at<=j){
				kk=dp[i+1][at];
				long long tmp=kk+(long long)(stf[0][ind[j]]-stf[0][ind[at]])*stf[0][ind[at]]+(stf[i][ind[j]]-stf[i][ind[at]])+(stf2[i][ind[j]]-stf2[i][ind[at]]);
				if(prev>tmp){
					break;
				}
				dp[i][j]=max(dp[i][j],tmp);prev=tmp;at++;
			}
			at--;
		//	printf("%d %d: %d %lld\n",i,j,at,dp[i][j]);
		}
	}
	long long mm=0;
	for(int i=1;i<=b+1;i++)for(int j=0;j<=a;j++)mm=max(mm,dp[i][j]);
	printf("%lld\n",ret+mm);
}

公式のGの答えが間違っていたらしい。