488.1

難易度設定が謎なセットが続いているような気もします。

250

N人の既に知っている人と、M人の知らない人がいる状況で、ランダムに2人選んで情報を伝えるという作業をする。このとき、全員に情報が伝わるのにかかるステップ数の期待値を答えよ、という問題。

単純にDPするだけ。状態が変わらないことがあるので、自分の状態の値を変数にして式を立てて解く。

500

文字列AとBが与えられ、それぞれから二つの重ならない部分文字列を取る。A1+B1でできる文字列とA2+B2でできる文字列が等しくなるようにしたい。このとき、最長の文字列のうち、辞書順で最初のものを答えよ、という問題。

どうも全部探索して、効率良く求めればうまくいくらしい？

1000

2対1のゲームをする。ゲームは繰り返し行われ、各ステップでは、どちらかのチームが全滅するまで攻撃を行う。敵を攻撃すると得点がもらえ、味方を攻撃すると減点される。攻撃された人はそのステップはもう何もできない。得点と攻撃された回数が各人について与えられるので、ゲームが行われたステップ数の最大値と最小値を求めよ。

各ステップで攻撃された人のパターンは4通りになり、それぞれの中の得点分布を考えると9通り。前者はどれか一つのパターンの数が決まれば、他のパターンの数が求まるようにできている。

次に、式変形を行うと、後者のパターンのうち二つを固定すると、そういう状況が起こり得るかどうかが判定できるようになる。後はこれをコーディングするだけ。問題文の読解と実装の問題のように見えるが、ちゃんとTLEしない確証を得るのは大変そう。各ゲームで攻撃される回数が単調増加するので、実際に起こり得る範囲はかなり狭いはず、という程度。