読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

SRM541 - Redcoderキラーセット

o-- 96.62点 434位 1575→1586
writerは@semiexpさん。

開戦前のアリーナで

(」・ω・)」うー!(/・ω・)/にゃー!」

とか連投してたら日本人が次々(」・ω・)」うー!(/・ω・)/にゃー!言い始めて楽しかった。感染力高い。

Easy(250) AntsMeet

  • 蟻と蟻の全組み合わせについて衝突イベントが起こるとしたらその時刻を計算、ソートして早い順に見ていくコードを書いた。というかそれを書くのに妙に時間がかかってしまった (63'10'')

  • 3匹以上が対消滅することもあるし、格子点でない場所(1/2)で衝突する場合もある
  • 初期座標の範囲が狭いので単純なシミュレーションで十分いけるじゃないか><と終了数分前に気づいて書いてみてやっぱり行けてショック
  • Challenge PhaseにDiv1 Summaryを見てたら赤い人達がぼろぼろ落ちていく
    • 0.5
  • おかげでこんなのろまなのにレーティング微増
#define sz(a)  int((a).size())
#define pb  push_back
#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 AntsMeet {
 public:
  int countAnts(vector<int> x, vector<int> y, string direction) {
	int n=sz(x);
    int dx[128],dy[128];
    dx['E']=1; dx['W']=-1; dx['S']=0; dx['N']=0;
    dy['E']=0; dy['W']=0;  dy['S']=-1;dy['N']=1;

    priority_queue<pair<int,pair<int,int> > > pq;
    for(int i=0;i<n-1;++i) {
      int dix=dx[direction[i]], diy=dy[direction[i]];
      for(int j=i+1;j<n;++j){
        int _x=x[i]-x[j], _y=y[i]-y[j];
        _x*=2; _y*=2;
        int djx=dx[direction[j]], djy=dy[direction[j]];
        int d_x=djx-dix, d_y=djy-diy;
        if (d_x==0 && d_y==0) continue;
        int qx,rx, qy,ry;
        if(_x==0 && _y!=0){
          if(d_x==0 && d_y!=0) {
            qy=_y/d_y; ry=_y%d_y;
            if (qy>0 && ry==0) {
              pq.push(make_pair(-qy,make_pair(i,j)));
            }
          }
        }else if(_y==0 && _x!=0){
          if(d_y==0 && d_x!=0) {
            qx=_x/d_x; rx=_x%d_x;
            if (qx>0 && rx==0) {
              pq.push(make_pair(-qx,make_pair(i,j)));
            }
          }
        }else if (_x!=0 && _y!=0){
          if(d_x!=0 && d_y!=0) {
            qx=_x/d_x; rx=_x%d_x;
            qy=_y/d_y; ry=_y%d_y;
            if (qx==qy && rx==0 && ry==0 && qx>0 && qy>0) {
              pq.push(make_pair(-qx,make_pair(i,j)));
            }
          }
        }
      }
    }

    int ans=n;
    set<int>dd;
    while(true){
      set<int>dt;
      int tmin = 999999;
      while(!pq.empty()){
        int t=-pq.top().first;
        if (t<tmin) tmin=t;
        if (t>tmin) break;
        
        int ti=pq.top().second.first;
        int tj=pq.top().second.second;
        pq.pop();
        
        if (found(dd,ti) || found(dd,tj)) continue;
        if (!found(dt,ti)) {
          dt.insert(ti);
        }
        if (!found(dt,tj)) {
          dt.insert(tj);
        }
      }
      if (tmin == 999999) break;
      
      int d = sz(dt);
      ans -= d;
      tr(dt,it) dd.insert(*it);
    }
    return ans;
  }
};

単純シミュレーション版:

#define sz(a)  int((a).size())
#define pb  push_back
#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 AntsMeet {
 public:
  int countAnts(vector<int> x, vector<int> y, string direction) {
    int n=sz(x);
    int dx[128],dy[128];
    dx['E']=1; dx['W']=-1; dx['S']=0; dx['N']=0;
    dy['E']=0; dy['W']=0;  dy['S']=-1;dy['N']=1;

    set<int> dd;
    rep(t,2002){
      map<pair<int,int>,vector<int> > mm;
      rep(i,n){
        int di=direction[i];
        x[i]+=dx[di]; y[i]+=dy[di];

        if(found(dd,i))continue;
        pair<int,int> k(x[i],y[i]);
        if(!found(mm,k)) mm[k].assign(1,i);
        else mm[k].pb(i);
      }
      tr(mm,it){
        if(it->second.size() >= 2) {
          tr(it->second,jt) dd.insert(*jt);
        }
      }
    }
    return n-dd.size();
  }
};

Medium(550) AkariDaisukiDiv1

  • 残り10分強で問題を眺める。
  • ドラゴンブック的な何かが脳裏をかすめる
  • どう考えても実装間に合わなさそうなので数分で諦めてEasy問題を見返した。

Hard(1000) XorLife

  • 終わってから問題見た。Lifeゲームの変形版。
  • 個別に伝播したものをXORしたら答えが出るのでなんか綺麗に整理できそうな気がする(ていうか問題名のXorがネタバレ)