ferinの競プロ帳

競プロについてのメモ

Educational Codeforces Round 47 E. Intercity Travelling

問題ページ

解法

部分集合全通りを求めるのは無理なので見方を変えてi-1km~ikmの区間を難易度a[j]で通過する確率を求めるとしてみる。n=4で試してみると以下の図のようになる。
f:id:ferin_tech:20181226040224p:plain
図を辺ごとに縦に区切るのではなく、難易度a[i]ごとに横で区切ってみる。すると答えはsum(a[i]*(1/2^(i-1))+(n-1)/2^i)*2^(n-1))=sum(a[i]*(n-i+2)/2^i*2^(n-1))=sum(a[i]*(n-i+2)*2^(n-i-1))となる。この式はO(N)で求めることができるので答えを求めることができた。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define endl '\n'

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 998244353;

struct mint {
  ll x;
  mint(): x(0) { }
  mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
  ll get() const { return x; }
  // e乗
  mint pow(ll e) {
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    return mint(a);
  }
  // Comparators
  bool operator <(mint b) { return x < b.x; }
  bool operator >(mint b) { return x > b.x; }
  bool operator<=(mint b) { return x <= b.x; }
  bool operator>=(mint b) { return x >= b.x; }
  bool operator!=(mint b) { return x != b.x; }
  bool operator==(mint b) { return x == b.x; }
  // increment, decrement
  mint operator++() { x++; return *this; }
  mint operator++(signed) { mint t = *this; x++; return t; }
  mint operator--() { x--; return *this; }
  mint operator--(signed) { mint t = *this; x--; return t; }
  // Basic Operations
  mint &operator+=(mint that) {
    x += that.x;
    if(x >= MOD) x -= MOD;
    return *this;
  }
  mint &operator-=(mint that) {
    x -= that.x;
    if(x < 0) x += MOD;
    return *this;
  }
  mint &operator*=(mint that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  mint &operator/=(mint that) {
    x = (ll)x * that.pow(MOD-2).x % MOD;
    return *this;
  }
  mint &operator%=(mint that) {
    x = (ll)x % that.x;
    return *this;
  }
  mint operator+(mint that) const { return mint(*this) += that; }
  mint operator-(mint that) const { return mint(*this) -= that; }
  mint operator*(mint that) const { return mint(*this) *= that; }
  mint operator/(mint that) const { return mint(*this) /= that; }
  mint operator%(mint that) const { return mint(*this) %= that; }
};
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

signed main(void) 
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n;
  cin >> n;
  vector<mint> a(n);
  REP(i, n) cin >> a[i];

  mint ans = 0;
  FOR(i, 1, n+1) {
    if(i == n) ans += a[i-1] * (n-i+2) * mint(499122177); 
    else ans += a[i-1] * (n-i+2) * mint(2).pow(n-i-1);
  }
  cout << ans << endl;

  return 0;
}

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

Codeforces 競技プログラミング

問題ページ

解法

bitwise xorなのでbitごとに独立に考えられる。したがってbitごとに考えればa,bは0/1の数列に帰着でき、答えの行列も0/1要素しか持たないと考えてよい。1が書かれている行・列には1を奇数個、0が書かれている行・列には1を偶数個置くような行列が存在すればそれが答えになる。
条件を絞ってその条件ならば必ず構成できる or 構成できないことを積み上げていくと全体の条件について証明できるみたいな考え方を使う。まず行と列に1が奇数個存在することを考える。以下の図のように構成すると必ず条件を満たす。
f:id:ferin_tech:20181225230121p:plain
行と列どちらにも1が偶数個存在する場合について考える。以下の図のように構成すればよい。1が0個のパターンには注意が必要だが0の行もしくは列に1を偶数個置くことで構成できる。
f:id:ferin_tech:20181225230146p:plain
最後に行と列でどちらかは1が偶数個、もう片方は奇数個存在する場合について考える。一般性を失わず1の数が行の方が多いと考えることができる。1の行・列のみで構成を作ろうとした場合、1なので奇数個置かなければならない行が存在するが列の制約から1をどこにも置けないという状況になる。0の行、列に1を置いて調整しようとした場合でも偶数個の1しか置けないので残りの奇数個の1の行の分を構成することはできない。
f:id:ferin_tech:20181225230158p:plain
以上のように構成を行うことができる。

