Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-05-21

SRM470

02:05 | SRM470 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM470 - naoya_t@topcoder SRM470 - naoya_t@topcoder のブックマークコメント

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 DoorsGame 提出 - passed - 192.41
- 500 DrawingLines 間に合わず - - - 0
- 1000 -- 開いてない -

Easy(250): DoorsGame

  • ドアの色を、左の人の持分と、右の人の持分に分ける
  • ABAB とかなら A,B みたいにまとめられるので
  • それぞれset<char>とかで持っとく
  • あとは、相手が持ってなくて自分が持ってる色を優先的に開けていく勝負
  • 高々16色しかないので総当たりで調べても大丈夫でしょ
  • 以下、愚直なコード
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class DoorsGame {
 public:
  int determineOutcome(string doors, int trophy) {
    int n=sz(doors);
    set<char> js, gs;
    rep(i,n){
      if (i<trophy) js.insert(doors[i]);
      else gs.insert(doors[i]);
    }
    int jl=sz(js), gl=sz(gs), ml=min(jl,gl);
    for(int t=1; t<=ml*2; ) {
      if (js.empty()) return gs.empty() ? 0 : t;
      else if (gs.empty()) return -t;

      bool jd=false, gd=false;
      tr(js,jt){
        char jc=*jt; if (found(gs,jc)) continue;
        js.erase(jc); if (js.empty()) return t;
        jd=true; break;
      }
      if (!jd) {
        tr(js,jt){
          char jc=*jt;
          js.erase(jc); gs.erase(jc);
          if (js.empty()) return gs.empty() ? 0 : t;
          else if (gs.empty()) return -t;
          jd=true; break;
        }
      }
      t++;
      
      tr(gs,gt){
        char gc=*gt; if (found(js,gc)) continue;
        gs.erase(gc); if (gs.empty()) return -t;
        gd=true; break;
      }
      if (!gd) {
        tr(gs,gt){
          char gc=*gt;
          gs.erase(gc); js.erase(gc);
          if (gs.empty()) return js.empty() ? 0 : -t;
          else if (js.empty()) return t;
          gd=true; break;
        }
      }
      t++;
    }

    return 0;
  }
};

Medium(500): DrawingLines

  • 全部パターン見ると1億回ループとかなるよね...死ぬよね
  • クロスする箇所の数=バブルソートの回数か
    • 自分より左で大きい数の個数、の和
  • 場所が決まってる数と、決まってない数(集合)の位置と内容がわかってるので確率求められるはず
  • なのに
  • あるぇー
  • 間に合わなかった><

Hard(1000): 開いてない

Challenge Phase:

  • 落とさず、落とされず
  • 部屋に赤い人が2人いるからここで撃墜されなければ安心、とか思ってたけど赤の1人がfailed system testとか

System Test

  • (o - -)
  • 部屋で500通ったの1人だけ... 250も生存者10名
  • DIV1全体では、wataさんの1000点がfailedで、1000点全滅か

Room: 3/20

全体: 141/795 …nodchipさんの2つ下、gusmachineさんの3つ下。

1302→1453 黄色復帰までもう一声!

http://gyazo.com/ce2a72573c4832fb75e2cce36d7cef31.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100521