SRM 621 Div2 CF #257 Div2

SRM 621 Div2

Easy

文字列が辞書順なのか短い順なのか両方なのかどちらでもないのか

Med

配列に含まれる整数の和で作れない最小の整数。 何が作れるかをdpみたいに計算する

Hard

colorに含まれる全ての色をつくるのに必要な絵の具の数。２つの絵の具を混ぜるとxorの値を取る色になる。

colorの2進表現をそれぞれ配列に入れてく。２次の行列ができる。とあるM個の要素から2次の行列が生成できるとすると。その行列の階級を求めればいいらしい

Codeforces #257 Div2

A

N人の生徒に順番にM個だけ、アメを配る、生徒には満足するアメの個数があり、もらった時満たさないなら列の後ろに回る。最後にもらい終わる生徒は誰か。

キューを使うと楽

B

f[1] = x; f[2] = y; ∀i(i >= 2) f[i] = f[i-1] + f[i+1];

f[n]を10⁹+7でわったあまりを求める。

nが10⁹までなので全部計算するのは無理そう。20ぐらいまで計算してみると、6回でループしてることがわかる

example 1

2 3 1 -2 -3 -1 2 3 1 -2 -3 -1 2 3 1 .....

つまりn%6で割ってみればいいじゃん、

C

n*mのグリッドにk回、線を引いた時の最小面積を最大化する。

D

N個の都市とM個の道路の情報が与えられる。道路は双方向に通じてる。0からK個の都市に対して直接線路がある。廃線にしても最短経路の変わらない線路の数を数える。

直接線路を通じていくのが最短経路でない時、その線路は不要。 ダイクストラ法で解ける。解説読んで実装してみたらMとKが馬鹿でかいケースでTLE出してたので入力見てみたら、0から同じ都市に対して複数の路線があった。

E

codeforcesで流行りのconstractiveとかいう