2018-02-09

みんプロ2017 B - チーム決め

問題

問題概要

{a_i} (1 <= i <= N), {b_i} (1 <= i <= M)が与えられる.
各数列からK個選んで,昇順に並べた時のmax_(1 <= i <= K) (abs(a_i - b_i))を最小化せよ.
1 <= N,M,K <= 10⁵, 1 <= a_i,b_i <= 10⁹

解法

二分探索する. l = -1としないと X = 0とできる時に引っかかるので注意.
各探索では a[i] に対して a[i]-X <= b[j] <= a[i]+X を満たす最小のb[j]を貪欲に選んでいけば良い.
尺取り法を使えば O((N+M)log10⁹)

メモ

二分探索 -> 貪欲で選ぶと嘘っぽい？(嘘じゃない)
-> BITで数えられるやん！ -> MLEするわ...

絶対値の差がX以下のペアを選んで行く時,a[i]に対して条件を満たす最小のb[j]があり,
これ以外のb[j'] (昇順なのでj'>j)を選ぶとより多くのペアが作れると仮定する.
すると
b[j] を他の a[i'] (i'>i) に割り当てる -> 交差するので絶対値の差は大きくなる. a[i]-b[j],a[i']-b[j']の方が良い.
b[j] を割り当てない -> 単にa[i'] (i'>i)の選択肢が減るのでa[i]-b[j]の方が良い.
冷静に考えてみると明らか. 頭固い.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

int a[MAX_N],b[MAX_N];

int main(){
  int N,M,K; cin >> N >> M >> K;
  rep(i,N) scanf("%d",a+i);
  rep(i,M) scanf("%d",b+i);
  sort(a,a+N);
  sort(b,b+M);
  int l = -1, r = 1e9, mid;
  while(abs(r-l)>1){
    mid = (l+r)/2;
    int cnt = 0;
    for(int i=0,j=0;i<N&&j<M;i++){
      int lb = a[i] - mid, ub = a[i] + mid;
      while(j<M&&b[j]<lb) j++;
      if(b[j]<=ub) cnt++,j++;
    }
    if(cnt>=K) r = mid;
    else l = mid;
  }
  cout << r << endl;
  return 0;
}

2018-02-09

SoundHound Inc. Programming Contest 2018 (春) C - 広告

AtCoder 競プロ

問題

問題概要

グリッドが与えられる. '.'には広告を置くことができる.また広告は隣り合わないようにしたい.
置ける最大数を求めよ.
1 <= H,W <= 40

解法

グリッドグラフは二部グラフとみなせる.
すると二部グラフの最大独立集合を求める問題に帰着できる.
二部グラフの最大独立集合 = 頂点数 - 最大マッチングなので,
フローを流して最大マッチングを求めることで答えが求まる.

メモ

グリッドグラフは二部グラフグリッドグラフは二部グラフグリッドグラフは二部グラフグリッドグラフは二部グラフ

二部グラフというのを読んだ後も, 二部グラフの色の数じゃんと思ったがそうではなかった.
ダメなケース
言い換えができれば解ける問題(ググれば)にぶち当たることが多いので,最大独立集合,最小点カバー,最小辺カバー,最大マッチングは押さえておきたい.

まとめ

(最小辺カバー) + (最大マッチング) = |V|
(最小点カバー) + (最大独立集合) = |V|
二部グラフでは (最大マッチング) = (最小点カバー), 最大マッチングはフローでO(V(V+E))
一般最大マッチング O(|V||E|log|V|) 実装例
最大クリーク問題は補グラフに関する最大独立集合問題
一般最小点カバー,最大独立集合はNP-Hard 参考2
次数2以下の場合は2-SATらしい(？)

そのうち思考の整理も兼ねてまとめたい.

参考1
参考2
マッチングまとめ

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 41;

vector<int> graph[44*44];
string s[44];
int dd[2] = {-1,1};

