Codeforces Round #561 (Div. 2)
bあｙた
A. Silent Classroom
問題：n個の文字列が与えられ、2つのグループにわける。下で定義される値を最小化せよ。
うるささ：同じグループ内で同じ頭文字を持つペアの順序なしの数
考察：
まず全部を頭文字でわけます。
ある文字で始まる文字列がｋ個のとき、k/2ずつにわけることが最適なのでそうします。
算数得意じゃないと厳しそうですね。
k/2^2+k/2^2が最も小さくなるのって、算数の典型っぽいけどどこで身に着けたかあんまり覚えてないです。
B. All the Vowels Please
問題：整数ｋが与えられる。k=n*mを満たす任意の整数の組n,mで、n*mグリッドを作る。どの行、またはどの列にもすべての母音が現れるようにしたい。そのような長さkの文字列を構成せよ。
考察：
まず言いたいことがあります。問題文がわかりづらすぎる。マジで読解に時間かかりました。n,mも含めての構築ならかなり簡単です。この任意の整数組n,mというのが書いてなくて想像でやるしかなかったです。ほんとにひどい。
はい愚痴でした。
では考察していきます。
まずn,mが5以上になる整数組がない場合は構築不可能です。
例えば5と6で割り切れるとしましょう。
このとき文字列をaiueoの繰り返しにすると、n=5ではじかれます
1行ごとに1文字ずらしても、6のときはじかれます。
ではmod5で、存在しない数でずらすとしましょう（５，６なら2~4のどれかです）
次にmod5がすべて存在する例を考えます。
このとき構築不可能でしょうか？
結論から言うと適当にやっても構築できます。
最小でも2520くらいになります。
n<mとすると、ｎでは1周、mでは2周以上することが保証されます。
したがって雑な構築でも通ります。
実装結構重いですが、頑張ると通ります。
読解パートで２ペナでしたが、19分なのでよかったと思います。
C. A Tale of Two Lands
問題：ｎ個の整数が与えられる。この中の2つを選ぶ方法はnC2通りある。その各場合について下の条件が成り立つ個数を求めよ
条件：[|x|,|y|]を、[|x-y|,|x+y|]が完全に含む
考察：
ｘ、ｙが順不同！って書いてあるんですけど、これは算数しないと順不同でよいかわかりません。問題が悪すぎる。
はい愚痴でした。
順不同でも結果が変わらないことが暗に保証されています。
ではどのようなときに条件を満たすでしょうか。
ｘ、ｙが正、負、片方だけ正で片方が負、の3通りにわけたりいろいろします。
そうするとすべて絶対値を取ってよいことがわかります。
ここでx<yとして、2*x<=y のとき条件を満たします。
はじめにソートしておき、すべてのxの候補に対して二分探索でyの個数を求めていけばO(nlogn）で解くことができます
読解で苦労した割に17分だったので結構よかったと思います。
unorderedに惑わされなければ十分な速度だったと思います。
D. Cute Sequences
問題：n個の整数列を考えます。xi=x1+x2+...+xi-1+ri、1<=ri<=mです。あるクエリa,b,mについて、a=x1,b=xkかつk50以下の整数列を構築せよ
考察：
丁寧に整数列を計算してみます。そうすると以下のようになります
a
a+r1
2a+r1+r2
4a+2r1+r2+r3
これを一般化すると、だいたい
xk=2*xk-1+rk
のようになります。
kの個数で全探索をします。
2^k*aは固定なのでbから引きます。
またriは1以上なので、最低でも2^kは使います。最大で2^k*mです。
この範囲にb-2^k*aが収まるとき構築可能なので、riをiが大きいほうから貪欲に求めていきます（ｍ以下の最大の整数にしていく）
このとき、最後のほうでriを1にするとｂを超える場合があります。
これを防ぐためにあらかじめ2^k引いておいて、rのベクトルを1で初期化します。
各ステップでm-1以下になるように構築し、rベクトルに足せばよいです。
2^14*2^14でオーバーフローしてた；；；；
実質ACｗ
泣
E. The LCMs Must be Large
問題：n個の整数がある。この整数からsi個の整数を選ぶ操作をｍ回行う。各操作で、選んだ整数のlcm＞選ばなかった整数のlcmが成り立つことはできるか？
考察：
選んだ集合から、背反な2つの集合があるとき必ず不可能です。
このことからすべての集合から、整数のindexを経由して他の操作に行くパスを見つけるグラフ問題を考えます。
全ての操作において、他の操作が距離2以下ならOKです。
操作回数は高々50回らしいのでO(M*(N+M))くらいでも十分間に合います
考察重めで、実装もそこまで軽くないんですけど25分程度で通せました。
これが通せてなんとかって感じですね。通らなかったら3完だったので冷えてました。
