Atcoder Grand Contest 12

今回も数分遅刻。学ばない男。

A問題　AtCoder Group Contest

各人に強さA_iのついている3n人に対し3人組をn個作って、各グループの強さの中央値の総和を最大化する問題。

ソートしてi,3n-2*i-2,3n-2*i-1番目の人でグループを作っていくと最適。

B問題　Splatter painting

グラフはつらい。なんか後ろからやっていくんかなといった感想。知らない。

C問題　Tautonym puzzle

なんか算数要素強そうなのでとりかかる。

同じ種類のものがn個あればそいつらで2^(n-1)-1個の良い部分文字列は作れることは示せた。10^12だと2進数で40bitとかだし、文字列の長さの制約に引っかかるなぁ、なんかいい構成法ないかなーとやっていたけど、何も降ってこなかった。おしまい。

残り3分の時点で535位。うげぇ。。

結局いつも算数しか解いてないので、競プロちゃんとやりましょうっていう話。