class BipartiteMatching {
  int size;
  vector<vector<int>> g;
  vector<int> match;
  vector<bool> used;
  bool dfs(int v) {
    used[v] = true;
    for (int u: g[v]) {
      int w = match[u];
      if (w < 0 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
public:
  BipartiteMatching(int v) : size(v), g(v), match(v), used(v) {}
  void add_edge(int u, int v) {
    g[u].push_back(v);
    // g[v].push_back(u);
  }
  int maximum_matching(void) {
    int res = 0;
    fill(begin(match), end(match), -1);
    for (int v = 0; v < size; ++v) {
      if (match[v] >= 0) continue;
      fill(begin(used), end(used), 0);
      if (dfs(v)) ++res;
    }
    return res;
  }
};

int main(){
  int r,c; cin >> r >> c;
  rep(i,r) cin >> s[i+1];
  s[0] = string('*',c+1);
  s[r+1] = string('*',c+1);
  rep(i,r) s[i+1] = "*" + s[i+1] + "*";
  map<int,int> node; int cnt = 0;
  REP(i,1,r+1) REP(j,1,c+1) if(s[i][j]=='.') node[i*44+j] = cnt++;
  BipartiteMatching bp(cnt);
  REP(i,1,r+1) REP(j,1,c+1){
    if(s[i][j]=='.'){
      rep(k,2)
        if(s[i][j+dd[k]]=='.') bp.add_edge(node[i*44+j],node[i*44+j+dd[k]]);
      rep(k,2)
        if(s[i+dd[k]][j]=='.') bp.add_edge(node[i*44+j],node[(i+dd[k])*44+j]);
    }
  }

  cout << cnt - bp.maximum_matching() << endl;
  return 0;
}

2018-02-09

SoundHound Inc. Programming Contest 2018 (春) D - 建物

AtCoder 競プロ

問題

問題概要

HxWのグリッド,各グリッドに報酬p[i][j], コストc[i][j]が与えられる.
各グリッドに移動すると初回でp[i][j]が得られ, 毎回c[i][j]かかる. (i,j) -> (i+1,j), (i,j)+1, (i,j-1) への移動が可能であるとして(H,j) (1<=j<=W)に最終的にいる時の最大利益を求めよ.

解法

DPを3回ぐらいする.
完全にはまやんさんの解説通りにやったので,そんなに書くことがない...

ただいくつか自分がわかりにくいところがあったので書いておく.
a[i] := [0,i) で得られる利益 (解説だと1-indexed) について,

a_i = max(l<i)( sum(l<=j<i)(p_j - 2f_j) + f_l )
a(i+1) = max(l<i+1)( sum(l<=j<i+1)(p_j - 2f_j) + f_l ) = max( a_i + p_i - 2f_i (l<iの時), p(i+1) - f_(i+1) (l=iの時))

数式クソ見にくいけどはてなの数式クソだから仕方ないね.(ハマった)
b_iも同様に遷移する.

またdpの遷移も左から来る場合と下からそのまま来る場合を分ければわかる.

メモ

むずくない... DP苦手だ.
最初max_(3変数)で無理ってなったけど結局下準備すれば解決する話だった.
あと,updateでのmaを使うみたいに分解する術を身につけた方が良さそう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 50004;

using vl = vector<ll>;
using vll = vector<vl>;

int W,H;

vl update(const vl& dp,const vl& p,const vl& f){
  vl res(W,0LL),a(W,0LL),b(W,0LL);
  // a[i] := [0,i) で得られる利益
  rep(i,W-1) a[i+1] = max(a[i]+p[i]-2*f[i],p[i]-f[i]);
  // b[i] := (i,W-1] で得られる利益
  RREP(i,W-1,1) b[i-1] = max(b[i]+p[i]-2*f[i],p[i]-f[i]);
  
  ll ma = -LINF;
  rep(i,W){
    ma = max(ma+p[i]-f[i],dp[i]+p[i]-f[i]+max(a[i]-f[i],0LL));
    res[i] = ma + max(b[i]-f[i],0LL);
  }
  // 一緒だけどわかりにくいからmaを使った
  // res[0] = dp[0] + p[0] - f[0] + max(b[0]-f[0],0LL);
  // REP(i,0,W-1){
  //   res[i+1] = max(dp[i+1]+p[i+1]-f[i+1]+max(a[i+1]-f[i+1],0LL),
  //               res[i]+p[i+1]-f[i+1]-max(b[i]-f[i],0LL))
  //               + max(b[i+1]-f[i+1],0LL);
  // }
  return res;
}

int main(){
  scanf("%d%d",&H,&W);
  vll dp(H+1,vl(W)),p(H,vl(W)),f(H,vl(W));
  rep(i,H) rep(j,W) scanf("%lld",&p[i][j]);
  rep(i,H) rep(j,W) scanf("%lld",&f[i][j]);
  REP(j,1,W) dp[0][j] = -LINF;
  dp[0][0] = 0LL;
  rep(i,H){
    auto d1 = move(update(dp[i],p[i],f[i]));
    reverse(ALL(dp[i]));
    reverse(ALL(p[i]));
    reverse(ALL(f[i]));
    auto d2 = move(update(dp[i],p[i],f[i]));
    reverse(ALL(d2));
    rep(j,W) dp[i+1][j] = -LINF;
    rep(j,W) dp[i+1][j] = max(d1[j],d2[j]);
  }
  rep(j,W) cout << dp[H][j] << endl;
  return 0;
}

2018-02-08

ABC 014 D - 閉路

AtCoder 競プロ

問題

問題概要

N辺の木が与えられる.
aとbを繋いだ時にできる閉路の長さを出力せよ,というQ個のクエリに答えよ.

1 <= N,Q <= 10⁵

解法

典型的なLCAの練習問題.
a,b間に閉路を作った時, depth[a] + depth[b] - 2 * depth[lca(a,b)] + 1
の長さとなる.

メモ

abs()つけてなくて10分ぐらい悩んだ.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

class LCA {
  int size, log_size;
  vector<vector<int>> parent;
  vector<int> depth;
  template <typename Edge>
  void dfs(const vector<vector<Edge>> &g, int v, int p, int d) {
    parent[0][v] = p; depth[v] = d;
    for (const Edge &e: g[v]) {
      if (e.to != p) dfs(g, e.to, v, d + 1);
    }
  }
public:
  template <typename Edge>
  LCA(const vector<vector<Edge>> &g, int root) : size(g.size()), log_size(0), depth(size, 0) {
    for (int v = size; v > 0; v /= 2) ++log_size;
    parent.assign(log_size, vector<int>(size, 0));
    dfs(g, root, -1, 0);
    for (int k = 0; k < log_size - 1; ++k) {
      for (int v = 0; v < size; ++v) {
        if (parent[k][v] < 0) parent[k + 1][v] = -1;
        else parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }
  int query(int u, int v) {
    int ui = u, vi = v;
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < log_size; ++k)
      if (((depth[v] - depth[u]) >> k) & 1) v = parent[k][v];
    if (u == v) return abs(depth[vi] - depth[ui]);
    for (int k = log_size - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    // LCA = parent[0][u]
    return depth[vi] + depth[ui] - 2 * depth[parent[0][u]];
  }
};

struct Edge {
  int to;
  Edge(int t) : to(t) {}
};

using Graph = vector<vector<Edge>>;
Graph graph;

void add_edge(Graph &g, int from, int to) {
  g[from].push_back(Edge(to));
  g[to].push_back(Edge(from));
}

int main(){
  int N; cin >> N;
  graph.resize(N);
  rep(i,N-1){
    int a,b; scanf("%d%d",&a,&b);
    a--; b--;
    add_edge(graph,a,b);
  }
  LCA lca(graph,0);
  int Q; cin >> Q;
  rep(i,Q){
    int a,b; scanf("%d%d",&a,&b);
    a--; b--;
    cout << lca.query(a,b) + 1 << endl;
  }
  return 0;
}

2018-02-08

CODE THANKS FESTIVAL 2017 H Union Sets

AtCoder 競プロ

問題

問題概要

N頂点のグラフが与えられる.
M辺が与えられ,順番に張っていく.
2頂点がいつ何番目の辺で連結になったか,というQ個のクエリを出力せよ.
1 <= N,M,Q <= 10⁵

解法

永続union-find treeを張って,クエリごとに二分探索.
完全永続でも部分永続でも良い. コードは完全永続.
O(M logN loglogN+Q(logN)²)？(怪しい)

想定解はダブリングLCA,並列二分探索.

メモ

自分で実装した訳ではないので良くないな..
想定解どちらでも解けるようにしたい.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

class Array {
  public:
  Array() {}

  Array(int n) {
    h = 0;
    for (int i = 1; i < n; i *= 8) h += 3;
  }

  int *mutable_get(int k) {
    auto p = mutable_get(k, root, 0, h);
    root = p.first;
    return &p.second->value;
  }

  int operator[](int k) {
    node *res = immutable_get(k, root, 0, h);
    return res != nullptr ? res->value : -1;
  }

private:
  struct node {
    node *ch[8] = {};
    int value = -1;
  };

  int h;
  node *root = nullptr;

  node *immutable_get(int a, node *x, int l, int d) {
    if (x == nullptr) return x;
    if (d == 0) return x;
    int id = (a - l) >> (d - 3);
    return immutable_get(a, x->ch[id], l + (id << (d - 3)), d - 3);
  }

  pair<node *, node *> mutable_get(int a, node *x, int l, int d) {
    x = x != nullptr ? new node(*x) : new node();
    if (d == 0) return make_pair(x, x);
    int id = (a - l) >> (d - 3);
    auto p = mutable_get(a, x->ch[id], l + (id << (d - 3)), d - 3);
    x->ch[id] = p.first;
    return make_pair(x, p.second);
  }
};

// root: O(logN loglogN)
// merge: O(logN loglogN)
struct UnionFind {
  Array uf;

  UnionFind() : uf(0) {}

  UnionFind(int n) : uf(n) {}

  int root(int x) {
    int nd = uf[x];
    if (nd < 0) return x;
    return root(nd);
  }

  void merge(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;

    int *u = uf.mutable_get(x);
    int *v = uf.mutable_get(y);
    if (-*u < -*v) swap(u, v), swap(x, y);

    *u += *v;
    *v = x;
  }

  int size(int x) {
    return -uf[root(x)];
  }

  bool query(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return true;
    } else {
      return false;
    }
  }
};


int main(){
  int N,M; cin >> N >> M;

  vector<UnionFind> ufs(M+1);
  UnionFind uf(N);

  rep(i,M){
    int a,b; scanf("%d%d",&a,&b);
    a--; b--; uf.merge(a,b);
    ufs[i+1] = uf;
  }
  int Q; cin >> Q;
  rep(i,Q){
    int a,b; scanf("%d%d",&a,&b);
    a--; b--;
    if(!ufs[M].query(a,b)){
      cout << "-1" << endl;
      continue;
    }
    int l = 0, r = M, mid;
    while(abs(l-r)>1){
      mid = (l+r)/2;
      if(ufs[mid].query(a,b)) r = mid;
      else l = mid;
    }
    cout << r << endl;
  }
  return 0;
}

追記 : LCAも書いた.早い.

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;


class LCA {
  // 森のu-v間最大辺を求める
public:
  int size, log_size;
  vector<bool> used;
  vector<vector<int>> parent,cost;
  vector<int> depth;
  template <typename Edge>
  void dfs(const vector<vector<Edge>> &g, int v, int p, int d,int c) {
    used[v] = true; parent[0][v] = p; depth[v] = d; cost[0][v] = c;
    for (const Edge &e: g[v]) {
      if (e.to != p) dfs(g, e.to, v, d + 1, e.cost);
    }
  }
  template <typename Edge>
  LCA(const vector<vector<Edge>> &g) : size(g.size()), log_size(0), depth(size, 0) {
    for (int v = size; v > 0; v /= 2) ++log_size;
    parent.assign(log_size, vector<int>(size, 0));
    cost.assign(log_size, vector<int>(size, 0));
    used.assign(size,false);
    for(int i = 0; i < size; i++) if(!used[i]) dfs(g, i, -1, 0, -1);
    for (int k = 0; k < log_size - 1; ++k) {
      for (int v = 0; v < size; ++v) {
        if (parent[k][v] < 0) parent[k + 1][v] = -1;
        else parent[k + 1][v] = parent[k][parent[k][v]];
        if(parent[k][v]>0) cost[k+1][v] = max(cost[k][v],cost[k][parent[k][v]]);
      }
    }
  }
  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    int res = 0;
    for (int k = 0; k < log_size; ++k)
      if (((depth[v] - depth[u]) >> k) & 1){
        res = max(res,cost[k][v]);
        v = parent[k][v];
      }
    if (u == v) return res;
    for (int k = log_size - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v] && cost[k][u] != cost[k][v]) {
        res = max(res,cost[k][u]);
        res = max(res,cost[k][v]);
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    res = max(res,max(cost[0][u],cost[0][v]));
    return res;
  }
};

struct Edge {
  int to; int cost;
  Edge(int t) : to(t) {}
  Edge(int t,int c) : to(t),cost(c) {}
};

using Graph = vector<vector<Edge>>;

void add_edge(Graph &g,int a,int b,int c){
  g[a].pb(Edge(b,c)); g[b].pb(Edge(a,c));
}


struct UnionFindTree{
  int par[MAX_N],rank[MAX_N],size[MAX_N];
  UnionFindTree(int N){
    fill(rank,rank+N,0);
    fill(size,size+N,1);
    rep(i,N) par[i]=i;
  }
  int find(int x){
    if(par[x]==x) return x;
    else  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;
    }else{
      par[y]=x;
      if(rank[x]==rank[y])  ++rank[x];
    }
    size[x]=size[y]=size[x]+size[y];
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
};

int main(){
  int N,M; cin >> N >> M;
  Graph graph(N);
  UnionFindTree uft(N);

  REP(i,1,M+1){
    int a,b; scanf("%d%d",&a,&b);
    a--; b--;
    if(!uft.same(a,b)) add_edge(graph,a,b,i);
    uft.unite(a,b);
  }
  LCA lca(graph);
  
  int Q; cin >> Q;
  rep(i,Q){
    int a,b; scanf("%d%d",&a,&b);
    a--; b--;
    if(!uft.same(a,b)) cout << "-1" << endl;
    else cout << lca.query(a,b) << endl;
  }
  return 0;
}

2018-02-08

CODE THANKS FESTIVAL 2017 G - Mixture Drug

AtCoder 競プロ

問題

問題概要

N辺M頂点のグラフが与えられる.
頂点集合S⊆VでSに含まれる二頂点を結ぶ辺が存在しないようなSのmax(|S|)を求めよ.
1 <= N <= 40

解法

解説がめっちゃ丁寧.

半分全列挙して4回ぐらいbitDPする.
Vに含まれる二頂点に含まれる辺が存在しないという条件をVが独立であるという.
V = V1 ∪ V2 , V1 ∩ V2 = φ, |V1| = N/2 として,
ok1[v1] := (v1⊆V1は独立であるか)
ok2[v2] := (v2⊆V2は独立であるか)
ok3[v1] := (v1⊆V1と連結でないv2⊆V2全体の集合)
dp[v1] := (独立なv2⊆ok3[v1]の最大|v2|)
ここで,ok3[v1]自体は独立でないことに注意する.

以上をbitDPを用いて出すと,各v1⊆V1について
max(|v1| + dp[v1])が答えとなる.

メモ

これ最小カットでいけるんじゃと思ったけど同じ側にあるとペナルティはうまくいかないみたいだった.
DPの遷移が理解するのに時間かかった.
普通にfor文を回したらS -> S∪a -> S∪a∪b と遷移できることがイメージできてなかった気がする.
dp[S∪a]->dp[S∪a∪b], dp[S∪b]->dp[S∪a∪b] の前に dp[S] -> dp[S∪a] と dp[S] -> dp[S∪b] が来ないとおかしくなるじゃんと思ったけど冷静に見ると絶対にそうなっている.
結構好きな問題なのでそのうちまた解きたい.
追記:
最大独立集合問題 <-> 補グラフに関する最大クリーク

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 41;

vector<int> graph[40];
bool ok1[1<<20],ok2[1<<20];
int ok3[1<<20],dp[1<<20];

int main() {
  int N,M; cin >> N >> M;
  rep(i,M){
    int a,b; cin >> a >> b;
    a--; b--; graph[a].pb(b); graph[b].pb(a);
  }
  int n1 = (N+1)/2; int n2 = N/2;
  fill(ok1,ok1+(1<<n1),true);
  rep(i,n1) for(auto u:graph[i]) if(u<n1) ok1[(1<<i)|(1<<u)] = false;
  rep(i,1<<n1) if(!ok1[i]) rep(j,n1) ok1[i|(1<<j)] = false;
  
  fill(ok2,ok2+(1<<n2),true);
  REP(i,n1,N) for(auto u:graph[i]) if(u>=n1) ok2[(1<<(i-n1))|(1<<(u-n1))] = false;
  rep(i,1<<n2) if(!ok2[i]) rep(j,n2) ok2[i|(1<<j)] = false;

  ok3[0] = (1<<n2) - 1;
  rep(i,n1){
    ok3[1<<i] = (1<<n2) - 1;
    for(auto u:graph[i]) if(u>=n1) ok3[1<<i] ^= (1<<(u-n1));
  }
  rep(i,1<<n1) rep(j,n1) ok3[i|(1<<j)] = ok3[i]&ok3[1<<j];

  rep(i,1<<n2){
    if(ok2[i]){
      int cnt = 0;
      rep(j,n2) if(i&(1<<j)) cnt++;
      dp[i] = cnt;
    }else{
      dp[i] = 0;
    }
  }
  rep(i,1<<n2) rep(j,n2) dp[i|(1<<j)] = max(dp[i|(1<<j)],dp[i]);

  int ans = 0;
  rep(i,1<<n1){
    if(!ok1[i]) continue;
    int cnt = 0;
    rep(j,n1) if(i&(1<<j)) cnt++;
    ans = max(ans,cnt + dp[ok3[i]]);
  }
  cout << ans << endl;
  return 0;
}

2018-02-07

AGC 003 C - BBuBBBlesort!

AtCoder 競プロ

問題

問題概要

数列{a_i} (1 <= i <= N)が与えられる.
1. 連続する2数を入れ替える
2. 連続する3数を反転させる
の2つの操作を行い単調増加数列にする時,1.の最小回数を求めよ.
1 <= N <= 10⁵ , i != j => a[i] != a[j]

解法

2.では奇数番目/偶数番目の数の順番を任意の場所に入れ替えることができる.
また,1.は連続する2数の偶奇を入れ替えることができる.
{a_i}で奇数番目であり,{a_i}をソートした{b_i}で偶数番目の数(1)の個数をXとする.
これは{a_i}で偶数番目かつ{b_i}で奇数番目(2)の数の個数と等しい.
そのような数が存在する時,(1)と(2)が隣り合うように2.の操作で動かし,
1.でその2数を入れ替えるという操作をX回繰り返すと,そのような数をなくすことができる.
あとは2.で偶奇に関してソートすれば単調増加数列にできる.
また,自明に(1),(2)のような数が隣り合うことはないので最低X回は1.が必要なため,
Xが答えとなる.

メモ

偶奇に関してソートできることはわかったが,(*1)が隣り合っていたら無理じゃんとなった.
入れ替える(またはそれを先頭に持ってくる)という発想がなかった.惜しい.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

int a[MAX_N],b[MAX_N];

int main(){
  int N; cin >> N;
  rep(i,N) scanf("%d",a+i);
  copy(a,a+N,b);
  sort(b,b+N);
  int ans = 0;
  rep(i,N){
    int ind = int(lower_bound(b,b+N,a[i])-b);
    if(i%2==0 && ind%2==1) ans++;
  }
  cout << ans << endl;
  return 0;
}

kurarrr's memooo

主に競プロ備忘録

みんプロ2017 B - チーム決め

問題概要

解法

メモ

コード

SoundHound Inc. Programming Contest 2018 (春) C - 広告

問題概要

解法

メモ

まとめ

コード

SoundHound Inc. Programming Contest 2018 (春) D - 建物

問題概要

解法

メモ

コード

ABC 014 D - 閉路

問題概要

解法

メモ

コード

CODE THANKS FESTIVAL 2017 H Union Sets

問題概要

解法

メモ

コード

CODE THANKS FESTIVAL 2017 G - Mixture Drug

問題概要

解法

メモ

コード

AGC 003 C - BBuBBBlesort!

問題概要

解法

メモ

コード