Hatena::Grouptopcoder

ir5は引退した

 | 

2010-09-15

SRM 482

08:14

SRM481での零完の無念をなんとかする気持ちで参戦.


DivLevelProblemNameStatus
1250LockersDivOnePassed System Test
1500HanoiGoodAndBadPassed System Test
11000あけただけOpened

250

  • なんか2飛びで数字を除去,3飛びで数字を除去,4飛びで数字を除去,…とかやっていくらしい.Nは200万.
  • 普通にやればいいんでは? O(N) or (NlogN) がよい.
  • データ構造は… めんどいからsetでいいや.
  • 書く.6分くらい.
  • テスト.

  • …200万のケースでギリギリ2秒くらい掛かってる.
    • えええ,なにこれうざい…
    • O(NlogN)だからよさそうなんだけどなぁ.
  • よくわからんけど,駄目っぽいのでsetを普通の配列(bool[])にしてやってみる.同じ.
  • vector<int>でやってみる.eraseとかやってるせいでとても遅い.
  • うーん…

  • もしかして,愚直なシミュレートじゃなくて,規則性がある系?
    • ためしに1~200くらいまで吐いて見る.が,何も分からない.
  • うおおおお

  • よーわからんけど,t飛びのときに残る要素を,別のvector<int>にpush_backしていくとかはどうだろう.(書いていたときは気づかなかったが,eraseはvectorの要素数に比例するが,push_backは普通に末尾に数字を入れるだけなので圧倒的に速い.はず.
  • 普通に間に合った.答えもよさそう. → 提出.ここまで20分くらい.ちょっと遅すぎた.前回の二の舞になりそうで結構焦る.

500

  • ハノイの塔をごにょごにょ.
  • この前参加したZOJのコンテストとなんとなく雰囲気似てるなーと思ったけど,ハノイの塔の問題って大体が同じ雰囲気だな.
  • 適当に書いた.良さそうなので提出.ここまで50分くらい.

1000

  • 開いて閉じた.
  • やることがないし,お茶を買いに行った.

Challenge Phase

  • 500は大体似たような人が多かったので250を見る.みんなシミュレートやってるんじゃないかと思ってたけど意外といろんな方法でやってるげ.
  • 愚直にsetでやってる人がいたので,Challengeすべきかどうか悩んだけど撃墜.
  • listでやってる人がいて,試しにローカルで同じコードを写して実行したら結構怪しそうだったのでChallenge.
    • が,失敗.うーん,手元だとset使った実装と実行時間変わらないんだけど.なぜだ.運か.

結果

両方通った

o o x +25.0 496.19 63位

1907→2020


回復できたんで良かったです.

250はNの上限がなんで200万だったのかわからないし,もうちょっと小さめか,もうちょっと大きめにした方が良かったんでは… と思う.TLEを狙う系のChallengeがしづらい.

 |