Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM340 (Practice)

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

DP回 こういうセットばっかりだったらいいのに

問題結果ポイントその他
250ProblemsToSolveAccepted231.59DP
500CsCoursesAccepted329.54DP
1000VegetableGardenOpened0.00

SRM 340 ProblemsToSolve

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

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

  • 動的計画法
    • 座標圧縮して [現在位置][最大][最小] でDPする

続きを読む

SRM 340 CsCourses

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

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

  • 動的計画法+辞書順最小経路復元
    • 状態は [month][theoreticalValue][practicalValue]
    • 経路復元付きの場合はメモ化再帰すると楽。

続きを読む

SRM 340 VegetableGarden

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

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

  • 面白い問題。
    • グラフに帰着できるような気がするが、どうすればいいかわからない
    • 答えは必ず偶数になる?
  • あとで解く。

SRM341 (Practice)

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

問題結果ポイントその他
250KLastNonZeroDigitsAccepted246.14実装
550LandAndSeaOpened0.00実装、BFS
1000ValidPlatesOpened0.00

SRM 341 ValidPlates

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

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

  • DP
    • 行列累乗すればいい気がする
  • まだ解いてない

SRM342 (Practice)

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

問題結果ポイントその他
250TagalogDictionaryAccepted181.71実装、ソート
500ReverseResourcesOpened0.00DP
1000DrivingAroundTLE0.00グラフ

SRM 342 TagalogDictionary

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

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

  • やるだけ。
    • Comparatorの中に変数を仕込む方法が分からなかったので仕方なくバブルソートでやった

続きを読む

SRM 342 ReverseResources

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

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

  • 動的計画法
    • 典型っぽいのでこのぐらいはサクッと解けるようになりたい

続きを読む

SRM 342 DrivingAround

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

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

  • 既視感のある問題。
  • だが、この問題は辺に重みがついているので違う問題になっている
    • 待てよ、重みが w >= 2 の時はダミーの頂点を w-1 個はさんでやることで重みなしのグラフにできるのでは
    • これで簡易版「いけるかな?」に帰着できた
  • しかし、最大でノードが 10 + 90 * 4 = 370個必要になる。
    • 相当スパースな行列になるが、累乗すると 370^3 のコストが重くのしかかる
    • しかも、「いけるかな」とは違い場合の数を求めなきゃなので、MOD操作のコストがものすごく重い。
      • YES/NO 問題だったらまだ救いはあったが・・・
  • この考え方ではダメのようだ。
    • 一応、書いて出してみるか・・・問題の条件を見落としてるかもしれないし。
      • 案の定TLE。dsyn-

その後

  • ノード数は実は50個用意すれば十分
    • あるノードから他のノードに向かう途中のダミーノードは共通にして使いまわせるため

続きを読む

2012-04-21SRM343, SRM344 (Practice)

SRM343 (Practice)

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

問題結果ポイントその他
250CDPlayerAccepted228.59実装
500MoneyGameWA0.00ゲーム
1000RefactorableNumberAccepted860.09実装

SRM 343 MoneyGame

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

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

  • ゲーム木実装するだけかな?
  • 書いたらサンプル通ったので出した
    • 愚直にやると計算量的に厳しいと思ったのでポットから取り出すコインの選択を貪欲法でやった
  • WA

その後

  • 愚直にやっても充分間に合った。
    • O(12^6) = 2Mちょい

続きを読む

SRM 343 RefactorableNumber

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

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

  • これ(難易度的に)250だろ・・・
  • 当時の本番後どんな反応だったかは想像に難くない

続きを読む

SRM344 (Practice)

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

問題結果ポイントその他
250VolleyballTournamentAccepted192.23全探索
500QuantumAlchemyTLE0.00探索
1000FairTournamentOpened0.00動的計画法

SRM 344 VolleyballTournament

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

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

  • 0点、1点、2点を取った試合数を全探索する。

SRM 344 QuantumAlchemy

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

http://www.topcoder.com/stat?c=problem_statement&pm=7540
  • 逆から考えていけばいいのではと思った
    • つまり、'X' だけの状態から反応を逆向きにして戻していく
  • 終了条件は、文字列が initial の subset になること。
  • TLEが不安だが他に思いつかないのでこのまま出してしまおう。

後で

  • wataさんのコード見た
    • 基本的な考え方は同じっぽい・・・
    • よく見ると、一度展開した文字は再度展開しないようにしてる
      • 無限に展開されるのを防ぐためか
    • また、状態を文字列そのものではなく残り必要な文字数で管理している
      • うまいなぁ

続きを読む

2012-04-20SRM345 (Practice)

マラソンマッチが終わったので練習再開。

問題結果ポイントその他
250PathfindingAccepted134.08場合分け
500StoneGameAccepted398.14数学
1000ByteLandOpened0.00グラフ

SRM 345 Pathfinding

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

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

  • 探索で解こうと思った
    • 無理だった
  • 結局場合分けした。
    • xとyは対称性を持つので片方が負の場合だけを考えれば良い
  • 解法の検討に色々迷走したので時間がかかってしまった。

続きを読む

SRM 345 StoneGame

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

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

  • 手で実験してみる
    • これ、総取りできるか、全部相手に取られるかのどちらかなのでは
      • 石の総数の偶奇で決まる気がする(奇数なら総取りできる)
  • でも、石の数が1の場合はまずそちらを取った方がいい
    • 複数ある場合は当然価値が高いものを取った方がいい
    • 相手も当然価値が高いものを優先して取るはず
  • 石の数が1の山をすべて取り終えたときゲームが始まる
  • 書いたらサンプル合った。
    • 証明はできないが正しい気がするのでそのまま出した

続きを読む

SRM 345 ByteLand

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

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

  • 貪欲で行ける気がするが、証明ができない
    • 距離を決めうちしてDPする系なのかな?
  • 後で解く

2012-04-10SRM346 (Practice)

三日ぐらい前にやった。

500が難しい回。1000に逃げたのは正解だと思ったがWAを食らう。

問題結果ポイントその他
250CommonMultiplesAccepted236.48最小公倍数
500HeightRoundOpened0.00貪欲法
1000MeteoritesWA0.00幾何

SRM 346 HeightRound

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

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

  • 貪欲法。難しい
    • editorialや他の人のコードを見ながら書いた。
    • 要復習

続きを読む

SRM 346 Meteorites

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

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

  • 各隕石ごとに他の隕石で覆われている部分をラジアンの区間で持つ。
    • 角度の計算はatan2を使うと場合分けしなくて済み楽。
  • 隕石が他の隕石に完全に含まれている場合に注意する

続きを読む