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

naoya_t@hatenablog

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

SRM638

金曜日にagwさんクラスタ(Marathon勢多め)とお好み焼に行ってきて刺激されて。
半年ぶりのSRM参戦。

300-600-800とな
いずれにしてもEasyから開く方針

Coding Phase

Easy (300) ShadowSculpture

開いた。

1x1x1キューブで出来た三次元物体のxy面・yz面・zx面それぞれへの射影が与えられ、それと辻褄の合うような、「1つに繋がった」物体が存在しうるかどうか。

まず、xy面の影に、yz面の影を掛けあわせていく感じ。(論理積
xy面の影からyz面の影が不可能だと分かる場合はその時点で"Impossible"。
さらにそこにzxの影を掛けあわせていく。ここで不可能なら"Impossible"。
出来上がった物体が1つに繋がっていれば(ここはUnionFindね)"Possible"。2つ以上の島になってれば”Impossible”。

→WA(30'57'', 167.69pts→0.0pts)
3つの影からの合成だと、内側に(というかどの軸からも見えない影に)孤立したキューブが残ってしまってImpossibleと誤判定してしまうケース(しかもそれを消しても影は変わらなくて本当はPossible,みたいな)などがあるらしい。

うちの部屋はyellowとblueしかいなくて撃墜少なめだったけど、ほとんどsystem testで落ちてた。
Div1でこれ通せた人数はMediumより少なかった。

using namespace std;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);++var)

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size);
  bool unionSet(int x, int y);
  bool findSet(int x, int y);
  int root(int x);
  int size(int x);
};

class ShadowSculpture {
 public:
  int n;
  int b[10][10][10];
  string possible(vector <string> XY, vector <string> YZ, vector <string> ZX) {
    n = sz(XY);

    int cc=0;
    UnionFind uf(n*n*n);

    rep(x,n)rep(y,n)rep(z,n) b[x][y][z]=0;
    rep(x,n)rep(y,n){
      int s = (XY[x][y]=='Y')?1:0;
      rep(z,n) b[x][y][z] = s;
    }
    rep(y,n)rep(z,n){
      int s = (YZ[y][z]=='Y')?1:0;
      int cnt = 0;
      rep(x,n) cnt += b[x][y][z];
      if (s>0 && cnt==0) goto impossible;
      rep(x,n) b[x][y][z] &= s;
    }
    rep(z,n)rep(x,n){
      int s = (ZX[z][x]=='Y')?1:0;
      int cnt = 0;
      rep(y,n) cnt += b[x][y][z];
      if (s>0 && cnt==0) goto impossible;
      rep(y,n) b[x][y][z] &= s;
    }

    rep(x,n)rep(y,n)rep(z,n){
      if (!b[x][y][z]) continue;
      ++cc;
      int id=z*n*n + y*n + x;
      if (x<n-1){
        if (b[x+1][y][z]) uf.unionSet(id,id+1);
      }
      if (y<n-1){
        if (b[x][y+1][z]) uf.unionSet(id,id+n);
      }
      if (z<n-1){
        if (b[x][y][z+1]) uf.unionSet(id,id+n*n);
      }
    }
    if (cc==0) goto possible;

    rep(x,n)rep(y,n)rep(z,n){
      if (!b[x][y][z]) continue;
      int id=z*n*n + y*n + x;
      if (uf.size(id) == cc) goto possible;
      else goto impossible;
    }
 possible:
    return "Possible";
 impossible:
    return "Impossible";
  }
};

Medium (600) NarrowPassage2

開いた
左からDP?違うね
大きい狼からtreeにぶら下げていく?ちょっと違う。
大きい狼から順に、可動域(左右の自分より大きい狼だけ見て行って、swapできなくなる所まで)を調べていく。
自分より大きな狼の並び順は、swapさえできるならどうでもいい。(というか単純に掛けあわせていけばいい)

→AC(39'41'', 290.52pts)
これ通してたの部屋で5人だけだった

using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
typedef pair<int,int> i_i;

class NarrowPassage2 {
 public:
  int n;
  int count(vector<int> size, int mss) {// maxSizeSum
    n = sz(size);
    ll ans = 1L;
    vector<i_i> pos(n);
    rep(i,n) pos[i] = i_i(size[i], i);
    sort(all(pos)); reverse(all(pos));
    vector<int> rev(n);
    rep(i,n){
      rev[pos[i].second] = i;
    }
    rep(i,n){
      int s=pos[i].first, a=pos[i].second;
      int x=mss-s, c=1;
      for(int j=a-1; j>=0; --j){
        if (rev[j]>=i) continue;
        if (size[j]>x) break;
        ++c;
      }
      for(int j=a+1; j<n; ++j){
        if (rev[j]>=i) continue;
        if (size[j]>x) break;
        ++c;
      }
      ans = (ans * c) % 1000000007LL;
    }

    return (int)(ans % 1000000007LL);
  }
};

Hard (800)

3分ぐらい残ってたけど
開いてない

Challenge Phase


600みんなに開かれた(が落とされず)
300落とされた
Div1の他所の部屋では300大虐殺らしい。

System Test

600通ってよかった。最高レーティング更新!


f:id:n4_t:20141103183041p:plain