SRM487

TopCoder

信頼と実績の問題クオリティーで楽しめた回でした。

  • -

250. BunnyComputer

問題：n個の数字の配列から，K個間隔の2個のペアを取っていく。とれる数字の和の最大値を求める

  • う…うさぎだと…。
  • とりあえずペアを取る操作で関係するのはK個離れた数字どうしなので分けてみる。
  • K個とばしで得た数列上で，隣接する数字を取った時にとれる数字の和の最大値を取れば良くなる
  • DPできそうだなぁ…。
    • DP[i] = max(DP[i-1], DP[i-2]+(p[i-1]+p[i])) とかそんな感じ
  • 書いたら答えが合ったので提出してしまう。

550. BunnyExam

問題：k以下の自然数からなる長さmの数列のうち，隣接する2要素の値が異なり，linkage[2*i]番目の要素とlinkage[2*i+1]番目の要素の値が等しいものを考える。このような数列をランダムに2つ選んだとき，一致する要素の数の期待値は？条件を満たす数列がなければ-1.0を返す。

  • mもkも最大10億。linkageの要素数が最大20。
  • mもkもやたら大きいから期待値は式で出るんだろうなぁ…。
  • と，悶々としつつ40分くらいが経過
  • 分からなすぎるのでm=2でlinkageが空の場合を考えてみる。
    • 期待値を計算してみたら2/k
    • ひょっとして期待値はm/kで出るのか…？
  • m=3でlinkage = {0, 2}の場合を考えてみる。
    • 期待値を計算してみたら3/k
    • ひょっとしてlinkageの条件を満たす数列が存在すればm/k…？
  • プログラムを書いたら-1.0になるもの以外はサンプルが通ったのでそういう事にする。
  • 問題は，数列の存在判定をどうするかだけど…。
  • とりあえずk=1かつならm>1なら存在しない
  • k=2で，linkage[2*i]とlinkage[2*i+1]の偶奇が異なるものがあってもダメ
  • k=3なら良いんじゃね…と思ったところ、普通に反例が見つかる。
  • こういうときはとりあえずグラフにして考えるんだ…。
    • linkage[2*i]とlinkage[2*i+1]のペアをノードとする。
    • 数字が異ならなきゃいけないノード間に枝を張る。
    • これはk彩色問題…！
  • わずかな残り時間を気にしつつ可能な限りの速度でグラフ彩色を実装。
  • したけど，さすがにシステムで落ちました。いい加減にライブラリ化すべきか…。
  • -

結果：AC / WA / -- ，224.05pt, 160位
レーティング：2193 -> 2186


今回はMedium > Hardだったという説もあるので，実はHardを開くべきだった気もしますが，
問題がとても面白く、良い線までは行けてたので後悔はしていません。
しっかし、2200の壁は厚いなぁ…。