naoya_t@hatenablog

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

SRM537(欠席回)の問題を解いてみた

275-500-925て何その配点...

Div1 Easy(275) KingXNewCurrency

  • 場合分けして考える
    • A,B,Xの相互間のGCDで?
    • 綺麗に整理できない。なんか漏れそう。
  • 範囲も[1..200]とかだし総当たりでよくね?
    • (ちょっと多めに取って)[0,39999]の範囲でpA+qBで表現できる数を調べておく。DP。
    • Yを[1..201]で取って pX+qYで表現できる数を調べ、pA+qBで表現できる数が全部カバーできるか調べる。
    • [1..201]全部で行けたら無限扱いということで-1を返そう。
  • passed system test
    • 144.46 = 34'25''
    • 総当りを途中まで考えて、また場合分け作戦に戻って、諦めて総当りで書いたりとかしてる。時間かかりすぎ。
#include <vector>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)

class KingXNewCurrency {
 public:
  int howMany(int A, int B, int X) {
    vector<bool> ck(40000,false);
    ck[0] = true;
    rep(i,40000){
      if (i>=A && ck[i-A]) ck[i] = true;
      else if (i>=B && ck[i-B]) ck[i] = true;
    }
    set<int> s;
    for (int Y=1;Y<=201;++Y) {
      bool ok = true;
      vector<bool> ck_(40000,false);
      ck_[0] = true;
      rep(i,40000){
        if (i>=X && ck_[i-X]) ck_[i] = true;
        else if (i>=Y && ck_[i-Y]) ck_[i] = true;

        if (!ck[i]) continue;
        if (!ck_[i]) {ok=false;break;}
      }
      if (ok) s.insert(Y);
    }
    int ans = s.size();
    return (ans == 201 ? -1 : ans);
  }
};

Div1 Medium(500) KingXMagicSpells

  • ナイーブなメモ化再帰コード。正しい(いちおう題意は読めてる)けれど終わる気がしない。
class KingXMagicSpells {
  vector<int> dk, rv, sp;
  map<ll,double> mm;
  double sub(int ix, int rday, int xo) {
    // 50, 50, 1e9
    ll k = ((ll)xo << 12LL) | ((ll)ix << 6LL) | (ll)rday;
    if (found(mm,k)) return mm[k];
    double r;
    if (rday == 0) {
      r = (double)(dk[ix] ^ xo);
    } else {
      r = (sub(ix,rday-1,xo^sp[ix]) + sub(rv[ix],rday-1,xo)) / 2;
    }
    return mm[k]=r;
  }
 public:
  double expectedNumber(vector<int> ducks, vector<int> spellOne, vector<int> spellTwo, int K) {
    int N = ducks.size();
    dk.assign(all(ducks));
    sp.assign(all(spellOne));
    rv.resize(N);
    rep(i,N){
      // i -> spellTwo[i]
      rv[ spellTwo[i] ] = i;
    }
    mm.clear();
    return sub(0,K,0);
  }
};
  • K日後にroom0に辿り着く動きを逆再生してみる。
    • それぞれのroomがどういう経路でroom0に辿り着くかを考えてる。
    • 部屋移動かXORかの組み合わせは碁盤の目の移動パターンの数え方みたいな感じ。
  • 最悪ケースで間に合わないし、おそらくMLE
    • Easy問題でかかった時間を考えるとこの辺りで既にGAME OVER
class KingXMagicSpells {
  vector<int> dk, rv, sp;
  int n,k;
  map<ll,ll> mm;
  ll sub(int xo, int hi, int l) {
    // (30000000), 50, 50
    ll k = xo*51*51 + hi*51 + l;
    if (found(mm,k)) return mm[k];

    if (l == 0) return mm[k]=xo;

    ll sm = 0;
    for (int i=0; i<=hi; ++i) {
      sm += sub(xo^sp[i], i, l-1);
    }
    return mm[k]=sm;
  }
 public:
  double expectedNumber(vector<int> ducks, vector<int> spellOne, vector<int> spellTwo, int K) {
    int N = ducks.size();
    rv.resize(N);
    rep(i,N){
      // i -> spellTwo[i]
      rv[ spellTwo[i] ] = i;
    }
    
    vector<int> kt;
    kt.resize(K+1); kt[0] = 0;
    rep(i,K){
      kt[i+1] = rv[ kt[i] ];
    }
    n=N; k=K;

    dk.resize(K+1);
    sp.resize(K+1);
    rep(i,K+1){
      dk[i] = ducks[ kt[i] ];
      sp[i] = spellOne[ kt[i] ];
    }

    ll sm = 0;
    for (int i=0; i<=K; ++i) {
      x = dk[i];
      mm.clear();
      sm += sub(dk[i], i, K-i);
    }
    return (double)sm / (double)(1LL << K);
  }
};
  • SRM当時のTLを見てみた

  • あ、そうかbitばらせるじゃん
    • かなり速いしメモリも喰わない
    • 最後に1ビットずつの期待値を足しあわせていくのが素敵
    • これでpassed system test
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class KingXMagicSpells {
  vector<vector<int> > dk, sp;
  int n,k;
  map<int,ll> mm;
  ll sub_(int b, int xo, int hi, int l) {
    // 50, 1, 50, 50  : 6 1 6 6 = 19
    int k = (b << 13) | (xo << 12) | (hi << 6) | l;
    if (found(mm,k)) return mm[k];

    if (l == 0) return mm[k]=xo;

    ll sm = 0;
    for (int i=0; i<=hi; ++i) {
      sm += sub_(b, xo^sp[b][i], i, l-1);
    }
    return mm[k]=sm;
  }
  double sub(int ix, int b) {
    //mm.clear();
    return (double)sub_(b, dk[b][ix], ix, k-ix) / (double)(1LL << k);
  }
 public:
  double expectedNumber(vector<int> ducks, vector<int> spellOne, vector<int> spellTwo, int K) {
    int N = ducks.size();

    vector<int> rv(N);
    rep(i,N){
      // i -> spellTwo[i]
      rv[ spellTwo[i] ] = i;
    }
    
    vector<int> kt;
    kt.resize(K+1); kt[0] = 0;
    rep(i,K){
      kt[i+1] = rv[ kt[i] ];
    }
    n=N; k=K;

    dk.resize(31);
    sp.resize(31);
    rep(b,31) {
      dk[b].resize(K+1);
      sp[b].resize(K+1);
    }
    rep(i,K+1){
      rep(b,31){
        int m = 1 << b;
        dk[b][i] = (ducks[ kt[i] ] & m) ? 1 : 0;
        sp[b][i] = (spellOne[ kt[i] ] & m) ? 1 : 0;
      }
    }

    double ans = 0;
    rep(b,31){
      rep(i,K+1){
        ans += sub(i,b) * (1LL << b);
      }
    }
    return ans;
  }
};