Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-01-15

過去問マラソン(#10):SRM152

過去問マラソン | 23:40 | 過去問マラソン(#10):SRM152 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#10):SRM152 - naoya_t@topcoder 過去問マラソン(#10):SRM152 - naoya_t@topcoder のブックマークコメント

過去問マラソン10回目。

  • （いまさらですが）listとかstackとかも使うようになった
  • （いまさらですが）vector<char>とstringの相互変換とか
  • （いまさらですが）assignが使いこなせるようになった
  • cpprefがすごく便利なのでボウズラボに足を向けて寝られない

Easy(250): LeaguePicks

  • 問題文の意味がいまいち分からない
  • だが解く
    • Sample Caseが通るように修正していく感じ
    • 不安なのでテストケースを追加
  • 218.14pt (11'11'')
    • passed system test
  • 問題読めてないのに通るのはあまり楽しくない
#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()

class LeaguePicks {
 public:
  vector <int> returnPicks(int position, int friends, int picks) {
    vector<int> res;
    for(int q=0;;){
      int next = q+position;
      if (next>picks) break;
      res.pb(next);
      q+=friends;

      next = q+(friends+1-position);
      if (next>picks) break;
      res.pb(next);
      q+=friends;
    }
    return res;
  }
};

Medium(500): QuiningTopCoder

  • Unefungeな言語で書かれたプログラムソースが与えられ、これがQuineになってるかを調べる。
  • とりあえずエミュレータ書いて
  • 80000サイクルでQuineな出力が得られない場合はTIMEOUT判定
    • 環境(IP,D,stack)をメモ化してみたりとか
  • 1投目: failed
    • 環境とっとくなら出力文字列も保存しないと駄目だ
  • 2投目: failed
    • ":"１文字のコードでメモ化が破綻する。メモ化やめてみてもいい？...別に80000サイクル回してもTLEにならないっぽいし
  • 3投目: passed
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#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())

// BEGIN CUT HERE
void dump_stack(stack<int> st){
  int n = st.size();
  vector<int> vec(n);
  rep(i,n) {
    vec[i] = st.top(); st.pop();
  }
  reverse(all(vec));
  rep(i,n) st.push(vec[i]);
  cout << vec << endl;
}
// END CUT HERE

class UnefungeEmulator {
 private:
  string code; int N;
  int IP, D, cycles;
  stack<int> st;
  stringstream output;
  bool error; string errormsg;

  //set<pair<pair<int,string>,pair<int,stack<int> > > > known;
  
 public:
  UnefungeEmulator(string source) {
    code = source; N = source.size();
    IP = 0;
    D = 1;
    cycles = 0;
    error = false; errormsg = "";
    //known.clear();
  }

  void push(int x) {
    if (x < -1000000000 || 1000000000 < x) {
      error = true;
      errormsg = "OVERFLOW";
      return;
    }
    st.push(x);
  }
  int pop(){
    if (st.empty()) return 0;
    int x = st.top(); st.pop();
    return x;
  }

  void run(){
    while (1) {
      if (error) break;

      string ostr = output.str();
      if (ostr.length() > 0) {
        if (ostr.length() == code.length()) {
          if (ostr == code) break; // QUINE
          else {
            error = true;
            errormsg  = "MISMATCH";
            break;
          }
        }
        if (ostr != code.substr(0,ostr.length())) {
          error = true;
          errormsg  = "MISMATCH";
          break;
        }
      }

      /*
      pair<pair<int,string>,pair<int,stack<int> > > key =
          make_pair(make_pair(IP,ostr), make_pair(D, st) );
      if (found(known,key)) {
        cycles = 80001;
        return;
      }
      known.insert(key);
      */
      
      int D_for_this_cycle = D;
      cycles++; if (cycles > 80000) break;

      switch (code[IP]){
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
          {
            push( code[IP] - '0' );
          }
          break;
        case '$':
          {
            pop();
          }
          break;
        case ':':
          {
            int x = pop();
            push(x); push(x);
          }
          break;
        case 'W':
          {
            int a = pop(), b = pop();
            push(a); push(b);
          }
          break;
        case ',':
          {
            int x = pop();
            char p = code[ abs(x) % N ];
            output << p;
          }
          break;
        case '+':
          {
            int a = pop(), b = pop();
            push( a + b );
          }
          break;
        case '-':
          {
            int a = pop(), b = pop();
            push( a - b );
          }
          break;
        case '#':
          {
            D_for_this_cycle *= 2;
          }
          break;
        case 'R':
          {
            D_for_this_cycle = D = -D;
          }
          break;
        case 'S':
          {
            int x = pop();
            push( x > 0 ? 1 : -1 );
          }
          break;
        case '_':
          {
            int x = pop();
            D_for_this_cycle = D = x % N; // ここの D_for_this_cycle = を忘れてて結果が合わず延々と悩んだ
          }
          break;
        case 'J': // jump
          {
            int x = pop();
            IP = abs(x) % N;
            continue;
          }
          break;
        case '@': // stops the program
          return;
        default: // illegal
          printf("ILLEGAL OP %c\n", code[IP]);
          break;
      }
      IP = (3 * N + IP + D_for_this_cycle) % N;
    }
    // next
  }

  string result(){
    if (cycles > 80000) return "TIMEOUT";
    
    stringstream msg;
    if (error) {
      msg << errormsg;
    } else if (output.str() == code) {
      msg << "QUINES";
    } else {
      msg << "BADEND";
    }
    msg << " " << (cycles - 1);
    return msg.str();
  }
  
};

class QuiningTopCoder {
 public:
  string testCode(string source) {
    UnefungeEmulator emulator(source);
    emulator.run();
    return emulator.result();
  }
};

Hard(1000):

SRM458 Div1 Hard: ModuloFourDivisor

過去問, 練習 | 22:39 | SRM458 Div1 Hard: ModuloFourDivisor - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM458 Div1 Hard: ModuloFourDivisor - naoya_t@topcoder SRM458 Div1 Hard: ModuloFourDivisor - naoya_t@topcoder のブックマークコメント

昨日の900点問題を解いてみた。

Nの約数を列挙するためには素因数分解すればいいんですが…

最初、オイラーのφ関数がどうのとかあれこれ考えていたのですが、ここではmod 4だけが問題になっているので、4で割った余りがそれぞれ0,1,2,3な素数（※0は無いですね。2は2だけ）は同一視して

N = 2^S x (4k+1)^T x (4k+3)^U

が見えたら解けたも同然...

a,c

4で割って余りが0になるのはS≧2な全パターンなので

S=0,S=1:

　a = 0

S≧2:

　a = [2..S]x[0..T]x[0..U] = (S-1)(T+1)(U+1) > 0

同様に、余りが2になるのはS=1な全パターンなので

S=0:

　c = 0

S>=1:

　c = [1]x[0..T]x[0..U] = (T+1)(U+1) ≧1

c≠0のとき、aはcで割り切れなければならない。∵a=(S-1)c

あと

  • a≠0のとき（Nは4の倍数）には必ずc≠0（2の倍数）
  • c=0（Nは2の倍数でない）のときには必ずa=0（当然4の倍数でもない）

b,d

余りが1(または3)になるのはS=0の場合。Uが偶数なら1,奇数なら3になる。Tはいくつでも関係ない。よって

b = [0]x[0..T]x[0,2,4,...n<=U] = (T+1)[(U+2)/2] ≧1

d = [0]x[0..T]x[1,3,5,...m<=U] = (T+1)[(U+1)/2] ≧0

  • U=0のときd=0
  • Uが奇数のときb=d
  • Uが偶数のときb=d+(T+1)

という関係が成り立つ。b≠dのとき [(U+2)/2]=[(U+1)/2]+1 のため (T+1) はbとdの最大公約数に等しいことも使える。

  • あと、c>0のときc=b+d

以上の条件をクリアするものをA,B,C,Dの全組み合わせ（高々50^4通り）の中から数え上げればよい。

Mediumより簡単じゃないか...

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

ll gcd(ll m, ll n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (m > n) m %= n; else n %= m;
  }
}

class ModuloFourDivisor {
  bool possible(ll a,ll b,ll c,ll d){
    if (b==0) return false;
    if (a>0 && c==0) return false;
    if (c==0 && a>0) return false;
    if (c>0) {
      if (a % c) return false;
      if (b+d != c) return false;
    }
    if (d==0 || b==d) return true;
    if (b == d+gcd(b,d)) return true; // ※※
    return false;
  }

 public:
  int countQuadruplets(vector<long long> A, vector<long long> B, vector<long long> C, vector<long long> D) {
    int cnt=0;
    tr(A,at) tr(B,bt) tr(C,ct) tr(D,dt)
      if (possible(*at,*bt,*ct,*dt)) cnt++;
    return cnt;
  }
};

最初、※※のチェックをc>0のときにしかしていなくてfailed system test → そこを直したら通った

SRM458

SRM | 02:57 | SRM458 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM458 - naoya_t@topcoder SRM458 - naoya_t@topcoder のブックマークコメント

01.14.2009+

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 BouncingBalls 15'45'' - passed system test - 196.42pt
1 450 NewCoins 間に合わず - - -
1 900 - 開いてない -

250点問題: BouncingBalls

  • すべてのパターンについて調べても高々2^12通り
  • 跳ね返る回数＝跳ね返らず直進するとした場合に交差する回数
  • 傾きが同じなら除外
  • 交点が(0..t]にあるか
  • 15'45''
  • passed system test
#define sz(a)  int((a).size())
#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++)

class BouncingBalls {
  vector<int> y,v;
  int n,t;
  int test(){
    int cnt = 0LL;
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        if (v[i]==v[j]) continue;
        double at = (double)(y[j] - y[i])/(v[i] - v[j]);
        if (0 < at && at <= t) cnt++;
      }
    }
    return cnt;
  }
 public:
  double expectedBounces(vector<int> x, int T) {
    n=sz(x); t=T;
    y.assign(all(x)); v.resize(n);
    int ps=1<<n, cnt=0;
    rep(p,ps){
      for(int j=0,m=1;j<n;j++,m<<=1) v[j] = (p&m) ? 1 : -1;
      cnt += test();
    }
    return (double)cnt / ps;
  }
};

