Yandex.Algorithm 2016 Online Round 2

Algorithm 2016 — Yandex.Algorithm 2016 Online Round 2 — Enter
午前3時からという日本人を潰しにかかったような時間だったけど、2完242位だった
これで総合4完327位なので、頑張ればTシャツいけそう？

A. Role Distribution

• 解法

問題文の例では長い部分文字列を作れば良いようにも見えるが、結局各文字が各役者のセリフに含まれているかが問題となる。
よってS[i]が各役者のセリフに調べているかどうかを調べて、coolさ最小のactorを選べばよい。
もしどの役者のセリフにもS[i]が含まれてなければ、-1を出力して終了する。

• 計算量

O(SM log w)

• コード

B. Binary Representation Game

• 解法

LからRまでの、各ビットに合計何個1が立っているかを求めれば、各ビットに対して、(ビットが立っている)*2 < L-R+1 ならば、そのビットを1に、それ以外はそのビットを0にすれば、期待値が最も大きくなる。

0からNまでを2進数表記したときの、各ビットに合計何個1が立っているかはlog(N)(=Nのビット数)で求めることができる。
参考: SRM543 div.1 250 EllysXors - n-knuu's logs

• 計算量

O(log^2 R)

• コード