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

naoya_t@hatenablog

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

Google Code Jam 2014 - Round 1C

Google Code Jam Programming Contest

観戦してるだけってのも何だし、問題文は読めるのでカフェで解いてみた。
※Small/Largeデータがダウンロード出来るのは終戦後(20:30)Practice落ちしてから。

19:20開始
A) small 20:33 AC (8pt), large 20:33 AC (12pt)
B) small 20:35 AC (10pt)
C) small 20:50 AC (15pt)
ここまでで45点(1時間半でno WAなので458位相当)取れてるので、ここで参加しててもR2進出は出来たと思う。

続きを読む

SRM620

TopCoder Single Round Match Programming Contest

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)

  • 開いてない

SRM619

TopCoder Single Round Match Programming Contest

久々に参加するSRM

こないだのTCO R1CでVolatilityが上がってるから、ここで良い点を出せばスムーズに黄色に戻れるかも?(0完だと逆に急降下のおそれが)


去年の8/12に青に陥落し、一度は1200台までレーティングを下げてからの黄色復帰。
f:id:n4_t:20140506103458p:plain

それにしても 250-600-1000 って何?

続きを読む

Google Code Jam 2014 - Round 1B

Google Code Jam Programming Contest

Round 1Aで通過してしまって1Bは参加資格がないので、Practice落ちした問題を見てみました。

規定の2時間半でどこまで行けるか見たいので一応時間を計りながらね。
場所を転々としながら、A(small+large), B(small), C(small) までで通算1時間41分。これで46点確保。
A-largeで1回WAしてるので、1時間45分相当、ということでこれは732位ぐらい?連続でやって同じように落ち着いて考えられるかは分からないから単純比較は出来ないけれど、一応R2進出ラインは越えられて安堵。

続きを読む

2014 TopCoder Open Algorithm Round 1C(無事通過しました)

TopCoder Programming Contest

今度こそ通過
ooo +0/-0 1352.95pt 80th 1320→1432

レーティングも少し取り戻せました。
Round2でお会いしましょう!
(Round2はチャンス3回:(A)5/18 (B)6/8 (C)7/6 それぞれ日本時間の日曜1am*

続きを読む

Google Code Jam 2014 - Round 1A

Programming Contest Google Code Jam

まさかとは思いましたが1Aで通過です

A-small + B-small + C-どこがsmallやねん で62点、265位でした。

Large全部捨てました。
「Largeを取らずに通過」62点勢は9人でした。そのうちLargeを1度も開かずに通った3人に入ってしまいましたw

終わってからLarge問題を考えてみたらそんなに難しい話ではなく、あと1時間あれば満点、ってところでした。

この後 Round 1B, 1C があって、Round 2は日本時間5/31(土)23:00〜です。
開催スケジュール
Round 2で上位1000人に入るとTシャツGETできます。
Tシャツほしいですw

続きを読む

2014 TopCoder Open Algorithm Round 1B〈タイムシフト参戦記〉

TopCoder Programming Contest

registerしておきながら寝倒したので、翌朝Practice Roomでタイムシフト参戦してみた記。
Round1Cでお会いしましょう。

200-600-900て何

Easy (200) SpamChecker

問題ちゃんと読んでなかった。一瞬でもスコアが負になったらSPAMでいいのね。

600を通してたのが300人ちょいなので、事実上この200の早解き勝負だったと思う。
Practice Roomで195.77点。本番の950位相当なので予選通過ならず。

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

class SpamChecker {
 public:
  string spamCheck(string judgeLog, int good, int bad) {
    int score=0,n=sz(judgeLog);
    rep(i,n){
      switch(judgeLog[i]){
        case 'o': score += good; break;
        case 'x': score -= bad; break;
        default: break;
      }
      if (score < 0) return "SPAM";
    }
    return "NOT SPAM";
  }
};

Medium (600) WolvesAndSheep

時間内には解けず。
壁の位置を総当たり?間に合わないよね

水平壁パターンを総当たりして、それぞれの垂直壁候補を出しておいて、それを全て満たす位置に垂直壁を引けばよさげ
という所まで辿り着いて、実装を始めたところで時間切れ。

以下、2回WAして3度目に通せたコード。
WAの原因は「それを全て満たす位置」を探す際のパターンの網羅ミス。

#line 2 "WolvesAndSheep.cpp"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>

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())
#define cons(x,y) make_pair((x),(y))

class WolvesAndSheep {
  int H, W;
  vector<string> f;

