CODE THANKS FESTIVAL 2017 H - Union Sets

問題ページ
H - Union Sets

thanksのHを複数の解法で解いてみた話

解法1

公式で解説されていたLCAを使った解法
t回目のクエリではじめて頂点p, qがつながれたとき、頂点p, qを重みtの辺でつないだ森をつくる。これはunionfindを用いて、頂点p, qがすでにつながれていなければ新たに辺でつなぐとすることでできる。

パス(p, q)上で最も大きい辺の重みを高速に求めることを考えるとこれはLCAを使うとできる。
ダブリングを用いたLCAでは parent[k][v] = (頂点vから2^k回親をたどったときの頂点) を構築しLCAを求めるが、同様に (頂点vから2^k回親をたどったときの最大の重み) の情報を前計算しておくことで最大の重みを求めることが出来る。

LCAの実装が怪しい気がするけど通ったのでセーフ

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAX_N 100010

class UnionFind {
private:
  // 親と木の深さ
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
public:
  UnionFind();
  UnionFind(int);
  int find(int x);
  void unite(int, int);
  bool same(int, int);
  int size(int);
  int group(int);
};

//MAX_Nで初期化
UnionFind::UnionFind() {
  for(int i=0; i<MAX_N; ++i) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素数nで初期化
UnionFind::UnionFind(int n) {
  for(int i=0; i<n; i++) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素xの親を求める
int UnionFind::find(int x) {
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void UnionFind::unite(int x, int y) {
  // xとyの親
  x = find(x);
  y = find(y);
  if(x == y) return;

  // yのほうが深さが深い　xの親はyの親
  if(rank[x] < rank[y]) {
    par[x] = y;
    s[y] = s[x] + s[y];
  }
  else {
    par[y] = x;
    s[x] = s[x] + s[y];
    if( rank[x] == rank[y] ) rank[x]++;
  }
}

// xの属する連結成分のサイズ
int UnionFind::size(int x) { return s[find(x)];}

// xとyが同じ集合に属するか
bool UnionFind::same(int x, int y) { return find(x) == find(y);}

// 連結成分数
int UnionFind::group(int n) {
  REP(i, n) used[find(i)] = true;
  int ret = 0;
  REP(i, n) if(used[i]) ret++;
  return ret;
}

UnionFind uf;

#define MAX_LOG_N 50

vector<PII> G[MAX_N];  //グラフの隣接リスト
int root = 0;     //根のノード

PII parent[MAX_LOG_N][MAX_N];
int depth[MAX_N];
bool used[MAX_N];

void dfs(int v, int p, int d, int w) {
  // cout << v << " " << p << " " << d << " " << w << endl;
  used[v] = true;
  // 頂点pと頂点vの辺の重み
  parent[0][v] = {p, w};
  depth[v] = d;
  REP(i, G[v].size()) if(G[v][i].first != p) dfs(G[v][i].first, v, d+1, G[v][i].second);
}

//初期化 O(logn)
void init(int n) {
  REP(i, n) {
    if(!used[i]) {
      // cout << i << endl;
      dfs(i, -1, 0, -1);
    }
  }
  REP(k, MAX_LOG_N-1) REP(v, n) {
    if(parent[k][v].first < 0) parent[k+1][v] = parent[k][v];
    else {
      PII tmp = parent[k][parent[k][v].first];
      parent[k+1][v] = {tmp.first, max(parent[k][v].second, tmp.second)};
    }
  }
}

// uとvのlcaを求める
int lca(int u, int v) {
  if(depth[u] > depth[v]) swap(u, v);
  int ret = 0;
  REP(k, MAX_LOG_N) {
    if((depth[v]-depth[u]) >> k & 1) {
      chmax(ret, parent[k][v].second);
      v = parent[k][v].first;
    }
  }
  if(u == v) return ret;
  for(int k = MAX_LOG_N-1; k>=0; k--) {
    if(parent[k][u] != parent[k][v]) {
      chmax(ret, parent[k][u].second);
      chmax(ret, parent[k][v].second);
      u = parent[k][u].first;
      v = parent[k][v].first;
    }
  }
  return ret;
}

signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    if(!uf.same(a, b)) {
      uf.unite(a, b);
      G[a].PB({b, i+1});
      G[b].PB({a, i+1});
    }
  }

  init(n);
  int q;
  cin >> q;
  REP(i, q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    if(!uf.same(x, y)) cout << -1 << endl;
    else {
      int ret = lca(x, y);
      cout << ret << endl;
    }
  }

  return 0;
}

解法2

並列ニ分探索を使った解法
並列二分探索についてはAGC002-Dの解説放送を見るのがおすすめです。
まず、クエリが1個のとき二分探索で答えを求めることを考える。「X回目まで頂点の併合をしたとき、クエリで指定された頂点が連結であるかどうか」という質問を考えると1回連結になればそれ以降はずっと連結なので単調性があり二分探索ができる。頂点の併合はO(Mα(N))でできるのでクエリ1つに対してはO(Mα(N)logM)でできる。
クエリはQ個あるためQ個バラバラに上記の二分探索を行うと当然TLEする。そこでQ個並列に二分探索をすることで2sec以内に計算することができる。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
      par[x] = y; s[y] = s[x] + s[y];
    } else {
      par[y] = x; s[x] = s[x] + s[y];
      if( rank[x] == rank[y] ) rank[x]++;
    }
  }
  int size(int x) { return s[find(x)];}
  bool same(int x, int y) { return find(x) == find(y);}
  int group(int n) {
    REP(i, n) used[find(i)] = true;
    int ret = 0;
    REP(i, n) if(used[i]) ret++;
    return ret;
  }
};
UnionFind uf;