実験してある条件で構成できそうな規則を見つけるを繰り返すのがよくあるパターン。xorでbitごとに考える、偶奇性に注目するというのもよく見る。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

vector<vector<ll>> solve(vector<ll> a, vector<ll> b) {
  vector<ll> p, q;
  REP(i, a.size()) if(a[i] == 1) p.push_back(i);
  REP(i, b.size()) if(b[i] == 1) q.push_back(i);

  if(p.size()%2 + q.size()%2 == 1) {
    cout << "NO" << endl;
    exit(0);
  }
  vector<vector<ll>> ret(a.size(), vector<ll>(b.size()));
  if(p.size()%2 + q.size()%2 == 2) {
    REP(i, p.size()) ret[p[i]][q[0]] = 1;
    REP(i, q.size()) ret[p[0]][q[i]] = 1;
  } else {
    if(p.size() == 0) {
      REP(i, q.size()) ret[0][q[i]] = 1;
    } else if(q.size() == 0) {
      REP(i, p.size()) ret[p[i]][0] = 1;
    } else {
      FOR(i, 1, p.size()) ret[p[i]][q[0]] = 1;
      FOR(i, 1, q.size()) ret[p[0]][q[i]] = 1;
    }
  }
  return ret;
}

signed main(void) 
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll h, w;
  cin >> h >> w;
  vector<ll> a(h), b(w);
  REP(i, h) cin >> a[i];
  REP(i, w) cin >> b[i];

  vector<vector<ll>> ans(h, vector<ll>(w));
  REP(i, 30) {
    vector<ll> aa(h), bb(w);
    REP(j, h) aa[j] = !!(a[j]&1<<i);
    REP(j, w) bb[j] = !!(b[j]&1<<i);

    auto ret = solve(aa, bb);

    REP(j, h) REP(k, w) {
      if(ret[j][k]) ans[j][k] |= 1<<i;
    }
  }

  cout << "YES" << endl;
  REP(i, h) {
    REP(j, w) {
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }

  return 0;
}

Xmas Contest 2018 B - Bit Smaller

AtCoder 競技プログラミング

問題ページ

解法

入力が与えられないので条件を満たす数を予め全列挙するプログラムをローカルで実行しておきその答えをtextで提出すればよい。数nをa1,b1,a2,b2,…,ak,bk,cと切れ目を入れたときに条件を満たしているような切り方があれば数nを答えに追加すればよい。この切り方を全て試すような探索をdfsを用いて実装する。dfs(idx, last, turn, a, ans)として引数を持つ。idx→今見ているのが何桁目か、last→最後に切った位置の次の桁(idxで切った場合区間[last,idx]が該当する数)、turn→現在見ている場所が累乗の底か肩のどちらか(trueであれば底)、a→累乗の底、ans→現在までの積の結果をそれぞれ表す。
idx番目で切る場合と切らない場合の2通りに分けて考える。切らない場合は簡単でidxを1桁進める以外引数の値が変わることはないのでdfs(idx+1, last, turn, a, ans)を呼び出せばよい。切る場合は現在見ている場所が累乗の底か肩か(=turn)によって場合分けする。累乗の底であれば a = (区間[last,idx]が表す数) とする。したがってdfs(idx+1,idx+1,false,(区間[last,idx]が表す数),ans)と呼び出せばいい。累乗の指数であればans += a^(区間[last,idx]が表す数)とする。この場合はdfs(idx+1,idx+1,true,0,ans*(区間[last,idx]が表す数))と呼び出せばいい。累乗は二分累乗等で高速に計算できる。
idx=(数nの桁数)となった時点でdfsを終了し、この切り方でnと等しくなったかの判定をする。turnがfalseで累乗の指数を表している場合最後のcを掛けることができないので条件を満たさない。turnがtrueの場合ansに(区間[last,idx)が表す数)を掛けて、nと等しければ条件を満たす数が存在したと判定できる。
注意点として区間[idx,last]がleading-zeroになるような切り方をしてはいけないこととabが大きくなりオーバーフローしてしまうケースを除くためにnより大きい数になった場合探索を打ち切る処理が必要である。自分のパソコンではこのdfsで数分程度だった。

こういうdfsはあまり競プロででないので書くのに慣れていないと大変そう。手元で愚直解を書いたりするときに使えるので書けるようにしておくとたまに役立ちます。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

