Google Code Jam Round 1B 2019 を通過した

C-large以外は解けて72点。308位で通過。1Aのときと違って破滅しなくてよかった。

A (Manhattan Crepe Cart)

• 問題を読むのに時間がかかる
• 東西と南北に分けてimosするだけ
• 16:57 AC

void solve() {
  int p, q; cin >> p >> q;
  vector<int> x1(q+1);
  vector<int> x2(q+1);
  vector<int> y1(q+1);
  vector<int> y2(q+1);

  rep(i, p) {
    int x, y; cin >> x >> y;
    char c; cin >> c;
    if (c == 'E') {
      x1[x+1]++;
    } else if (c == 'W') {
      x2[x-1]++;
    } else if (c == 'N') {
      y1[y+1]++;
    } else {
      y2[y-1]++;
    }
  }

  for(int i=0; i<q; i++) {
    x1[i+1] += x1[i];
    y1[i+1] += y1[i];
  }
  for(int i=q-1; i>=0; i--) {
    x2[i] += x2[i+1];
    y2[i] += y2[i+1];
  }

  int ma = -1;
  int ansx = -1;
  for(int i=0; i<=q; i++) {
    auto now = x1[i]+x2[i];
    if (now > ma) {
      ma = now;
      ansx = i;
    }
  }
  ma = -1;
  int ansy = -1;
  for(int i=0; i<=q; i++) {
    auto now = y1[i]+y2[i];
    if (now > ma) {
      ma = now;
      ansy = i;
    }
  }
  cout << ansx << ' ' << ansy << endl;
}

B (Draupnir)

• 2回のクエリで1~3と4~6がそれぞれ求まりそうだなと思った
• とりあえず出してみたらRE(実質WA)したので自分で {100, 100, 100, 100, 100, 100} のテストを書いてみたら、{100, 100, 107, 100, 100, 100} が返ってきて混乱
• しばらくすると、3を求めるときに4の情報が入り込んでいることがわかった
• またテストしたら {100, 100, 101, 100, 100, 100}
• 5の情報も入り込んでいた (気づくのに時間がかかった)
• Wの読み込みは初回だけというのが非常にわかりづらいのでやめてほしい (1TLE)
• 57:32 AC (2ペナ)

vector<ll> test = {100, 100, 100, 100, 100, 100};

ll calc(int n) {
  vector<ll> ret = test;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=6; j++) {
      if (i%j == 0) {
        ret[j-1] *= 2;
        ret[j-1] %= mod;
      }
    }
  }
  ll sum = 0;
  rep(i, 6) {
    sum += ret[i];
  }
  return sum;
}

void solve() {
  vector<ll> ans(6);
  ll ret;
  cout << 224 << endl;
  cin >> ret;
  //ret = calc(224);  

  ans[3] = ret>>56;
  ans[4] = (ret>>44) & 127;
  ans[5] = (ret>>37) & 127;

  cout << 56 << endl;
  cin >> ret;
  //ret = calc(56);

  ret -= (ans[3]<<14);
  ret -= (ans[4]<<11);

  ans[0] = ret>>56;
  ans[1] = (ret>>28) & 127;
  ans[2] = (ret>>18) & 127;

  rep(i, 5) {
    cout << ans[i] << ' ';
  }
  cout << ans[5] << endl;

  cin >> ret;
  assert(ret==1);
}

C (Fair Fight)

• Large解法を考えるが、全然思いつかず、しばらく悩んでからSmallを通す
• 79:27 Small AC
• 終了20分前くらいにLarge解法を思いついて書き始めたけど遅かった
• Smallはセグ木を貼って全区間探索するだけなので、Largeに悩む前にとりあえず投げれば65分くらいで通せたと思う

Small

// Segment Tree for query max[a, b)
struct {
  int N;
  vector<long long> dat;

  void init(int n) {
    N = 1;
    while(N < n) N *= 2;
    dat.resize(2*N-1, 0);
  }

  // update k-th element
  void update(int k, long long a) {
    k += N-1;
    dat[k] = a;
    while(k > 0) {
      k = (k-1)/2;
      dat[k] = max(dat[k*2+1], dat[k*2+2]);
    }
  }

  // add k-th element by a
  void add(int k, long long a) {
    k += N-1;
    dat[k] += a;
    while(k > 0) {
      k = (k-1)/2;
      dat[k] = max(dat[k*2+1], dat[k*2+2]);
    }
  }

  // return max[a, b)
  long long query(int a, int b) {
    return query(a, b, 0, 0, N);
  }
  long long query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    int m = (l+r)/2;
    return max(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r));
  }
} A, B;

void solve() {
  int n, k; cin >> n >> k;
  if (n>200) {
    return;
  }
  A.init(n);
  B.init(n);
  rep(i, n) {
    int a; cin >> a;
    A.update(i, a);
  }
  rep(i, n) {
    int b; cin >> b;
    B.update(i, b);
  }
  ll ans = 0;
  for(int i=0; i<n; i++) {
    for(int j=i; j<n; j++) {
      auto a = A.query(i,j+1);
      auto b = B.query(i,j+1);
      if (abs(a-b) <= k) {
        ans++;
      }
    }
  }
  cout << ans << endl;
}

Large

• 2分探索まみれで疑心暗鬼になったけど、コンテストが終わってからそのまま実装したら通ったので考察は合ってた系
• の最大値から順番に確認
• 最低1つは区間に含めないといけない候補をok setに入れる
• 1つでも区間に含めてはいけない候補をng setに入れる
• あとは二分探索したりするといい感じになる

ll n;

// get the smallest value (>= pos) of the set
ll get_upper(int pos, set<ll>& st) {
  auto it = st.lower_bound(pos);
  if (it==st.end()) {
    return n;
  } else {
    return *it;
  }
}

// get the largest value (<= pos) of the set
ll get_lower(int pos, set<ll>& st) {
  auto it = st.lower_bound(pos);
  if (it==st.begin()) {
    return -1;
  } else {
    it--;
    return *it;
  }
}

void solve() {
  ll k; cin >> n >> k;

  // P(skill, pos)
  priority_queue<P> queA, queB, queC;

  rep(i, n) {
    int a; cin >> a;
    queA.emplace(a, i);
  }
  rep(i, n) {
    int b; cin >> b;
    queB.emplace(b, i);
    queC.emplace(b, i);
  }

  set<ll> ok, ng;
  ll ans = 0;

  while(!queA.empty()) {
    P p = queA.top(); queA.pop();
    int val = p.first;
    // count the intervals including pos
    int pos = p.second;
    while(queB.size() && queB.top().first > val+k) {
      ng.insert(queB.top().second); queB.pop();
    }
    while(queC.size() && queC.top().first >= val-k) {
      ok.insert(queC.top().second); queC.pop();
    }
    ll upper = get_upper(pos, ng);
    ll lower = get_lower(pos, ng);
    ll upper2 = get_upper(pos, ok);
    ll lower2 = get_lower(pos, ok);

    if (lower < lower2) {
      ans += (lower2-lower) * (upper-pos);
    }
    if (upper2 < upper) {
      ans += (upper-upper2) * (pos-lower);
    }
    // subtract duplication
    if (lower < lower2 && upper2 < upper) {
      ans -= (lower2-lower)*(upper-upper2);
    }
    // used. insert to NG set
    ng.insert(pos);
  }
  cout << ans << endl;
}