struct query_{
  int piv,z,x,y;
  int lb,ub;
  int idx;
  bool operator<(const query_& a){ return piv<a.piv; }
};
query_ query[100010];

int a[100010], b[100010];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }
  int q;
  cin >> q;
  REP(i, q) {
    cin >> query[i].x >> query[i].y;
    query[i].x--, query[i].y--;
    query[i].lb = -1;
    query[i].ub = m;
    query[i].piv = (m-1)/2;
    query[i].idx = i;
  }

  sort(query, query+q);
  REP(_, 20) {
    uf.init(n);
    int idx = 0;
    REP(i, m) {
      // i番目について処理
      uf.unite(a[i], b[i]);
      while(idx < q && query[idx].piv==i) {
        if(query[idx].ub-query[idx].lb <= 1) {
          query[idx].piv = query[idx].ub;
          idx++;
          continue;
        }
        // query[idx].pivで二分探索の条件判定
        if(uf.same(query[idx].x, query[idx].y)) query[idx].ub = i;
        else query[idx].lb = i;
        query[idx].piv = max(0LL, (query[idx].lb + query[idx].ub)/2);
        idx++;
      }
    }
    sort(query, query+q);
  }

  VI res(q);
  REP(i, q) {
    if(uf.same(query[i].x, query[i].y)) res[query[i].idx] = query[i].ub;
    else res[query[i].idx] = -2;
  }
  REP(i, q) cout << res[i]+1 << endl;

  return 0;
}

解法3

部分永続unionfindを使う
やぶについて書きます を参考に部分永続unionfindを実装する。
find(x, t):t回目のクエリ以前で頂点xの親を求める O(logN)
unite(x, y):頂点x,yを併合 O(logN)

部分永続unionfindを構築しておくと、解法2と違い二分探索で辺を張る必要がないためクエリ1つあたりO(log(N+M))で解くことができ、全体でO(Qlog(M+N))で解ける。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// find:O(logN) unite:O(logN)
class persistentUF {
public:
  const static int MAX_N = 100010;
  unordered_map<int, int> par[MAX_N];
  int rank[MAX_N];
  int fin[MAX_N];
  int idx;

  persistentUF() { init(); }
  void init() {
    idx = 0;
    REP(i, MAX_N) par[i][0] = i, rank[i] = 1, fin[i] = 0;
  }
  persistentUF(int n) { init(n); }
  void init(int n) {
    idx = 0;
    REP(i, n) par[i][0] = i, rank[i] = 1, fin[i] = 0;
  }

  int find(int x, int t) {
    if(t >= fin[x] && par[x][fin[x]] != x) return find(par[x][fin[x]], t);
    return x;
  }

  void unite(int x, int y) {
    x = find(x, idx);
    y = find(y, idx);
    idx++;
    if(x == y) return;
    if(rank[x] < rank[y]) par[x][idx] = y, fin[x] = idx;
    else {
      par[y][idx] = x, fin[y] = idx;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

  bool same(int x, int y, int t) { return find(x, t) == find(y, t); }
};
persistentUF uf;

signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    uf.unite(a, b);
  }