450点問題: NewCoins

  • Sample Caseが全部通るやつは書けた。まだ30分ちょい残ってる。
  • でも最悪とは言えないまでもひどいケースで試してTLE
  • これがなんとかならないとsubmitできない
  • なんとかならなかった
  • 提出を諦めた（Sample Caseしか通らない）コードを晒しておく：
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#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())

typedef pair<int,int> i_i;

class NewCoins {
  int n,maxprice;
  vector<i_i> av; int avn;
  vector<int> coins;

  map<vector<int>,int> memo;
  map<vector<int>,int> mmc;

  int sub() {
    int cn = sz(coins); 

    if (found(memo,coins)) return memo[coins];
    
    int lastcoin = coins.back(); coins.pop_back();

    int cntnow=0;
    if (found(mmc,coins)) {
      cntnow = mmc[coins];
      coins.pb(lastcoin);
      rep(i,avn){
        if (av[i].first>=lastcoin){
          int k = (av[i].first / lastcoin) * av[i].second;
          int m = lastcoin / coins[cn-2];
          cntnow -= (m-1)*k;
        }
      }
    } else {
      // cn=1
      coins.pb(lastcoin);
      rep(j,avn){
        if (av[j].first % lastcoin) {
          memo[coins]=-1; return -1;
        }
        cntnow += av[j].second * av[j].first/lastcoin;
      }
    }

    mmc[coins] = cntnow;
    cn++;

    for(int b=lastcoin*2;b<=maxprice;b+=lastcoin){
      coins.pb(b);
      int cnt = sub();
      coins.pop_back();
      if (cnt >= 0) cntnow = min(cntnow, cnt);
    }
    memo[coins] = cntnow;
    return cntnow;
  }
 public:
  int minCoins(vector<int> price) {
    memo.clear();
    mmc.clear();
    n=sz(price); maxprice = price[n-1];
    map<int,int> a;
    rep(i,n) { int p=price[i]; if (found(a,p)) a[p]++; else a[p]=1; }
    av.assign(all(a)); avn = sz(av);
    if (avn==1) return av[0].second;

    int minc=INT_MAX;
    coins.clear();
    for(int b=1;b<=price[0];b++){
      coins.pb(b);
      int cnt = sub();
      coins.pop_back();
      if (cnt >= 0) minc = min(minc, cnt);
    }
    return minc;
  }
};

900点問題: 開いてない

Challenge phase

  • 他の人の450を見てみた。Javaが多い。あと、なんか短い。

System Test

o - -

196.42 points

結果

room:9/20位

DIV1:282/680位

1292→1366(+74) 少し持ち直したがまだ青。

http://gyazo.com/676d02329e29cd36fe112a183fee9b69.png

コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100115
naoya_t
→TopCoder Member Profile
→日本人参加者ランキング
→PKU日記はこちら
カレンダー
<< 2010/01 >>
日 月 火 水 木 金 土
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
注目エントリー
自作ライブラリ
最近のコメント
最近のトラックバック
最新日記一覧