kurarrr's memooo

主に競プロ備忘録

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

AGC 003 C - BBuBBBlesort!

AtCoder 競プロ

問題概要

数列{a_i} (1 <= i <= N)が与えられる.
1. 連続する2数を入れ替える
2. 連続する3数を反転させる
の2つの操作を行い単調増加数列にする時,1.の最小回数を求めよ.
1 <= N <= 105 , 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;
}

AtCoder Petrozavodsk Contest 001 D - Forest

AtCoder 競プロ

問題概要

N頂点M辺の森と,各頂点にコストが与えられる.
両端の頂点のコストを払うことで辺を作ることができる.
なお各頂点は1回までしか使えない.
全て連結にするのに必要なコストを答えよ.

解法

連結成分はN-M個あるため,必要な辺はN-M-1,必要な頂点は2(N-M-1)である.
まず, N < 2(N-M-1) だと頂点が足りないのでimpossibleである.
解説にある通り, 各連結成分から少なくとも1個ずつ取り, その他の点を小さい順に取れば良い.
そうすることで選ばれた頂点数が多い順に繋げていくとうまくいく.
コストをインデックス付きでソートして,
その連結成分から取っていなかったら無条件で取り,
そうでないようなコストは小さい順に連結成分の数を引いた (2N-2M-2) - (N-M) = N-M-2 個取った.

メモ

貪欲でやったらダメだった.
ここのコーナーケースに引っかかる.
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 = 100005;

template <typename T>
struct UnionFindTree{
  T 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;
  }
  T find(T x){
    if(par[x]==x) return x;
    else return par[x] = find(par[x]);
  }
  void unite(T x,T 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(T x,T y){
    return find(x)==find(y);
  }
};

Pl a[MAX_N];
bool used[MAX_N];

int main(){
  int N,M; cin >> N >> M;
  UnionFindTree<int> uft(N);
  rep(i,N){
    scanf("%lld",&a[i].first);
    a[i].second = i;
  }
  rep(i,M){
    int x,y; scanf("%d%d",&x,&y);
    uft.unite(x,y);
  }
  if(2*(N-M-1)>N){
    cout << "Impossible" << endl;
    return 0;
  }else if(M==N-1){
    cout << "0" << endl;
    return 0;
  }
  sort(a,a+N);
  set<int> st;
  ll ans = 0LL; int cnt = 0;
  rep(i,N){
    if(st.count(uft.find(a[i].second))){
      if(cnt < N-M-2) ans += a[i].first, cnt++;
    }else{
      st.insert(uft.find(a[i].second));
      ans += a[i].first;
    }
  }
  cout << ans << endl;
  return 0;
}

ARC 067 E - Grouping

AtCoder 競プロ

問題概要

N人をいくつかのグループに分ける. ただし以下の制約を満たす.
グループに含まれる人数iは a <= i <= bである.
i 人が含まれるグループの数を f_i とした時, c <= f_i <= d.
分け方の総数を求めよ.
1 <= N <= 103

解法

sum(a<=e<=b)f_e*e = N を満たす f_e が決まれば (e人のグループがf_e個ずつあるということ),あとはコンビネーションで求まる.
雰囲気がDPっぽいのでDPでやる.
dp[i][j] := (f(a+i+1)までを決めて, 合計 j 人の時の組み合わせ) とすると,
dp[i][j] += dp[i-1][j] (f=0とした時)
dp[i][j] += sum_(c<=f<=d) (N-j+ef)! / (f! * (N-j)! * (e!)f )
(N-j+ef人の中からe人のグループをf個取ってきて残りをN-j人にした(j人選んだ状態にした))
ここで,f個のグループは区別しないことに注意.
割り算はフェルマーの小定理使って1e9+7に関する逆元求めるやつ使う.
一見O(N3)ぽいが, e*f <= j でなければならないのでO(N2 * logN)ですむ.

メモ

配るDPの方が楽そうだったけどなぜかエラー出たしあんまり好きじゃないんだよなあ.