  int q;
  cin >> q;
  REP(i, q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    if(uf.find(x, m) != uf.find(y, m)) {
      cout << -1 << endl;
      continue;
    }
    int lb = -1, ub = m;
    while(ub-lb > 1) {
      int mid = (ub+lb)/2;
      if(uf.find(x, mid) == uf.find(y, mid)) ub = mid;
      else lb = mid;
    }
    cout << ub << endl;
  }

  return 0;
}

あとデータ構造をマージする一般的なテクで解けるらしいが理解できなかったのでできたら書く。

CODE THANKS FESTIVAL 2017 F - Limited Xor Subset

問題ページ
F - Limited Xor Subset

考えたこと

• 数列の順番はどうでもいいのでsortできるし何なら個数だけ持ってもよさそう
• sumの制約の使い方がわからなくて永遠と実験していた
• 実験すると規則を見つけた気になったけど試してたケースが偏ってただけだった
  ------解説を見て------
  sumの制約からわかること
  No.1 大きい数は高々n個しかない
  No.2 種類数はそんなにない
  No.3 O(sum)ができるので

REP(i, n) REP(j, a[i]) {
  // 処理
}

みたいなのはできる

解法1は3番を使っている
→ここまでに出てきた数のorまでを処理すればok(XORでそれ以上の数を作るのは不可能)
→計算量が
a_0 + a_0 | a_1 + … になってこれはソートされている条件で
= 2×a_0 + 2×a_1 + …
= 2×sum
= O(sum)
になって間に合う

解法2は2番を使ってる
→数列の種類数はsqrt(n)
→数字Xがcnt個あるとき、0とXが作られるパターンがそれぞれ2^(cnt-1)個
→数列の各数字についてO(sum)で処理すれば合計O(sqrt(n)sum(a))で解ける

\sum{i=0} C(cnt, i*2) = 2^{m-1}
\sum{i=0} C(cnt, i*2+1) = 2^{m-1}

N = 1 + 2 + 3 + … + M
N = M*(M+1)/2
よってM = O(sqrt(N))

あとTLで見た解法で1番を使っているのがあった
上の方のbitはそんなに表れないことを使って上の方は全列挙で下の方はDPみたいな切り替えをするらしい

• 数式を書いて自明な変形をするとはいみたいなパターンをいい加減解けるようになりたい

解法1

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template<unsigned MOD>
class ModInt {
public:
  unsigned x;
  ModInt(): x(0) { }
  ModInt(signed y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}
  unsigned get() const { return x; }

  // 逆数
  ModInt inv() const {
    ll a = 1, p = x, e = MOD-2;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }
  // e乗
  ModInt 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--;}
    }
    a %= MOD;
    return ModInt(a);
  }
  // 2のx乗
  ModInt pow2() {
    ll a = 1, p = 2, e = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }

  // Comparators
  bool operator <(ModInt b) { return x < b.x; }
  bool operator >(ModInt b) { return x > b.x; }
  bool operator<=(ModInt b) { return x <= b.x; }
  bool operator>=(ModInt b) { return x >= b.x; }
  bool operator!=(ModInt b) { return x != b.x; }
  bool operator==(ModInt b) { return x == b.x; }

  // increment, decrement
  ModInt operator++() { x++; return *this; }
  ModInt operator++(int) {ModInt a = *this; x++; return a;}
  ModInt operator--() { x--; return *this; }
  ModInt operator--(int) {ModInt a = *this; x--; return a;}

  // Basic Operations
  ModInt &operator+=(ModInt that) {
    x = ((ll)x+that.x)%MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    x = ((((ll)x-that.x)%MOD)+MOD)%MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  // O(log(mod))かかるので注意
  ModInt &operator/=(ModInt that) {
    x = (ll)x * that.inv() % MOD;
    return *this;
  }
  ModInt &operator%=(ModInt that) {
    x = (ll)x % that.x;
    return *this;
  }
  ModInt operator+(ModInt that)const{return ModInt(*this) += that;}
  ModInt operator-(ModInt that)const{return ModInt(*this) -= that;}
  ModInt operator*(ModInt that)const{return ModInt(*this) *= that;}
  ModInt operator/(ModInt that)const{return ModInt(*this) /= that;}
  ModInt operator%(ModInt that)const{return ModInt(*this) %= that;}
};
typedef ModInt<1000000007> mint;
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

