SRM 619 Div2 Codeforces #FF Div2

SRM 619 Div2

Easy

N人の社員のいる会社。0番目以外のi番目の社員にはsuperior[i]という上司がいる。各社員はひとつの部署を持っている。部署の中で同じ仕事をしている社員のいない部署の数はいくつか。

それぞれの部署に対して好ましい部署か調べる。

Med

1〜N番目の人が円形に並んでる。ここから(N-1)人を取り除いて一人にする。kターン目にはk3番目の人が消える。

queueを使うと時間が大変なのでmodを使ってvectorなりでシュミレーションする、オーバーフローに気をつける

Hard

N人の社員を採用するか、iを採用するにはvalue[i]だけコストがかかる。i<jであるiとjの社員において

  • 2人を採用するとearning[i][j]の利益。 * 採用しないとearning[i][j]の損
  • 片方だけだと何も起きない

利益を最大化

解説を読んで解いた。

Codeforces #FF Div2

A

pの大きさのハッシュ配列がある。n個の要素を格納したい。

h(x) = x mod p

最初に衝突するのはいつか

シュミレーションする。

B

sが与えられる。sにk文字を追加する。各アルファベットに対して、価値が決まっている。i文字目の価値はi*s[i]の価値

価値の一番高いのを追加していく。

C

数列が与えられて、連続する列が単調増加列である最大の長さを求める。一つの要素を任意の数に変更できる。

DPらしいです