naoya_t@topcoder

SRM470

02:05 |

DIV	level	問題名	競技中	後で	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 黄色復帰までもう一声！