naoya_t@hatenablog

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

SRM620

SRMに連続参戦するの久しぶり。


とりあえずレーティング少し上げた。(Volatility少し下げたか)
黄色キープ。
f:id:n4_t:20140511085719p:plain

===
250-500-800て。(Hardは開いてない)

Easy (250) PairGame

  • (x, y) の次のステップは (x+y, y) か (x, x+y)
  • てことは (a, b) の前のステップは、a>bなら (a-b, b) で、a
  • てな感じで、遡れなくなるまで、即ち (n, n) の形になるまで遡る
  • (a, b) から遡ったルートと、(c, d) から遡ったルートが合流するなら、その分岐点のx,yの和を答える
  • ルートの合流地点求めるのに集合演算使ってるけどね
  • 211.96pt; AC
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
#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> II;

class PairGame {
 public:
  set<II> pg(int a,int b){
    set<II> s;
    s.insert(II(a,b));
    while(true) {
      if (a>b) {
        a -= b;
        s.insert(II(a,b));
      } else if (a<b) {
        b -= a;
        s.insert(II(a,b));
      } else {
        s.insert(II(a,b));
        break;
      }
    }
    return s;
  }
  int maxSum(int a, int b, int c, int d) {
    set<II> ab = pg(a,b);
    set<II> cd = pg(c,d);
    vector<II> ix(sz(ab) + sz(cd));
    auto end = set_intersection(all(ab), all(cd), ix.begin());
    int cnt = end - ix.begin();
    if (cnt == 0) return -1;
    int best = 0;
    rep(i,cnt){
      int sum = ix[i].first + ix[i].second;
      if (sum > best) best = sum;
    }
    return best;
  }
};

Medium (500) CandidatesSelection

  • 各skillでソートした時の順番を保持しておく(同順情報も持たせてBBAAなら"2200"みたいな)
  • resultから逆に辿って、辻褄のあうソートがあれば遡っていく
  • とか書いてたけど時間切れ
  • 出来たコードは最悪ケースでTLE(そりゃそうだ)
  • DPとかしないと駄目じゃね?

以下TLEコードのまま。

using namespace std;
#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(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> II;

class CandidatesSelection {
  int N, M;
  vector< vector<int> > sortloc; // 0202

  vector<int> sorting(vector<string>& score, int m){
    vector<vector<int> > la(26, vector<int>());
    rep(i,N) {
      int si = score[i][m] - 'A';
      la[si].pb(i);
    }
    vector<vector<int> > res;
    rep(i,26){
      if (sz(la[i]) > 0) res.pb(la[i]);
    }

    vector<int> loc(N);
    int c=sz(res),l=0;
    rep(i,c){
      int d=sz(res[i]);
      rep(j,d) {
        int o=res[i][j];
        loc[o]=l;
      }
      l += d;
    }
    return loc;
  }

  bool eq(vector<int>& a, vector<int>& b) {
    int al=sz(a), bl=sz(b);
    if (al!=bl) return false;
    rep(i,al){
      if (a[i] != b[i]) return false;
    }
    return true;
  }
  bool match(vector<vector<int> >& sr, vector<int>& res) {
    int a=sz(sr);
    int c=0;
    rep(i,a){
      int b=sz(sr[i]);
      vector<int> tmp;
      rep(j,b) tmp.pb(res[c++]);
      sort(all(tmp));
      if (!eq(sr[i],tmp)) return false;
    }
    return true;
  }

  vector<vector<int> > clusters(vector<int>& vo, vector<int>& gi){
    vector<vector<int> > tmp(N);
    rep(j, sz(vo)){
      int o = vo[j];
      tmp[o].pb(gi[j]);
    }
    vector<vector<int> > cl;
    rep(j,N){
      if (sz(tmp[j]) < 2) continue;
      cl.pb(tmp[j]);
    }
    return cl;
  }

  vector<int> strans(int m, vector<int>& gi){
    vector<int> vo; //0033
    rep(j, sz(gi)){
      vo.pb(sortloc[m][gi[j]]);
    }
    return vo;
  }

  bool asc(vector<int>& v){
    rep(i, sz(v)-1){
      if (v[i] > v[i+1]) return false;
    }
    return true;
  }

  bool same(set<vector<int> >& s1, set<vector<int> >& s2) {
    int cnt = 0;
    tr(it, s2){
      if (found(s1, *it)) ++cnt;
    }
    return (cnt == sz(s1));
  }

  map<set<vector<int> >,bool> mm;
 public:
  bool sub(set<vector<int> >& g) {
    int gn = sz(g); if (gn == 0) return true;
    if (found(mm,g)) return mm[g];

    rep(m,M+1){
      int p = true;
      set<vector<int> > g2;
      tr(it,g){
        vector<int> gi = *it;//20
        vector<int> vo = strans(m, gi);
        if (!asc(vo)) { p=false; break; }

        vector<vector<int> > cl = clusters(vo, gi);
        g2.insert(all(cl));
      }
      if (same(g, g2)) { p=false; continue; }
      if (!sub(g2)) { p=false; continue; }

      if (p) {
        return mm[g] = true;
      }
    }
    return mm[g] = false;
  }

  string possible(vector<string> score, vector<int> result) {
    N = sz(score);
    M = sz(score[0]);

    sortloc.clear();
    vector<int> iota(N); rep(i,N) iota[i] = i;
    sortloc.pb(iota);
    rep(m,M){
      sortloc.pb( sorting(score, m) );
    }

    set<vector<int> > g;
    g.insert(result);
    return sub(g) ? "Possible" : "Impossible";
  }
};

Hard (800)

  • 開いてない