Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-28ARC003

ARC003 A GPA計算

|  ARC003 A GPA計算 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 A GPA計算 - hama_DU@TopCoderへの道

  • 一瞬。
    • 足して、平均を取るだけ。

ARC003 B さかさま辞書

|  ARC003 B さかさま辞書 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 B さかさま辞書 - hama_DU@TopCoderへの道

  • List<String> に反転した文字列を突っ込む。
    • new StringBuffer(S).reverse().toString()
  • ソートする。
    • Collections.sort()
  • 順番に出力。
    • 出力するときに反転を元に戻す

ARC003 C 暗闇帰り道

|  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道

  • 方針を考える。
    • ダイクストラする?
      • (現在位置,時間)を状態に持つ
      • 500 * 500 * 1000 ぐらいになっておそらく間に合わない。
  • しばらく考える
    • 二分探索で、通れる明るさの上限を決めてしまおう
      • これだと現在位置だけを状態に持てばいいので、 500 * 500 * (二分探索の回数) で済む。
    • これでよさそう。
  • 実装
    • 特に詰まること無くサクサク。
    • 各明るさの初期値 (i:1〜9) について、n時間たった時の明るさを予め dvalue[i][n] に計算しておく
  • 出してみる。
    • TLEしてしまう。あれ?
    • 二分探索で誤差がe-10ぐらいになったら打ち切るようにしてみる
  • 再提出
    • 今度はWA
    • 到達不可の場合は -1 を出力しなければならないが、その判定がミスってる
      • 二分探索する前に、到達可否を調べるコードを書いた。
  • 提出。やっとACがもらえた。この時点で残り30分。

ARC003 D シャッフル席替え

|  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道

  • これは難しそう・・・
  • 制約の小ささから、bitDP的なことができるのではと思ってみる
    • dp[K][P] : K回席替えした時、禁止パターンの出現組合せがPになってる確率
    • でも、更新式が思い浮かばない。
    • 紙に書いてみても、
  • 素直に順列を全探索か?
    • 制限時間10秒あるし・・・
  • 書いてる途中にコンテスト終わった

コンテスト後

  • 答えの誤差が 0.002 まで許されることから、モンテカルロ法が使えるらしい。
    • 実際にランダムにK回席替えをして、禁止パターンになってるかどうか調べるという実験をする。
    • 成功数 / 試行回数 が答え
  • 制限時間ギリギリまで実験するコードを書いたら通った。