naoya_t@topcoder

SRM485

22:03 |

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

総括

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

• 道筋は割とすぐに立った。
  • 最初の２つの数字 (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