ll n;
const ll m = 20181224;

// 二分累乗 O(funcの計算量*logE)
template<typename T=ll>
T binpow(T x, ll e, function<T(T,T)> func=[](T a, T b){return a*b;}, T d=1) {
  T ret = d, p = x;
  while(e > 0) {
    if(e%2 == 0) {
      p = func(p, p);
      e /= 2;
      if(p > n) return -1;
    }
    else {
      ret = func(ret, p); 
      e--;
      if(ret > n) return -1;
    }
  }
  return ret;
};

vector<ll> pre;
bool ok;
string s;
ll num[10][10];
void dfs(ll idx, ll last, bool turn, ll a, ll ans) {
  if(idx == s.size()) {
    if(!turn) return;
    // [last,s.size()-1]を掛ける
    ans *= num[last][idx-1];
    if(ans == n) ok = true;
    return;
  }

  // idxで切る
  if(turn) {
    if(num[last][idx] != -1) {
      dfs(idx+1, idx+1, false, num[last][idx], ans);
      if(ok) return;
    }
  } else {
    if(num[last][idx] != -1) { 
      ll bpow = binpow(a, num[last][idx]);
      if(bpow != -1) {
        dfs(idx+1, idx+1, true, 0, (ans==0?bpow : ans * bpow));
        if(ok) return;
      }
    }
  }
  // idxでは切らない
  dfs(idx+1, last, turn, a, ans);
}

signed main(void) 
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  vector<ll> ans;
  FOR(i, 1, m + 1) {
    if(i%10000==0) cerr << i << endl;
    n = i; ok = false;
    s = to_string(i);
    REP(j, s.size()) {
      ll t = 0;
      bool zerol = false, flag = false;
      FOR(k, j, s.size()) {
        if(!flag && s[k]=='0') zerol = true;
        if(s[k] != '0') flag = true;
        t *= 10;
        t += s[k]-'0';
        num[j][k] = t;
        if(zerol) num[j][k] = -1;
      }
    }
    dfs(0, 0, true, 0, 0);
    if(ok) ans.push_back(i);
  }

  REP(i, ans.size()) cout << ans[i] << endl;

  return 0;
}

yukicoder No.776 A Simple RMQ Problem

競技プログラミング yukicoder

問題ページ

解法

この記事(Maximum Subarray Sum in a given Range - GeeksforGeeks)のセグメント木を使って解いた。このセグ木では区間[l,r)の連続した部分列の区間和のmaxを求めることができる。セグ木の各頂点に「区間和」「maximum prefix sum」「maximum prefix sum」「部分列の区間和のmax」の4つの情報を持たせる。これらの情報sum,psum,ssum,maxの4つをもたせた構造体nodeを各頂点として扱う。
このセグ木を使ってmaxクエリに答える。まずr1<l1であればr1=l1、r2<l2であればl2=r2とできるのでr1>=l1,r2>=l2と考える。l2 < r1であれば答えは(区間[l1,l2]のssum) + (区間(l2,r1)のsum) + (区間[r1,r2]のpsum)となる。l2 >= r1であれば答えはmax(区間[l1,r1)のssum+区間[r1,l2]のsum+区間(l2,r2]のpsum、区間[l1,r1)のssum+[r1,l2]のsum、区間[r1,l2]のssum+区間(l2,r2]のpsum、区間[r1,l2]のmax)となる。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

/**
* @brief セグメント木
* @details 遅延評価をしない普通のセグメント木\n
* 点更新区間min d=INF, f=min(a,b), g=b\n
* 点更新区間max d=-INF, f=max(a,b), g=b\n
* 点加算区間和  d=0, f=a+b, g+=b
*/
template <typename T>
class segtree {
public:
  int n;
  vector<T> dat;
  T d;
  function<T(T,T)> f, g;