int a[100010];
mint dp[2][200010];
signed main(void)
{
  int n, k;
  cin >> n >> k;
  REP(i, n) cin >> a[i];
  sort(a, a+n);

  int cur = 1, pre = 0, lim = 0;
  dp[pre][0] = 1;
  REP(i, n) {
    REP(j, lim+1) {
      dp[cur][j] += dp[pre][j];
      dp[cur][j^a[i]] += dp[pre][j];
    }
    lim |= a[i];
    REP(j, lim+1) dp[pre][j] = 0;
    swap(cur, pre);
  }

  cout << dp[pre][k] << endl;

  return 0;
}

解法2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
const int MOD = 1000000007;

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], dp[2][200010];
unordered_map<int, int> mp;

//二分累乗法 xのe乗
ll binpow(ll x, 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 a % MOD;
}

signed main(void)
{
  int n, k;
  cin >> n >> k;
  int s = 0;
  REP(i, n) cin >> a[i], mp[a[i]]++, s+=a[i];

  int cur = 1, pre = 0;
  dp[pre][0] = 1;
  for(auto i: mp) {
    REP(j, 2*s) {
      if(dp[pre][j] == 0) continue;
      (dp[cur][j] += binpow(2, i.second-1) * dp[pre][j] % MOD) %= MOD;
      (dp[cur][j^i.first] += binpow(2, i.second-1) * dp[pre][j] % MOD) %= MOD;
    }
    REP(j, 2*s) dp[pre][j] = 0;
    swap(cur, pre);
  }

  cout << dp[pre][k] << endl;

  return 0;
}

構文解析 問題リスト

自分用
難易度ばらばらに並んでるので注意

• unordered operators　AOJ2613 Unordered Operators - ferinの競プロ帳
• Equation　AOJ2401 Equation - ferinの競プロ帳
• Bug Hunt
• Infallibly Crack Perplexing Cryptarithm
• Shipura
• operation with Finite set
• みさわさんの根付き木
• 6/2(1+2)　AOJ 2255 6/2(1+2) - ferinの競プロ帳
• ICPC計算機
• ascii expression
• Chemist's Math
• Matrix Calculator
• 階層民主主義
• 如何に汝を満足せしめむ？ いざ数え上げむ…
• 壊れた暗号生成器　AOJ 2584 Broken Cipher Generator - ferinの競プロ帳
• Points and Lines　AOJ2596 Points and Lines - ferinの競プロ帳
• AI
• Shifting a Matrix | Aizu Online Judge

参考サイト
構文解析 Howto · GitHub
構文解析 - アルゴリズム講習会
Spaghetti Source - 再帰下降型構文解析 ( LL(1) )

Codeforces Round #446 (Div. 2) C. Pride

問題ページ
Problem - C - Codeforces

概要

長さnの数列aが与えられる。以下の操作を繰り返して数列のすべての要素を1にする最小の操作回数を求めろ。
操作: 数列aから隣接した2要素x,yを選び、その一方をgcd(x, y)と置き換える。

解法

まず、数列中に1が1つでも存在すれば gcd(1,x)=1 よりすべての要素を1に置き換えることが可能でn-(1の個数)が答えになる。
操作を繰り返して1つでも1をつくることができれば同様に数列中のすべての要素を1にすることができ、答えは(1をつくるまでにかかった回数)+n-1となる。逆に1をつくることが不可能であれば数列中のすべての要素を1にすることは不可能で-1を出力する。
したがって、1をつくるのにかかる最短の操作回数を求めたい。
i番目の要素から左・右に操作を続け、gcdが1になったタイミングで最短の操作回数の更新を行うことで可能でこれはO(N²)でできる。

スパーステーブルやセグ木で区間gcdを求められるようにしておくと尺取っぽくできてO(NlogN)で解けそう。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[2010];

ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b) {
  return a/gcd(a, b)*b;
}

