SRM509

TopCoder

前夜は夜更かししてE3の中継を見てたので、だいぶ眠い感じで参戦。

  • -

300. LuckyRemainder

問題：与えられた数字の空でない全ての部分列の和を9で割った余りを求める

  • 9で割った余りとか桁ごとに使う回数の和を取るだけじゃないかｗｗｗ
  • と思ったものの、使う数字の集合を変える問題だと思って答え合わねーってなった
  • 問題を読み間違ってたことに気づいて慌てて修正
  • するが、わずか数行のコードに2ヶ所のバグを埋め込んで詰まる
  • 結果、瞬殺ゲーっぽい問題なのに15分もかかって残念な感じだった

500. PalindromizationDiv1

問題：決められた挿入・削除・置換操作を使って、最小コストで与えられた文字列を回文にする問題

  • 前後から1文字ずつ対応させてく感じのDPっぽい気がした
  • 1文字ずつ対応させる方法がいろいろありそうだったので、まず列挙
    • 同じ文字ならキープ
    • 違う文字なら片方を消し去ってみる(置換→消すのコンボも可)
    • 両方とも置換してみる
    • 片方に挿入してみる(挿入→置換のコンボも有りうる)
    • 片方は(挿入→置換)で、もう片方は置換
  • もうないかな…。不安
  • ワーシャルフロイド的なことも前処理で必要っぽい
  • typoがこわいので、列挙した仕様を落ち着いて1つずつ実装した
    • 結果的にtypoはあって、書き上げた後デバッグに15分近くかける羽目に
    • Sampleじゃ拾えないバグだったので、見つかっただけ良かった

Challenge Phase

  • 500は絶対に対応操作の列挙し忘れとかいると思った
  • けど、1回失敗した挙句、1人も落とせなくて悲しかった
  • -

結果：AC / AC / -- ，-25, 403.30pt, 39位
レーティング：2302 -> 2360


250がだいぶ眠たそうな感じで残念でしたが、
500は目が覚めて、珍しく実装重めな問題が通ったので良かったです。