  segtree(int n_, function<T(T,T)> f_, function<T(T,T)> g_, T d_) 
    : f(f_), g(g_), d(d_) {
    n = 1;
    while(n < n_) n *= 2;
    dat.assign(n*2, d); 
  }
  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return d;
    if(a <= l && r <= b) return dat[k];
    return f(query(a, b, 2*k+1, l, (l+r)/2),
             query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, n);}
  void update(int i, T v) {
    i += n-1;
    dat[i] = g(dat[i], v);
    while(i > 0) {
      i = (i-1)/2;
      dat[i] = f(dat[i*2+1], dat[i*2+2]);
    }
  }
};
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, q;
  cin >> n >> q;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  struct node {
    ll sum, psum, ssum, max;
    node() {}
    node(ll a, ll b, ll c, ll d) : sum(a), psum(b), ssum(c), max(d) {}
  };
  auto f = [](node l, node r) {
    node ret;
    ret.sum = l.sum + r.sum;
    ret.psum = max(l.psum, l.sum + r.psum);
    ret.ssum = max(r.ssum, l.ssum + r.sum);
    ret.max = max({l.max, r.max, l.ssum + r.psum});
    return ret;
  };
  auto g = [](node l, node r) {
    return r;
  };
  segtree<node> seg(n, f, g, node(0, -LLINF, -LLINF, -LLINF));

  REP(i, n) {
    node tmp(a[i], a[i], a[i], a[i]);
    seg.update(i, tmp);
  }
  REP(i, q) {
    string s;
    cin >> s;
    if(s == "max") {
      ll l1, l2, r1, r2;
      cin >> l1 >> l2 >> r1 >> r2;
      l1--, l2--, r1--, r2--;
      if(r1 < l1) r1 = l1;
      if(r2 < l2) l2 = r2;
      if(l2 < r1) {
        cout << seg.query(l1, l2+1).ssum + seg.query(l2+1, r1).sum + seg.query(r1, r2+1).psum << endl;
      } else {
        node left = seg.query(l1, r1),
             mid = seg.query(r1, l2+1),
             right = seg.query(l2+1, r2+1);
        cout << max({left.ssum + mid.sum + right.psum,
                     left.ssum + mid.psum,
                     mid.ssum + right.psum,
                     mid.max}) << endl;
      }
    } else {
      ll idx, val;
      cin >> idx >> val; idx--;
      node tmp(val, val, val, val);
      seg.update(idx, tmp);
    }
  }

  return 0;
}

CADDi 2018 E - Negative Doubling

競技プログラミング AtCoder

問題ページ

解法

