Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-10-21

SRM485

22:03 | SRM485 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM485 - naoya_t@topcoder SRM485 - naoya_t@topcoder のブックマークコメント

久しぶり(9/9以来)の参加。Room1, with Petr

http://gyazo.com/38cd4e5ae334c1c8e2173b3b12178d89.png

総括

250: 145.80/passed system test

500: Opened

1000: Unopened

145.80p + 0p

Room: #11/19

DivI: #304/659

Rating: 1577→1582 上げ止まり感

脳内解説

ネタバレになるほど書いてない残念回

Easy(250): AfraidOfEven
  • 道筋は割とすぐに立った。
    • 最初の2つの数字 (a=seq[0]*2^n0, b=seq[1]*2^n1) がとりうる全パターンについて、等差数列の差分(b-a)を後の数列(のとりうるパターン)について適用し、等差数列が成り立つか調べていくだけ
  • あとはコーディング力の問題
    • というかケアレスミス力の問題
      • というか…あああああ
        • 30分かけてしまったorz
  • passed system test
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define all(c)  (c).begin(),(c).end()
typedef long long ll;

#ifndef INT_MAX
#define INT_MAX 2147483647LL
#endif

class AfraidOfEven {
public:
  vector <int> restoreProgression(vector <int> seq) {
    int sn=sz(seq);
    ll a=seq[0], b=seq[1];
    vector<ll> as,bs;
    while(a<=(ll)INT_MAX) { as.pb(a); a<<=1LL; }
    while(b<=(ll)INT_MAX) { bs.pb(b); b<<=1LL; }
    int an=sz(as), bn=sz(bs);
    ll dlt,cur;
    rep(i,an){
      rep(j,bn){ 
        int okc=0;
        dlt=bs[j]-as[i];
        cur=bs[j]; 
        for(int k=2; k<sn; k++){
          ll nxt=cur+dlt;
          ll hr=(ll)seq[k];
          while(hr<=(ll)INT_MAX) {
            if(hr==nxt) { okc++; cur=hr; break;}
            hr<<=1LL;
          }
        }
        if(okc==sn-2) goto out;
      }
    }
 out:
    vector<int> res;
    rep(i,sn){
      res.pb(cur); cur -= dlt;
    }
    reverse(all(res));
    return res;
  }
};

Medium(500): RectangleAvoidingColoring

  • パターン数える
  • もしかして:DP
    • いろいろ考えた
    • (略
    • 残り7分あたりでそこで試合終了
  • Opened

http://gyazo.com/3890f3b43d69e2ab66b5ad23968ba100.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20101021