  string reduce(int ys, int ye, bool& b) {
    vector<char> r(W, '.');
    rep(x,W) {
      int wc=0, sc=0;
      for (int y=ys; y<=ye; ++y) {
        switch(f[y][x]) {
          case 'W': wc++; break;
          case 'S': sc++; break;
        }
      }
      if (wc*sc) { r[x]='X'; b=true; }
      else if (wc) r[x]='W';
      else if (sc) r[x]='S';
    }

    return string(all(r));
  }

  vector<pair<int,int> > line(string& s){
    vector<pair<int,int> > ans;

    char last = '|';
    int last_ix = -1;
    for (int i=0; i<W; ++i) {
      if (last == '|') {
        if (s[i] == '.') {
          // |.....
          continue;
        } else {
          // |...[SW]
          last = s[i];
          last_ix = i;
        }
      } else {
        if (s[i] == '.') {
          // last_ix = i-1;
          continue;
        } else if (s[i] == last) {
          last_ix = i;
          continue;
        } else {
          // printf(" !%d %c|%c\n", i, last, s[i]);
          ans.pb(cons(last_ix, i-1));
          last = s[i];
          last_ix = i;
        }
      }
    }
    return ans;
  }

  map<vector<pair<int,int>>,int> mm;

  int row(vector<pair<int,int> >& ss) {
    if (found(mm,ss)) return mm[ss];

    int singles = 0;
    vector<pair<int,int>> doubles;

    int lscore = 0;
    // x-x
    tr(it, ss){
      int s = it->first, e = it->second;
      if (s == e) {
        singles |= (1 << s);
        ++lscore;
      } else {
        ;
      }
    }
    // x-y
    tr(it, ss){
      int s = it->first, e = it->second;
      if (s == e) {
        ;
      } else {
        bool already = false;
        for (int i=s,m=1<<s; i<=e; ++i,m<<=1) {
          if (singles & m) { already = true; break; }
        }
        if (!already)
          doubles.pb(*it);
      }
    }

    if (sz(doubles) == 0) {
      return mm[ss] = lscore;
    }

    int rscore = sz(doubles);
    int P = 1 << (W-1);
    for (int p=0; p<P; ++p) {
      if (p & singles) continue;
      bool bad = false;
      tr(it, doubles) {
        int s = it->first, e = it->second;
        //printf(" (%d %d)", s,e);
        bool covered = false;
        for (int x=s,m=1<<s; x<=e; ++x,m<<=1) {
          if (p & m) { covered = true; break; }
        }
        if (!covered) { bad = true; break; }
      }
      if (!bad) {
        int bp = __builtin_popcount(p);
        if (bp < rscore) rscore = bp;
      }
    }

    return mm[ss] = lscore + rscore;
  }

 public:
  int getmin(vector<string> field) {
    f.assign(all(field));
    H = sz(field); W = sz(field[0]);

    vector<vector<string> > red(16, vector<string>(16));
    vector<vector<vector<pair<int,int>>>> redp(16, vector<vector<pair<int,int>>>(16));
    vector<vector<bool>> bads(16, vector<bool>(16, false));

    for (int ys=0; ys<H; ++ys) {
      for (int ye=ys; ye<H; ++ye) {
        bool bad=false;
        red[ys][ye] = reduce(ys,ye,bad);
        if (bad) {
          bads[ys][ye] = true;
          redp[ys][ye] = vector<pair<int,int>>();
        } else {
          redp[ys][ye] = line(red[ys][ye]);
        }
      }
    }

    int best_score = (H-1) + (W-1);

    int P = 1 << (H-1);
    for (int p=0; p<P; ++p) {
      vector<int> cut(1, 0);

      int last = 0;
      bool bad = false;

      for (int y=1,m=1; y<H; ++y,m<<=1) {
        if (p & m) {
          cut.pb(y);
          if (bads[last][y-1]) { bad = true; break; }
          last = y;
        }
      }
      cut.pb(H);
      if (bads[last][H-1]) { bad = true; }
      if (bad) continue;

      set<pair<int,int>> ss;
      for (int i=0,c=sz(cut)-1; i<c; ++i) {
        int s = cut[i], e = cut[i+1];
        tr(i, redp[s][e-1]) {
          ss.insert(*i);
        }
      }

      vector<pair<int,int>> ssv(all(ss));

      int score = (sz(cut)-2) + row(ssv);

      if (score < best_score) best_score = score;
    }

    return best_score;
  }
};