最終的な列はマイナスとプラスが ----/++++ のように並ぶはずである。したがってマイナスとプラスの区切り位置を決めると、+の列/-の列についてそれぞれ考えられる。符号が全て同じであれば4倍する操作を繰り返すと考えればよく、符号を無視できるので嬉しそう。
区間[i,n)を全て+にするときに必要な操作回数を考えるとj=i+1,…,n-1について順番に条件を満たすまで4倍する処理を繰り返せばよい。これを全ての区間に対して行うとO(N^2)かかるので高速化する必要がある。
dp1[i][j] = (A[i]にj回4倍する操作を行い区間[i,n)で条件を満たすような最小の操作回数) としてみる。dp1[i]をdp1[i+1]から高速に求めることができれば嬉しそう。この更新はdp1[i][j] = dp1[i+1][k] + j (kはa[i]*4^j <= a[i+1]*4^k を満たす最小のk) としてdpの遷移を書くことができ高速に求められる。ただしこのdpテーブルを普通に持とうとすると大きすぎてMLEやTLEになる。i番目に操作した回数が15回を超えると必ずmax(a[i])の値を超えることが10^9 < 4^15よりわかる。a[i]が10^9以上であれば[i,n)について隣接する要素が4倍以上離れることはありえない。したがってi番目に操作した回数がj回(j>=16)であればi+1番目以降にj-15回4倍することになる。つまりj>=16ではdp1[i][j] = dp1[i][15] + (j-15)*(n-i-1)として求めることができる。これによってdpテーブルがN*16程度で済むようになり時間内に求められる。
同様にマイナスが並ぶところについて考えるとdp2[i][j] = (A[i]にj回4倍する操作を行ったときの区間[0,i]で条件を満たすような最小の操作回数)とおいてDPをすればよい。dpの遷移はdp2[i][j] = dp2[i-1][k] + j (kはa[i-1]*4^k <= a[i]*4^j) とすればよい。
dpで持っていた値が-2倍ではなく4倍する操作の回数であること、最初に-2倍したことを考慮していないことを直す必要があることに注意する。[0,i]をマイナスに、[i,n)をプラスにしたときの必要な操作回数はmin(dp2[i][j]*2+i+1) + min(dp1[i+1][j]*2)となる。このうち最小のものが答えとなる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  // dp1[i][j] = dp1[i+1][k] + j (a[i]*4^j <= a[i+1]*4^k を満たす最小のk)
  auto dp1 = make_v<ll>(n, 16);
  REP(i, 16) dp1[n-1][i] = i;
  for(ll i=n-2; i>=0; --i) {
    ll tmp = 1;
    REP(j, 16) {
      ll k = 0, t = 1;
      while(a[i] * tmp > a[i+1] * t) {
        t *= 4;
        k++;
      }
      if(k <= 15) dp1[i][j] = dp1[i+1][k] + j;
      else dp1[i][j] = dp1[i+1][15] + (k - 15) * (n - i - 1) + j;
      tmp *= 4;
    }
  }

  // REP(i, 16) {
  //   REP(j, n) cerr << dp1[j][i] << " ";
  //   cerr << endl;
  // }

  REP(i, n) a[i] *= -2;
  auto dp2 = make_v<ll>(n, 16);
  REP(i, 16) dp2[0][i] = i;
  FOR(i, 1, n) {
    ll tmp = 1;
    REP(j, 16) {
      ll k = 0, t = 1; 
      while(a[i-1] * t > a[i] * tmp) {
        t *= 4;
        k++;
      }
      if(k <= 15) dp2[i][j] = dp2[i-1][k] + j;
      else dp2[i][j] = dp2[i-1][15] + (k - 15) * i + j;
      tmp *= 4;
    }
  }

  // num1[i] = (区間[i,n)で最小の操作回数)
  vector<ll> num1(n, LLINF);
  // num2[i] = (区間[0,i]で最小の操作回数)
  vector<ll> num2(n, LLINF);
  REP(i, n) {
    REP(j, 16) {
      chmin(num1[i], dp1[i][j]*2);
      chmin(num2[i], dp2[i][j]*2+i+1);
    }
  }
  // cerr << num1 << endl << num2 << endl;

  ll ans = LLINF;
  chmin(ans, num1[0]);
  chmin(ans, num2[n-1]);
  REP(i, n-1) chmin(ans, num2[i] + num1[i+1]);
  cout << ans << endl;

  return 0;
}

コンテスト中はa[i]とa[i+1]との差分から必要になる操作回数の分[i+1,n)に操作すればよいと考えて1 5 4 16みたいなケースで16にまで4倍していて終了した…適当な考察をしない
ある条件で値が容易に定まるのでその部分を配列に持つ必要はないみたいなパターン

Codeforces Round #525 (Div. 2) D. Ehab and another another xor problem

Codeforces 競技プログラミング

問題ページ

解法

xorなのでbitごとに見ていくのが基本的なパターンになる。クエリ回数の上限が62回なので30bit分について2回ずつクエリを飛ばして決めていけばよさそう。大小関係について見ていくので上のbitから順番に決めていくとよさそう。
c=d=0のクエリを飛ばすとa>b, a=b, a<bのどれなのかが分かる。次に最上位bitを建ててc=d=10…0となるクエリを飛ばすことを考える。

  • a=1X…X, b=1X…Xもしくはa=0X…X, b=0X…X c=d=0から変化しない
  • a=1X…X, b=0X…Xのとき a>bからa<bに変化する
  • a=0X…X, b=1X…Xのとき a<bからa>bに変化する

a=1X…X, b=1X…Xもしくはa=0X…X, b=0X…Xのどちらかを判定する方法を考える。c=10…0, d=0となるクエリを飛ばすことを考える。

  • a=1X…X, b=1X…X → a<bとなる
  • a=0X…X, b=0X…X → a>bとなる

このようにクエリを飛ばすことでa,bの最上位bitを決定することができる。これを30bit分繰り返すことで答えを求めることができる。
ただし全bitで「iビット目より下のビットだけでのa,bの大小関係を調べる」「a,bのiビット目が0,1か1,0か等しいのどれかを調べる」「a,bのiビット目が0,0か1,1のどちらかを調べる」と3回のクエリを飛ばしていてはクエリ回数の制限を超えてしまう。iビット目より下のビットだけでのa,bの大小関係をi+1ビット目で飛ばしたクエリから決定することで各ビットについて2回のクエリで済ませる。a,bのi+1ビット目が等しい場合はiビット目より下のビットだけにした場合でも大小関係は変化しない。a,bのi+1ビット目が0,1か1,0のどちらかの場合、クエリを飛ばす回数は1回で済むのでiビット目より下のビットだけでの大小関係を調べるクエリを飛ばしても問題ない。
したがってクエリ回数はc=d=0の1回と30bit分について2回クエリを飛ばすことで61回のクエリで答えを決定することができる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

