naoya_t@hatenablog

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

SRM530:出てないけど問題を見てみた

TopCoder SRMには1年ぐらい参加してなくて、今使ってるMacBook Airではまだ一度も参戦してないので動作環境整備から。

TopCoderに参加して何が良いかっていうと、単にパズルとして面白いってのもあるんだけれど、自分より若い人達が優秀であるという事実(そしてその若い人達)に出会える場であるという辺りかな。若者たちは強すぎるので、(池乃めだか的な意味で)ほどほどにしておかないとこちらが凹むけど。

で、Arenaを広げて今日やってたらしいSRM530の問題を見てみた。

Div2 Easy: GogoXBallsAndBinsEasy

Practice RoomでとりあえずDiv2 250問題を開ける。単に投稿機能の動作確認のため。(問題文はTopCoderのサイトかArenaで見てね)

以下、投げたコード:

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class GogoXBallsAndBinsEasy {
 public:
  int solve(vector<int> T) { // 10elem
    vector<int> T0(all(T));
    int N=sz(T);
    int maxmove = 0;
    while (next_permutation(all(T))) {
      int s=0;
      rep(i,N){
        if (T[i]>T0[i]) s+=T[i]-T0[i];
      }
      if(s>maxmove)maxmove=s;
    }
    return maxmove;
  }
};

投稿〜コンパイル〜システムテスト通してみた。まあそりゃDiv2 250だし通るわな、と。

Div1 Easy / Div2 Medium: GogoXCake

最初ビット演算を考えてなんか大げさなDFSを書いてて、盤面は最大で50x50だしこれでは最悪ケースで全然終わらないわけで、左上から見てるんだしその位置でカットできなかったらもう”NO"でいいんじゃないかと思って、問題よく見たらcutterの上下左右の辺それぞれどこか必ず1つはused cellがあるって制約書いてあるしそりゃそうかなと。

#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 GogoXCake {
  ll str2bin(string s){
    ll val=0LL;
    int n=sz(s);
    rep(i,n){
      val <<= 1LL;
      val |= ((s[i] == '.') ? 1LL : 0LL);
    }
    return val;
  }

  int Rck,Cck,Eck,Bck;
  int Rct,Cct,Ect,Bct;
  int Dr,Dc;

  vector<ll> ck, ct;
  set<vector<ll> > memo;

  bool sub(int depth){
    if (depth == 0) return true;

    if (found(memo,ck)) return false;
    memo.insert(ck);

    rep(sy,Dr+1) rep(sx,Dc+1) {
      // cut
      int did = 0, called = 0;
      rep(rt,Rct) {
        ll ct__ = ct[rt] << (ll)sx;
        if ((ck[rt+sy] & ct__) == ct__) {
          ck[rt+sy] -= ct__;
          ++did;
        }
        else break;
      }
      if (did == Rct) {
        if (sub(depth-1)) return true;
        else called++;
      }
      // uncut
      rep(rt,did) {
        ck[rt+sy] += ct[rt] << (ll)sx;
      }
      if (called) return false;
    }

    return false;
  }
  
 public:
  string solve(vector<string> cake, vector<string> cutter) {
    ck.clear(); ct.clear();
    Rck=sz(cake), Cck=sz(cake[0]), Eck=Rck*Cck, Bck=0;
    Rct=sz(cutter), Cct=sz(cutter[0]), Ect=Rct*Cct, Bct=0;
    rep(r,Rck) { ll row=str2bin(cake[r]); ck.pb(row); Bck+=__builtin_popcountll(row); }
    rep(r,Rct) { ll row=str2bin(cutter[r]); ct.pb(row); Bct+=__builtin_popcountll(row); }

    if (Bct==0) return (Bck==Eck) ? "YES" : "NO";
    if (Bck%Bct) return "NO";

    Dr=Rck-Rct, Dc=Cck-Cct;

    return sub(Bck/Bct) ? "YES" : "NO";
  }
};

まあこれで通るっちゃ通るんだけど格好悪い。Div1で一番早く解いた人のコードを見たらシンプルかつ適切な考え方をしていた。左上から見て行って、食べられた箇所に出会ったら、cutterの最上列の左上から数えて最初のused cellをそこに当てて、そこで切れなかったらアウト。それだけの簡単なチェックで良いのだった。

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class GogoXCake {
 public:
  string solve(vector<string> cake, vector<string> cutter) {
    int R=sz(cake),C=sz(cake[0]), r=sz(cutter),c=sz(cutter[0]);
    int ofs = 0; while (cutter[0][ofs]=='X') ++ofs;
    rep(Y,R) rep(X,C) {
      if (cake[Y][X]=='X') continue; //still contains
      if (Y+r-1 >= R || X-ofs+0 < 0 || X-ofs+c-1 >= C) return "NO";
      rep(y,r) rep(x,c) {
        if (cutter[y][x]=='.') { //eat
          if (cake[Y+y][X-ofs+x]=='.') // eaten
            cake[Y+y][X-ofs+x] = 'X';
          else
            return "NO";
        }
      }
    }
    return "YES";
  }
};

Div1 Medium: GogoXMarisaKirisima

サンプルケースぐらいなら通る程度のナイーブなコードを書いてみて、問題の意味は把握していることを確認したところまで。50シーンで全部双方向に繋げたようなケースでちゃんとお亡くなりになる。

#define mp(x,y) (((x)<<6)+(y))

class GogoXMarisaKirisima {
  int N;
  vector<vector<bool> > ch;

 public:
  int solve(vector<string> choices) { //2-50
    N=sz(choices);
    ch=vector<vector<bool> >(N, vector<bool>(N));
    rep(i,N)rep(j,N) ch[i][j] = choices[i][j] == 'Y';

    set< pair<int,set<int> > > v;
    set< set<int> > w;

    queue<pair<int,set<int> > > q; q.push( cons(0,set<int>()) );
    while (!q.empty()) {
      pair<int,set<int> > f = q.front(); q.pop();
      v.insert(f);
      int now = f.first;
      set<int> s = f.second;
      if (now == N-1) w.insert(s);
      rep(next,N) {
        if (next == now) continue;
        if (ch[now][next]) {
          int p = mp(now,next);
          bool to_remove = false;
          if (!found(s,p)) { s.insert(p); to_remove=true; }
          if (!found(v,cons(next,s))) {
            q.push( cons(next,s) );
          }
          if (to_remove) s.erase(p);
        }
      }
    }    
    return w.size() ;
  }
};

tomerun先生のコード見てみたんだけどなんでこれで解けるのか、コンビニの行き帰りに歩きながら考えてみたけどまだ分かっていない。

Div2 Hard: GogoXReimuHakurai

Div1 Mediumの問題とほとんど同じなんだけど、正の向きのジャンプしかできない制約になっている。なんかDPですらっと解ける気がしたんだけど出来てないなう。

結論

東方ぐらい知らないと最近のSRMの問題は解けない。いや、そうに違いない…