逆元を求めるのが重いので多用しない方が良い.
o ... imod(a) * imod(b)
x ... imod(a*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 = 1003;

vector<ll> fact;

void init(ll N){
  fact.resize(N+1);
  fact[0]=1;
  rep(i,N)  fact[i+1]=((i+1)*fact[i])%lmod;
}

ll ppow(ll a,ll b){
  // aのb乗を求める
  ll res = 1;
  while(b){
    if(b%2) res=(res*a)%lmod;
    a=(a*a)%lmod;
    b>>=1;
  }
  return res;
}

ll imod(ll n){
  // nのmodの逆元を求める
  ll P=lmod;
  return ppow(n,P-2);
}

ll comb_mod(ll n,ll k){
  //nまで埋めた階乗テーブルを渡す
  return (fact[n] * imod(fact[k]) % lmod) * imod(fact[n-k]) % lmod ;
  //nCk % mod を返す
}

int N,a,b,c,d;
ll dp[MAX_N][MAX_N];

int main(){
  cin >> N >> a >> b >> c >> d;
  init(N+2);
  dp[0][0] = 1LL;
  REP(i,1,b-a+2){
    rep(j,N+1){
      dp[i][j] += dp[i-1][j];
      int e = a+i-1;
      for(int f=c; f<=d && e*f<=j;f++){
        dp[i][j] += dp[i-1][j-e*f]*fact[N-j+e*f]%lmod*imod(fact[f]*fact[N-j]%lmod*ppow(fact[e],f)%lmod);
        dp[i][j] %= lmod;
      }
    }
  }
  cout << dp[b-a+1][N] << endl;
  return 0;
}

ARC 066 D - Xor Sum

AtCoder 競プロ

問題概要

自然数Nが与えられる.
0 <= u,v <= N であってa+b <= u, ab <= v を満たす非負整数a,bが存在するようなu,vのペアはいくつあるか.
1 <= N <= 1018

解法

a+b = ( (a & b) << 1 ) + (a ^ b)であることから,a+b >= a ^ b.
また, a&b = ( (a+b) - ( a ^ b ))>>1 から, u, vを決めると a ^ b, a&bが決まる.
(ab, a&b) = (0,0),(1,0),(0,1) に対して((1,1)はありえない),
(a, b) = (0,0), (1,0), (1,1) とすれば, a ^ b, a&bからa,bは1通りに決まる.
すなわちa,bをビットの集合とみた時 a ⊇ b ということに相当する.
よって, a+b <= N, a ^ b <= N, a⊇b を満たす a,b のペアの数を求めれば良い.

a+b = S, ab = X を満たすa,b の数を f(S,X) とすると,
a,b の最下位ビットが(0,0),(1,0),(1,1)の各場合に分けて,
(0,0) -> f(S/2,X/2)
(1,0) -> f((S-1)/2, (X-1)/2)
(1,1) -> f(S/2-1,X/2)
だが結局常に X <= S なので, S = X = n として,
f(n) = f(n/2) + f((n-1)/2) + f(n/2-1)
これをメモ化して求めれば良い.

メモ

解説は上から決めていく桁DPだった.
そのうちそっちでもやりたい.

あと OEISで検索するという知見を得た.

コード

#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 = 1003;

int main(){
  ll N; cin >> N;
  map<ll,ll> mp;
  mp[0] = 1LL; mp[1] = 2LL;
  function<ll(ll)> solve = [&](ll n){
    if(mp.count(n)) return mp[n];
    return mp[n] = (solve(n/2) + solve((n-1)/2) + solve(n/2-1)) % lmod;
  };
  cout << solve(N) << endl;
  return 0;
}

Codeforces #459 Div2 C Monster

Codeforces 競プロ

問題概要

文字列Sが与えられる.
'()', '((()))', '()(())'などの'('と')'が対応している文字列を有効な文字列とする.
')('はダメ. また,'?'はどちらにも変換できる.
l ,r (1<=l < r<=|S|)でS[l..r]が有効な文字列であるような組の数を求めよ.
1 <= |S| <= 5*103

解法

全 1 <= l < r <= |S| について判定する.
'('を+1,')'を-1とする.
')'がその前の'('と'?'の数より多いと決して有効でなくなるため,それをcheck変数でチェックする.
cntに関してはできるだけ閉じる -> '?' を ')' にするように数えていくが,
')' を作りすぎてもいけないので cnt = -1となったら, 1に変換する.
これは ')' と変換した '?' を '(' にすることに相当する.
cnt = 0 となる時, 有効な文字列に変換できる.
全パターンがO(|S|^2),各O(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 LINF=1LL<<60, lmod = 1e9+7;

int main(){
  string s; int N;
  cin >> s; N = s.size();
  int ans = 0;
  rep(i,N-1){
    int check = 0, cnt = 0;
    REP(j,i,N){
      if(s[j]=='(') check++,cnt++;
      else if(s[j]==')') check--,cnt--;
      else check++,cnt--;
      if(check<0) break;
      if(cnt<0) cnt += 2;
      // cout << i << "," << j << " = "<< check << "," << cnt << endl;
      if(cnt==0) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

ARC 090 E - Avoiding Collision

競プロ AtCoder

問題概要

N頂点M辺の距離のある無向グラフが与えられる.
頂点S,TからA,Bが各々頂点T,Sに最短路で向かうとき,AとBがすれ違わないような組み合わせをmod 1e9+7で求めよ.
1 <= N <= 105, 1 <= M <= 2*105, 1 <= d <= 109

解法

問題の流れ : Dijkstra -> DP -> 数え上げ

まずDijkstra法で頂点S,Tから各頂点への最短距離を求める.
次にDPでS,Tから各頂点への最短距離でのパスの本数を求める.
これも単純に距離が短い順に頂点を見て行き,
if(次の頂点へ今の頂点から最短距離で行ける辺がある) dp[次の頂点] += dp[今の頂点]
とすれば良い. DijkstraとDPを合わせて,
Dijkstraの距離の更新がある時に dp[頂点] = 0
最短距離で行ける辺を見つけた時に dp[次の頂点] += dp[今の頂点]
とすると楽.

S,Tから各頂点へのパスの本数と距離を patS, distS, patT, distT とする.
また len = (S-Tの最短距離) = distS[T] = distT[S],
pat = (S-Tのパスの本数) = patS[T] = patT[S] とする.

すれ違っても良い場合の組み合わせは pat2 である.

点u上ですれ違う時, distS[u] = distT[u] = len/2 で,
その組み合わせは (patS[u] * patT[u])2

辺(u, v, c)上ですれ違う時,
distS[u] + c + distT[v] = len ..(1)
distS[u] < len/2 かつ distT[v] < len/2 ..(2) で,
その組み合わせは (patS[u] * patT[v])2
(2)によって最短距離で使う辺でも,すれ違うことになる辺だけ数え上げられることに注意する.

上の二つの組み合わせをpat2から引いて答えとなる.
O(NlogN+M)で十分.

メモ

交わらない二つのパス -> Tを通る閉路と変換して解いたが,その前提が間違っていた.
例えば下のような場合.

S <-(10)->1<-(5)-> T
↕︎(3)　　　↕︎(5)
2 <-( 2)->3

国語力不足.

コード

#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 LINF=1LL<<60, lmod = 1e9+7;
const int MAX_N = 100005;

template<typename T> T inf;
template<> constexpr int inf<int> = 1<<30;
template<> constexpr ll inf<ll> = 1LL<<60;

using Cost = ll;
using Node = int;
struct Edge{
  Cost cost; Node to;
  Edge(Cost cost,Node to)
    :cost(cost),to(to){}
};
using Graph = vector<vector<Edge>>;

vector<Cost> dijkstra
(Graph &graph, Node start, ll pat[], Cost zero = 0LL)
{
  using Pcn = pair<Cost,Node>;
  priority_queue<Pcn,vector<Pcn>,greater<Pcn>> que;
  vector<Cost> dist(graph.size(),inf<Cost>);
  dist[start] = zero;
  pat[start] = 1LL;
  que.push(Pcn(zero,start));
  while(!que.empty()){
    Pcn p = que.top(); que.pop();
    Node v = p.second; //行き先
    if(dist[v] < p.first)  continue;
    for(Edge e : graph[v]){
      if(dist[v]+e.cost < dist[e.to]){
        dist[e.to] = dist[v]+e.cost;
        // 最小値を更新したら今までのパターンを消す
        pat[e.to] = 0LL;
        que.push(Pcn(dist[e.to],e.to));
      }
      if(dist[v]+e.cost == dist[e.to]){
        // 最小値を見つけたらパターンを足す
        (pat[e.to] += pat[v]) %= lmod;
      }
    }
  }
  return dist;
}

Graph graph;
ll patS[MAX_N],patT[MAX_N];

int main(){
  int N,M; scanf("%d%d",&N,&M);
  graph.resize(N);
  int S,T; scanf("%d%d",&S,&T); S--; T--;
  rep(i,M){
    int l,r; ll dd; scanf("%d%d%lld",&l,&r,&dd);
    l--; r--; graph[l].pb(Edge(dd,r)); graph[r].pb(Edge(dd,l));
  }
  auto distS = move(dijkstra(graph,S,patS));
  auto distT = move(dijkstra(graph,T,patT));
  ll ans = patS[T] * patS[T] % lmod;
  ll len = distS[T];
  rep(i,N){
    if(distS[i]+distT[i]==len && distS[i]*2LL==len){
      (ans += (lmod - patS[i]*patS[i]%lmod*patT[i]%lmod*patT[i]%lmod)) %= lmod;
    }
  }
  rep(i,N) for(auto e:graph[i]){
    int j = e.to; ll c = e.cost;
    if(distS[i]+c+distT[j]==len && distS[i]*2LL<len && distT[j]*2LL<len){
      (ans += (lmod - patS[i]*patS[i]%lmod*patT[j]%lmod*patT[j]%lmod)) %= lmod;
    }
  }
  cout << ans << endl;
  return 0;
}