499.1

問題自体は簡単。実装の仕方が難しい。

250

相異なるK人に、自分と同じグループの人は何人いるか、という問いをした結果が与えられる。このようなグループに所属する合計人数の最小値を答えよ、という問題。

同じ数を答えた人でグループを作り、余った人に関しては質問されていない人で補うということをやれば、全体の数が求まる。

550

見てない。

1000

ある文字列に変換操作を行って、作ることができる文字列が同じグループに所属しないようなグループ分けを考えるとき、グループはいくつ必要か答えよ、という問題。

文字列は各文字の登場回数で同値類分解できるような変換しかできない。後は同値類間での変換が有向グラフになるので、ループがあれば全体を別グループにして、そうでなければ、親とは違うグループにする。親と違うグループにするということは、一番重みの大きいパスがグループの数を決定するので、ループがなければDPすると求まる。