// #define DEBUG
int ansa = 5, ansb = 5;
int query(int c, int d) {
#ifdef DEBUG
  cout << "? " << c << " " << d << endl;
  int ret;
  if((ansa ^ c) > (ansb ^ d)) ret = 1;
  else if((ansa ^ c) == (ansb ^ d)) ret = 0;
  else if((ansa ^ c) < (ansb ^ d)) ret = -1;
  cout << ret << endl;
  return ret;
#else 
  cout << "? " << c << " " << d << endl;
  int ret;
  cin >> ret;
  return ret;
#endif
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  // a > b 1
  // a = b 0
  // a < b -1

  int maskc = 0, maskd = 0, prev = query(0, 0);
  for(int i=29; i>=0; --i) {
    int r1 = query(maskc | 1<<i, maskd | 1<<i);
    if(prev == r1) {
      int r2 = query(maskc | 1<<i, maskd);
      if(r2 == -1) maskc |= 1<<i, maskd |= 1<<i; 
    } else {
      if(prev == 1 && r1 == -1) maskc |= 1<<i;
      else if(prev == -1 && r1 == 1) maskd |= 1<<i;
      prev = query(maskc, maskd);
    }
  }
  cout << "! " << maskc << " " << maskd << endl;

  return 0;
}

インタラクティブのときはifdefでデバッグと提出用を切り替える関数を作ると手元で確かめるのが楽でおすすめ

AGC006 D - Median Pyramid Hard

AtCoder 競技プログラミング

問題ページ

解法

K番目の値を求めるときは二分探索がよくあるパターンである。二分探索を使うことでK番目の値がX以上か？という判定問題に置き換える。K番目の値がA以上であればA以下の数Bについても判定が真となるので単調性はある。数列をX以上とX未満の2種類に変換できるという性質が優秀でうれしい。
今回の問題ではX以上を1、X未満を0と置いてみる。この0/1列でpyramidの値がどうなるか実験してみる。00/11と並んでいたらその上のマスは必ず0/1になる。01010と並んでいた場合は左端・右端のマス目の数の幅が1マスずつ増えていく。区間[l,r]に交互に並んでいたとすると[l, ceil( (l+r)/2 ) )がl番目、( ceil( (l+r)/2 ), n-1]がr番目の値になる。ただしl,rが0やn-1番目のときの処理には注意が必要。これらの性質を使うとO(n)で判定ができ、全体でO(nlogn)で解ける。
f:id:ferin_tech:20181217174224p:plain

同じ数字が並ぶ箇所ごと(v[i-1]==v[i])に処理をするとして実装した。前に同じ数字が並んで現れた箇所をprevとして持っておく。区間[prev,i-1]で01が交互に現れるので上で述べたような処理を行う。最後が01交互で終わる列のときに処理を忘れないように注意。番兵を使うなりループ後に処理を入れるなりしましょう。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  n = 2*n-1;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  auto check = [&](ll mid) -> bool {
    vector<ll> v(n);
    REP(i, n) v[i] = a[i] >= mid;

    ll prev = 0;
    FOR(i, 1, n) {
      if(v[i] == v[i-1]) {
        if(prev < i-1) {
          ll x = ceil(prev+i-1, 2LL);
          FOR(j, prev, x) v[j] = v[prev];
          FOR(j, x, i) v[j] = v[i-1];
        }
        prev = i;
      }
    }
    if(prev < n-1) {
      ll x = ceil(prev+n-1, 2LL);
      FOR(j, prev, x) v[j] = v[prev];
      FOR(j, x, n) v[j] = v[n-1];
    }
    return v[n/2];
  };

  ll lb = 1, ub = n+1;
  while(ub-lb > 1) {
    ll mid = (lb+ub)/2;
    if(check(mid)) lb = mid;
    else ub = mid;
  }

  cout << lb << endl;

  return 0;
}