signed main(void)
{
  int n;
  cin >> n;
  int one = 0;
  REP(i, n) {
    cin >> a[i];
    if(a[i] == 1) one++;
  }

  if(n == 1) {
    if(a[0] == 1) cout << 0 << endl;
    else cout << -1 << endl;
    return 0;
  }

  if(one) {
    cout << n-one << endl;
    return 0;
  }

  bool flag = false;
  int ret = INF;
  REP(i, n) {
    int tmp = a[i];
    FOR(j, i, n-1) {
      tmp = __gcd(tmp, a[j+1]);
      if(tmp == 1) chmin(ret, j-i+1);
    }
    tmp = a[i];
    for(int j=i; j>0; --j) {
      tmp = __gcd(tmp, a[j-1]);
      if(tmp == 1) chmin(ret, i-j+1);
    }
    // cout << i << " " << ret << endl;
  }
  if(ret == INF) cout << -1 << endl;
  else cout << n+ret-1 << endl;

  return 0;
}

Codeforces Round #439 (Div. 2) C. The Intriguing Obsession

問題ページ
Problem - C - Codeforces

概要

赤い島がa個、青い島がb個、紫の島がc個ある。これらの島に橋をかける。橋の長さを1としたとき、同じ色の島で最短距離が3未満になるような島のペアが存在しないようにしたい。このとき、橋をかける方法が何通りあるのかをmod 998244353で求めろ。

考えたこと

1. 赤-青、青-紫、紫-赤の繋ぎ方が何通りなのかをそれぞれ考えてみる
2. 島の数が1-1のときは2通り、1-2のときは3通り、2-2のときは7通りになっている
3. これは組み合わせを頑張れば求められそうな気持ちになったので、求まったとして全体が何通りになるかを考える
4. 最短距離が3以上の制約より赤-青の繋ぎ方が青-紫、紫-赤の繋ぎ方に影響を与えることはなさそう
5. 独立に考えられそうなので(赤-青の通り数)×(青-紫の通り数)×(紫-赤の通り数)で全体が求まりそう
6. それぞれの通り数を求める方法について考える
7. dp[i][j] = (島の数がi, jの対になっているときの通り数)とする
8. 青い島が2個、紫の島が3のときどうなってるか考えてみる
   
   青1と紫1をつないだとき→dp[1][2]通り
   青1と紫2をつないだとき→dp[1][2]通り
   青1と紫3をつないだとき→dp[1][2]通り
   青2と紫1をつないだとき→1通り(重複して数えないように青1と紫をつなぐ繋ぎ方は数えない)
   青2と紫2をつないだとき→1通り
   青2と紫3をつないだとき→1通り
   何も繋がないとき→1通り
   したがって(dp[1][2] + 1) * 3 + 1通りになる
9. これを一般化するとdp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1] + … + dp[1][j-1] + 1) * j + 1通りになる
10. 素直にDPするとO(max(a, b, c)^3)だが累積和の部分を別に計算しておくとO(max(a, b, c)^2)で間に合う

modint構造体を使うと便利だけど定数倍が重いのでちょっとこわい

公式解説の方法

島の数がA-Bで橋の数がkのとき、C(A,k) * C(B, k) * k! で繋ぎ方が何通りあるか求まる。
よって島の数がA-Bのときはsum( k=0 to min(A, B), C(A,k) * C(B, k) * k!) で求められる。
これはO(max(a, b, c)^2)で計算できる。

どう考えてもこっちのほうが頭がいい。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template<unsigned MOD>
class ModInt {
public:
  unsigned x;
  ModInt(): x(0) { }
  ModInt(signed y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}
  unsigned get() const { return x; }

  // 逆数
  ModInt inv() const {
    ll a = 1, p = x, e = MOD-2;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }
  // e乗
  ModInt 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--;}
    }
    a %= MOD;
    return ModInt(a);
  }
  // 2のx乗
  ModInt pow2() {
    ll a = 1, p = 2, e = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }

  // Comparators
  bool operator <(ModInt b) { return x < b.x; }
  bool operator >(ModInt b) { return x > b.x; }
  bool operator<=(ModInt b) { return x <= b.x; }
  bool operator>=(ModInt b) { return x >= b.x; }
  bool operator!=(ModInt b) { return x != b.x; }
  bool operator==(ModInt b) { return x == b.x; }

  // increment, decrement
  ModInt operator++() { x++; return *this; }
  ModInt operator++(int) {ModInt a = *this; x++; return a;}
  ModInt operator--() { x--; return *this; }
  ModInt operator--(int) {ModInt a = *this; x--; return a;}

  // Basic Operations
  ModInt &operator+=(ModInt that) {
    x = ((ll)x+that.x)%MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    x = ((((ll)x-that.x)%MOD)+MOD)%MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  // O(log(mod))かかるので注意
  ModInt &operator/=(ModInt that) {
    x = (ll)x * that.inv() % MOD;
    return *this;
  }
  ModInt &operator%=(ModInt that) {
    x = (ll)x % that.x;
    return *this;
  }
  ModInt operator+(ModInt that)const{return ModInt(*this) += that;}
  ModInt operator-(ModInt that)const{return ModInt(*this) -= that;}
  ModInt operator*(ModInt that)const{return ModInt(*this) *= that;}
  ModInt operator/(ModInt that)const{return ModInt(*this) /= that;}
  ModInt operator%(ModInt that)const{return ModInt(*this) %= that;}
};
typedef ModInt<998244353> mint;
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

