Codeforces 138.1

Codeforcesって何が面白いんだろう？？？

A

()[]からなる文字列で、それぞれの括弧の対応が取れている文字列について、一番[をたくさん含むものを答えよ、という問題。

parseしましょう系。完全に慣れの問題。やったことないと色々と大変。

B

文字列が二つ与えられる。一つ目の文字列から順番を変えずに文字を拾って二つ目の文字列を作ることを考える。一つ目の文字列のすべての文字について何らかの方法で二つ目の文字列を作ることができるか答えよ、という問題。

取り敢えず一つ目の文字列を先頭から見ていって二つ目の文字列の何番目の文字になることができるかの最大値を覚えておく。次の文字は前の文字の次か、それよりも前の文字のどれかになることができる。最終的に最後の文字が最後の文字になることができれば良い。途中でどの文字にもなれないものが登場したら失敗。

C

整数列が与えられるので、i番目までの合計値をi番目の要素にするという処理をK回適用した結果を答えよ、という問題。

サイズが小さいなら行列乗算するだけ。実際にはその行列のべき乗が組み合わせで求められるので、行列作って計算してやるだけ。べき乗一回でもしたらTLEする。

D

見てない。

E

見る気もない。