kurarrr's memooo

主に競プロ備忘録

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

COLOCON 2018 final C - スペースエクスプローラー高橋君

AtCoder 競プロ

問題概要

N個の整数 {a_i} (i=1,2,..,N) が与えられる.
各 i = 1,2,..,N について min_(1<=j<=N) (a_j + (j-i)2) を求めよ.
1 <= N <= 2*105, 1 <= a_i <= 1012

解法

a_j + (j-i)2 = i2 + (-2ji + j2 + a_j) より,
各iについて, (-2ji + j2 + a_j)を最小化すれば良い.
これはiの一次関数なため,Convex Hull Trickを使って全体でO(N)でできる.

簡単に言うと,最小値を達成する区間があるような直線を
傾きで降順ソートして持っておき,(今回の場合は-2iがそのまま降順になっているためソート不要)
左から走査していくと各直線を毎回見る必要はないと言うもの.
詳しい解説はこことか.

メモ

Convex Hull Trickを知らなかったので今度からできるように.

コード

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

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<class Data>
struct ConvexHullTrick {
  deque<pair<Data, Data>> l;
  bool check(pair<Data, Data> l3) {
    // l2(lの末尾)が不必要か
    const auto l1 = *prev(end(l), 2);
    const auto l2 = *prev(end(l), 1);
    Data a = (l2.first - l1.first) * (l3.second - l2.second);
    Data b = (l2.second - l1.second) * (l3.first - l2.first);
    return a >= b;
  }
  bool empty() const { return l.empty(); }
  void add(Data a, Data b) {
    // 傾きが単調減少するように
    if (!empty()) assert (l.back().first >= a);
    pair<Data, Data> n(a, b);
    while ((int)l.size() >= 2 && check(n)) l.pop_back();
    l.emplace_back(n);
  }
  Data f(int k, Data x) { return l[k].first * x + l[k].second; }
  Data minimum(Data x) {
    // xが単調増加するように
    assert (!empty());
    while ((int)l.size() >= 2 && f(0, x) >= f(1, x)) l.pop_front();
    return f(0, x);
  }
};

ConvexHullTrick<ll> cht;

int main(){
  int N; cin >> N;
  for(ll j = 1LL; j <= ll(N); j++){
    ll a; scanf("%lld",&a);
    cht.add(-2*j,j*j+a);
  }
  for(ll i = 1LL; i <= ll(N); i++){
    cout << i*i+cht.minimum(i) << endl;
  }
  return 0;
}

ARC 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

AtCoder 競プロ

問題概要

N頂点M辺のグラフが与えられる.各辺には種類c_iがある.
頂点1からNに行くには最低何種類のパスをまたぐ必要があるか.
* 種類1 -> 2 -> 1 は3種類と数える.
2<=N<=105, 0<=M<=2*106, 1 <= c_i <= 106

解法

a b cのような辺に対して,
(a,c) <=> (a,0)
↕︎
(b,c) <=> (b,0)
と辺を張って最終的な答えを2で割るとうまくいく.(<=>はコスト1,↕︎はコスト0)
片方だけ1にして最終的な出力にしても良い.
ただし,全ての状態数NxMについて領域を確保するとMLEするのでunordered_mapを使って上手いことやる.
unordered_mapとmapの違いは前者がhashでO(1), 後者が二分木でO(logN).
(頂点,会社)を頂点としても良いが,64ビット変数に押し込むと楽.
追加する頂点数は高々辺の数*2なので,O*1で解ける.

解説放送の方法は(a,c)と(b,c)を同一視して,同じ会社の他社を介さずに行ける頂点全てに辺を張って2部グラフを作っていた.
こっちの方がノードが少なくなるので多分高速.

メモ

典型ぽいので覚えよう.
PlをPと書いてオーバーフローするクソみたいなミスした.

コード

#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<int,ll>;

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;

class Edge{
  public:
    int cost; ll to;
    Edge(int cost,ll to)
      :cost(cost),to(to){}
};

void dijkstra(ll start,unordered_map<ll,vector<Edge>> &graph,unordered_map<ll,int> &dist){
  priority_queue<Pl,vector<Pl>,greater<Pl>> que;
  dist[start] = 0;
  que.push(Pl(0,start));
  while(!que.empty()){
    Pl p=que.top(); que.pop();
    ll v=p.second; //行き先
    if(dist[v]==0&&v!=0LL) dist[v] = INF;
    if(dist[v]<p.first) continue;
    for(Edge e: graph[v]){
      if(dist[e.to]==0&&e.to!=0LL) dist[e.to] = INF;
      if(dist[v]+e.cost<dist[e.to]){
        dist[e.to]=dist[v]+e.cost;
        que.push(Pl(dist[e.to],e.to));
      }
    }
  }
  return ;
}

void add_edge(ll p,ll q,ll c,unordered_map<ll,vector<Edge>> &graph){
  ll p0,pc,q0,qc;
  p0 = ll(p); q0 = ll(q);
  pc = p0 | (c<<30);
  qc = q0 | (c<<30);
  graph[p0].pb(Edge(1,pc));
  graph[pc].pb(Edge(1,p0));
  graph[pc].pb(Edge(0,qc));
  graph[qc].pb(Edge(0,pc));
  graph[qc].pb(Edge(1,q0));
  graph[q0].pb(Edge(1,qc));
}

int main(){
  ll N,M; cin >> N >> M;
  unordered_map<ll,vector<Edge>> graph;
  unordered_map<ll,int> dist;
  rep(i,M){
    ll p,q,c; scanf("%lld%lld%lld",&p,&q,&c);
    p--; q--;
    add_edge(p,q,c,graph);
  }
  dijkstra(0LL,graph,dist);
  ll ans;
  if(dist[ll(N-1)]!=0 && dist[ll(N-1)]!=INF){
    ans = dist[ll(N-1)]/2LL;
  }else{
    ans = -1LL;
  }
  cout << ans << endl;
  return 0;
}

*1:N+M)log(N+M