Hatena::Grouptopcoder

ir5は引退した

 | 

2011-01-13

SRM 493

17:37

新年1回目のSRM


DivLevelProblemNameStatus
1300StonesGamePassed System Test
1450AmoebaCodePassed System Test
11000コンパイルしただけCompiled

300

  • ろめおとすとらんじぇれっと? (読み方あってるのかしらない) 新キャラっぽいけどwriter誰なんだろう… まぁいいや
  • 黒い石がN個(N<=100万)横に並んでいて,そのうちM番目にある1個だけが白い石である.
    • ある2人が次の操作を交互に行っていく:連続するK個の石の区間をとり,その区間の石の順番をひっくり返す.
    • 最初に白い石をL番目に持っていったほうが勝ちというルールで2人がゲームをするとき,2人が最適な手をとり続けた場合先手勝ちになるか後手勝ちになるか引き分けになるか決定せよ.

  • うーん,なんぞこれは
    • 状態はループしうるのでdfsとかDPっぽいアプローチでは無理
    • bfsして決定するのか? それちょっと面倒…
    • うーむ
    • というかそもそも,状態数が100万通りあって,さらにある状態から次の状態に移るのにも最大で100万×適当な定数くらいの手があるから,bfsでも時間厳しくても無理っぽい.どうやるのだ…

  • よく考えると,先手は1ターン目で勝利できなければ1手目が先手勝ちになることはありえない.
    • なぜなら,2ターン目以降,後手は先手の打った手を巻き返すということを繰り返せば,少なくとも引き分けには持ち越せる. (石をひっくりかえすという操作は可逆な操作である)
    • これは調べるのは簡単.んで,後手必勝になることってあるんだろうか….
    • サンプル見た感じあるっぽい.
    • 後手必勝もおんなじ感じなんでは? これでできた,はず….
  • 適当に書く.しかしこれが悲劇を生むことになる.

  • できたのでテスト.サンプル全部通ったし,サンプルは割と強固そうに見える(注:実はそんなことはない)ので大丈夫そう,提出. → 210ptsくらいだった記憶.

450

  • 450ということは簡単なはず.(実はそうでもない)
  • アメーバとか書いてるけど別にアメーバ関係ない.
    • "0001230003322" みたいなstringとK(1<=K<=7)が与えられる.'0'を適当に1~Kまでのどれかの値に置換して,stringの中で同じ数字間の距離の最小値が最大になるようにしたい. (たとえば"13143"なら1の数字間の距離は2,3の数字間の距離は3なので,全体の距離の最小は2である)

  • DP臭する.
    • とりあえず,答えはかならず1~7までに収まるので,最低限必要な距離というのをfixしてそのもとで条件を満たすstringができるかを調べればいい.
    • stringができるかどうかを調べるのには… 7^7*50のDPとかでいいんじゃね? 計算時間はちょっと怪しそうだけどなんとかならんだろうか.
    • DPの式を書き下す.
      • DPよりはbfsで探索,とかの方が良さそう.
state[pos][d1][d2]..[dK] := pos文字目までを埋めるとき,1を過去d1マス目に使った,2を過去d2マス目に使った,… とするときに可能かどうか
  (ただしdiは最低限離したい距離よりは大きくならないようにする)
とすると,
state[pos][d1][d2]..[dK] = true ならば,

string[pos]=='0' ならば, di==離したい距離 となるdiに対して state[pos][d1+1]..[di=0]..[dK+1] = true で,
string[pos]==u+1+'0' ならば, du==離したい距離となっていれば state[pos][d1+1]..[du=0]..[dK+1] = true となる.

  • 間に合うか若干怪しい気もするけど間に合いそうでもあるので書いてみる
    • 実装はめんどうなのでset<vector<int> > とか使っている.大丈夫なのかわからんけど駄目だったら考える .
    • 最悪ケースを試す.1.5secくらいかかってるように見えるけどセーフっぽいので提出. 255.44pts

1000

  • 開いたが問題文長すぎて読む気しないので閉じた.記念にCompileした.

300(再)

  • やることがないので300の見直し
  • アルゴリズムは大丈夫のはずだよなぁ,先手は1ターン目で勝たないといけなくて,後手は2ターン目で勝てればよくて,…ん,本当にそうか?
    • 後手が勝つのは,全ての先手の1ターン目に対して,ゴールへ持っていく手が存在するとき,のはず.
    • なのに自分の書いたコードを見ると,ある先手の1ターン目の手に対して,ゴールへ持っていく手が存在するときに後手必勝だと返している,あきらかにおかしい!!

  • 書き直して再提出. 210pts→90.00ptsに.トホホ…
    • 順位かなり下がっていてまずいのでチャレンジに備える.

Challenge Phase

  • 300で同じようなミスをしている人がいる気がするので,探す.落とす.+50.00pts
  • もう1人450でTLEしそうな人がいたけど悩んでいたら時間切れになってしまった.
    • ただあとで聞いてみたところ,撃墜しようとしていたケースでは結局落ちなかったっぽいので結果としてはChallengeしなくてよかったと言える.

System Test

通りました

oox +50.00 395.44pts 35th place

2506->2533


今回ははまりどころが結構あったのか多くの人が落ちていました.今回はRoomの人たちがとても落ちていたので,もう1人くらい撃墜できたような気がしなくもないのですが時間も限られているので難しい.

300のResubmissionがかなり痛かったですが無事通ったんで結果オーライということで.

30位台をコンスタントに取り続けていきたいものです.


問題についてですが,今回のMediumは言うほど簡単でもなかった気がするし500でいいんじゃないかと思います.問題自体は面白かったです.

 |