432.1

初めて全部時間内に解けました。

250

二次元に並んだランプを列単位で反転させる操作をK回行う。最終的にすべてのランプがついている行の数の最大値を答えよ、という問題。

行単位で見て同じものじゃないと最終的に一致しないので、全部つけられる行について、全く同じ内容の行がいくつあるか調べれば良い。

500

N個の文字列を任意の順番で結合して、ある文字の間に別の文字が入らないような文字列を答えよ、という問題。複数ある場合や、一個もできない場合はそう答える。

取り敢えず全部同じ文字からなる文字列を例外処理して、その文字から始まるかその文字で終わる文字列に結合してしまう。後はある文字で終わるものと、その文字で始まるものを結合する。途中で不自然なものができたらだめ。結合ができなくなった時点で、特定の文字が複数の文字列に存在するようならば、どう結合しても不可能。そのあとで、複数要素ある場合は任意の順番に並べられる。そうでなければそれが答え。

1000

N個の村の間にどのように道が配置されているかが与えられる。村の間に道を作るには両方の村の人口の総計だけコストが必要で、すべての村の間に何かしらのパスができるように道を作る。次に各村に任意の順番で1件ずつ家を作る。その時のコストは、その村と直接道がある村すべての人口の総計と、村に応じたコストの積だけコストが必要である。また作った家にはすぐに一人の人が住み、次からはその人がコストに計算されるようになる。最初の道を作ってから、村の人口を目標値にするまでの可能な最小コストを求めよ、という問題。

やたら長いけれど、MSTな問題。二つの村の間に道を作ると、道を作るコストと、両方の村に家を建てるコスト分だけ増えることになる。なのでコストの小さい道を順番に作って、すべての村が連結された状態にすれば良い。

ちなみに家を建てる順番は、コストの大きい村から順番に作っていけば良いことになる。