581.1

メモ忘れ...。

250

連続するNマスにどのようにモノが配置されているかが与えられる。連続するKマスにいくつモノが配置されているかの情報が与えられるが、どの位置のものかは分からない。同じ区間についての情報が複数ないことと、全体として正しい情報が与えられていることを前提として、情報が与えられているか否かをそれぞれのマスについて答えよ、という問題。

要はそれぞれのマスについて、情報が取得されているのであれば、同じ個数の情報が存在するはず。ただし、そのマスを含まない情報すべてでカバーされている場合は、そのマスの情報は含まれていない可能性がある。といったことを一通り調べてやるだけ。

500

木が2個与えられる。それぞれのノードを一対一にランダムにつなぐことを考える。それぞれの木を一度ずつ通り、閉路を作るとき、閉路長がKのものになるものの個数の期待値を答えよ、という問題。

取り敢えずそれぞれの木について、二点間の距離を全部求める。後は二地点間の距離と、それを実現するパスが何通りかを覚えておく。二つの木について、結合する二本の辺を加えた後の合計値がKになるように閉路を構築してやればいい。期待値なので、生成確率を適当に割り算してやればおしまい。

900

白と黒のマスが二次元平面上に配置されている。自分と隣接するマスの白黒を反転させる操作、または隣接するマスの白黒を反転させる操作を適用して、全体を黒いマスにしたい。二種類の操作が同じ行または列のマスに適用されることがないようにするとき、必要な最小回数を答えよ、という問題。

各列についてどの操作をしたか、と直近二列くらいを覚えておいて、ひたすら探索するだけ。直近二列が分かっていることで、次の列にする操作は一意に決まる。最初の列にやる操作だけ全パターン試してやればおしまい。