mint dp[5010][5010], dp2[5010][5010];
signed main(void)
{
  FOR(i, 1, 5001) {
    FOR(j, 1, 5001) {
      if(i == 1 || j == 1) dp[i][j] = max(i, j)+1;
      else dp[i][j] = (dp2[i-1][j-1]+1)*j + 1;
      dp2[i][j] = dp2[i-1][j] + dp[i][j];
    }
  }

  int a, b, c;
  cin >> a >> b >> c;
  cout << dp[a][b] * dp[b][c] * dp[a][c] << endl;

  return 0;
}

Codeforces Round #440 Div. 2 C. Maximum splitting

問題ページ
Problem - C - Codeforces

概要

q個(1<=q<=10^5)個のクエリが与えられる。各クエリでは整数n(1<=n<=10^9)が与えられる。整数nを合成数の和として表したとき、最大の合成数の個数を各クエリで答えろ。

考えたこと

1. できるだけ小さい合成数をつかったほうがよさそう
2. 合成数は小さい方から4,6,9,10,12…となっている
3. nが小さいときについて実験してみる

n
1  -1
2  -1
3  -1
4  1 (4)
5  -1
6  1 (6)
7  -1
8  2 (4+4)
9  1 (9)
10 2 (4+6)
11 -1
12 3 (4+4+4)
13 2 (4+9)
14 3 (4+4+6)
15 2 (5+9)
16 4 (4+4+4+4)

1. 4と6を使えば4以上の偶数はすべて表現できる
2. 同様に4と6と9を使えば13以上のすべての数が表現できる
3. したがって答えが-1になるのはn=1,2,3,5,7,11のみ
4. 偶数であればfloor(n[i]/4)が答えになり、奇数であればfloor((n[i]-9)/4)+1が答えになる

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int n[100010];
signed main(void)
{
  int q;
  cin >> q;
  REP(i, q) cin >> n[i];

  REP(i, q) {
    if(n[i] == 1 || n[i] == 2 || n[i] == 3 || n[i] == 5 || n[i] == 7 || n[i] == 11) {
      cout << -1 << endl;
    } else if(n[i]%2) {
      cout << (n[i]-9)/4 + 1 << endl;
    } else {
      cout << n[i]/4 << endl;
    }
  }

  return 0;
}

CODE FESTIVAL 2017 Final D - Zabuton

問題ページ
D - Zabuton

学び

最適な並べ方について考える発想がなかった(求められると思わなかった)
2要素を並べてどちらを前にするべきかを数式で書くとh+pが出て来る
最適な並べ方について考えてそれを満たすような数列を考える hを状態に持つDPしか思い浮かばなかった DPの取り方を頭に入れておく

解法

h+pで昇順にソートした後DPをする
dp[i人目][j人選んだ] = (最小の高さ)として
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + v[i][2]) と遷移する

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[5010][5010];
signed main(void)
{
  int n;
  cin >> n;
  VVI v;
  REP(i, n) {
    int h, p;
    cin >> h >> p;
    v.PB({h+p, h, p});
  }
  sort(ALL(v));

  REP(i, n) REP(j, n+1) dp[i][j] = INF;
  dp[0][0] = 0;
  dp[0][1] = v[0][2];
  FOR(i, 1, n) {
    dp[i][0] = 0;
    FOR(j, 1, n+1) {
      if(dp[i-1][j-1] <= v[i][1]) dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + v[i][2]);
      else dp[i][j] = dp[i-1][j];
    }
  }

  int ret = 0;
  REP(i, n+1) if(dp[n-1][i] < INF) ret = i;
  cout << ret << endl;

  return 0;
}