Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-28ARC003

久々にコンテストの参加レポート。 3AC92分で 35位/300人ぐらい

問題結果タイム解法
AGPA計算+02:20実装
Bさかさま辞書+07:51文字列
C暗闇帰り道+262:16(+30)二分探索+BFS
Dシャッフル席替え--モンテカルロ法

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回席替えをして、禁止パターンになってるかどうか調べるという実験をする。
    • 成功数 / 試行回数 が答え
  • 制限時間ギリギリまで実験するコードを書いたら通った。

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM336 (Practice)

SRM336 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM336 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250ServiceNamesAccepted196.25実装
500LikelyWordWA0.00実装
1000ShadowOpened0.00幾何

SRM 336 ServiceNames

|  SRM 336 ServiceNames - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 ServiceNames - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7313

  • ん?問題の意図するところがわからない・・・
    • サンプルから察するにやるだけっぽい

続きを読む

SRM 336 LikelyWord

|  SRM 336 LikelyWord - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 LikelyWord - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7351

  • 辞書順でdictionaries[i]の前に来る、長さkの文字列を数え上げる。
    • 区間は引き算して求められる
      • この時、dictionaries[i]の文字数がkであった場合、あとで数えないようにフラグを立てておく
    • 最後の区間は 26^k から (dictionaries[len-1] の前に来る文字列数) を引いて求める

続きを読む

SRM 336 Shadow

|  SRM 336 Shadow - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 Shadow - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7336

  • 問題文をナナメ読みしてそっと閉じた
    • 後でちゃんと解く。

SRM337 (Practice)

SRM337 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM337 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250CardStraightsWA0.00実装
500BuildingAdvertiseOpened0.00データ構造
1000CountPalindromesOpened0.00DP

SRM 337 CardStraights

|  SRM 337 CardStraights - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 CardStraights - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7417

  • し、しまった・・・(無能)
    • ジョーカーが余るパターンで、左に配置するパターンを考慮してなかった

続きを読む

SRM 337 BuildingAdvertise

|  SRM 337 BuildingAdvertise - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 BuildingAdvertise - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7473

  • 僕の苦手なデータ構造を利用するタイプの問題。
    • やり方がいろいろあるらしい(スタックを使ったり、分割統治法をしたり。)
    • 要復習

続きを読む

SRM 337 CountPalindromes

|  SRM 337 CountPalindromes - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 CountPalindromes - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7418

  • 典型的な文字列回文DP
    • 左右どちらかに余る文字列パターンは 15 * 15 * 2 * 50 = 22,500 なので、文字列 -> 数にエンコードして持っておく
    • どの文字列パターンにどの文字列を当てるとどの文字列パターンになるか、という状態遷移関数を前もって作成しておく。
      • これをやらないと多分文字列操作コストが重くてTLEする。
  • 時間はかかったが、一発ACできた。

続きを読む

SRM338 (Practice)

SRM338 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM338 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250ImprovingStatisticsAccepted239.03二分探索
500RandomSwapsAccepted416.29確率
1000CakePartyOpened0.00