SRM 664 Div1 Easy Bear Plays

組(X,Y)(X <=Y)を一回操作して(2X,Y-X)にするとき、石の総量S = X + Y は変化しない。よって、少ない方の個数がXのとき、一回の操作後に得られる組の少ない方の個数f(X)は

f(X) = 2X or S - 2X

これをmod S で見ると、f(X) ≡ 2X or -2X であるから、f^K (X) ≡ 2^K * X or -2^K * X

f^K (X) ≡ -2^K * X は個数がS - 2^K * X の場合に対応するから、X = min(A,B)として、min(2^K * X, S - 2^K * X) (mod S) が答えとなる。

#include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;

class BearPlays{
public:
  ll modpow(ll K, ll S){
    if(K == 0)return 1;
    if(K % 2) return (2 * modpow(K - 1, S)) % S;
    return (modpow(K/2, S) * modpow(K/2, S)) % S;
  };
  int pileSize(int A, int B, int K){
    ll S = A + B;
    A = min(A, B);
    ll res = (A * modpow(K,S)) % S;
    return min(res, S - res);
  };
};

Codeforces Round #304 (Div. 2) E Soldier and Traveling

sourceとsinkを追加し流量制限にa[i],b[i]を与えることで二部グラフのフローになることは本番中に気づいたが、YESだった場合に経路復元する方法が分からなかった。

考えてみると、逆辺のcapはその辺に流したフローの量であるから、ここから容易に復元することができる。

それと、source=2n, sink=2n+1 みたいに置いておくと、デバッグしやすいことを教えてもらった。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)

//Ford-Fulkerson's algorithm
struct edge{int to,cap,rev;};
const int INF=1e9;

void addEdge(vector<vector<edge> > &g,int from,int to,int cap){
    g[from].push_back((edge){to,cap,(int)g[to].size()});
    g[to].push_back((edge){from,0,(int)g[from].size()-1});
}

int dfs(vector<vector<edge> > &g,vector<bool> &used,int v,int t,int f){
    if(v==t) return f;
    used[v]=true;
    for(int i=0;i<(int)g[v].size();i++){
        edge& e=g[v][i];
        if(!used[e.to] && e.cap>0){
            int d=dfs(g,used,e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                g[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int FordFulkerson(vector<vector<edge> > &g,int s,int t){
    int flow=0;
    for(;;){
        vector<bool> used(g.size(),false);
        int f=dfs(g,used,s,t,INF);
        if(f==0) return flow;
        flow+=f;
    }
}
//

int main(){
	int n,m;
    cin >> n >> m;
    vector<int> a(n),b(n);
    REP(i,n) cin >> a[i];
    REP(i,n) cin >> b[i];
    vector<vector<edge> > g(2*n+2);
    int source=2*n;
    int sink=2*n+1;
    REP(i,n) addEdge(g,source,i,a[i]);
    REP(i,n) addEdge(g,n+i,sink,b[i]);
    REP(i,n) addEdge(g,i,n+i,INF);
    REP(i,m){
        int p,q;
        cin >> p >> q;
        addEdge(g,p-1,q-1+n,INF);
        addEdge(g,q-1,p-1+n,INF);
    }
    int sum1=0,sum2=0;
    REP(i,n){
        sum1+=a[i];
        sum2+=b[i];
    }
    int f=FordFulkerson(g,source,sink);
    if(f!=max(sum1,sum2)){
        cout << "NO" << endl;
    }else{
        vector<vector<int> > res(n,vector<int> (n));
        REP(i,n){
            for(auto e : g[i+n]){
                if(e.to<n) res[e.to][i]=e.cap;
            }
        }
        cout << "YES" << endl;
        REP(i,n){
            REP(j,n){
                if(j) cout << " ";
                cout << res[i][j];
            }
            cout << endl;
        }
    }
	return 0;
}

Codeforces Round #304 (Div. 2) D Soldier and Number Game

dp[i]をi以下の各自然数について素因数分解したときの素因数の個数の総和とすると、dp[a]-dp[b]が答えとなる。よって、前処理で素因数分解をしておけばいい。

エラトステネスの篩をするときにsieve[i]にiの素因数のひとつ(最小や最大のものに固定することもできる)を覚えておくと、素因数分解が簡単にできることを教えてもらった。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)

int sieve[6000000]={};
int dp[6000000]={};

int main(){
    sieve[0]=sieve[1]=1;
    for(int i=2;i*i<=5000000;i++){
        for(int j=2;i*j<=5000000;j++){
            if(sieve[i*j]) continue;
            sieve[i*j]=i;
        }
    }
    dp[0]=dp[1]=0;
	for(int i=2;i<=5000000;i++){
	    if(sieve[i]==0) dp[i]=1;
	    else dp[i] = dp[i/sieve[i]] + 1;
	}
	REP(i,5000000) dp[i+1]+=dp[i];
	int t;
    cin >> t;
    REP(i,t){
        int a,b;
        scanf("%d%d",&a,&b);
	    printf("%d\n",dp[a]-dp[b]);
    }
	return 0;
}

cin,cout は遅すぎ

高速メビウス変換について

高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。
(http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)

集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについてO(n2^n)でf(S)を計算することができる。
{ \displaystyle
    f(S) = \sum_{T \subset S} (-1)^{|S| - |T|} g(T) 
}

例えば、S={1,2,...,n}として、各i∈Sについて集合A_iが与えられているとき、和集合の要素数を計算したいとする。そして、
{ \displaystyle
    g(S) = |\bigcap_{i \subset S} A_i|
}
は任意のSについて計算が出来たとする。
このとき、
{ \displaystyle
    f(S) = \sum_{T \subset S} (-1)^{|S| - |T|} |\bigcap_{i \subset T} A_i|
}
に対して、包除原理の式
{ \displaystyle
    |\bigcup_{i \in S} A_i| = \sum_{T \subset S} (-1)^{|T|+1} |\bigcap_{j \in T} A_j|
}
を用いると、
{ \displaystyle
    f(S) = (-1)^{|S| - 1} |\bigcup_{i \subset S} A_i
}
となる。これの絶対値を取れば和集合の要素数を得られる。

さて、f(S)は次の漸化式を考えるとf(S)=f_n(S)として計算できることが証明できる。
{ \displaystyle
    f_0(S) = g(S) \\
    f_k(S) = f_{k-1}(S) , (k \not\in S) \\
    f_k(S) = -f_{k-1}(S-\{k\}) + f_{k-1}(S) , (k \in S)
}

bitDPをすることでこの漸化式はO(n2^n)で計算することができる。

これをそのまま書けば次のようになるはず。

//f[n+1][1<<n]
//f[0][T](=g[T]) は計算済みとする
for(int i=1;i<=n;i++)for(int S=0;S<(1<<n);S++){
    if(S & (1<<i)) f[i][S]=-f[i-1][S^(1<<i)]+f[i-1][S];
    else f[i][S]=f[i-1][S];
}

上のDPでは各iにおいて既に計算したSの値しか参照していないため、一次元配列を使いまわすことができる。

for(int i=0;i<n;i++)for(int S=0;S<(1<<n);S++) if(S & (1<<i)) f[S]-=f[S ^ (1<<i)];

ネットワークフロー

練習会でフロー関連の発表をした。内容は↓のとおり。

今までフローを避けてきたので、まとまった勉強をする良い機会となった。しかし、一般マッチングや最大マッチングと最小点カバーにおける関係などはまだ理解できてないので、もう少し蟻本を睨む必要がある。

SRM 657 Div1 Easy Problem Sets

二分探索するだけ。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ll long long

class ProblemSets {
public:

bool judge(ll E,ll EM,ll M,ll MH,ll H,ll num){
    ll x=max(0ll,num-E);
    ll y=max(0ll,num-H);
    if(x>EM || y>MH) return false;
    if(num>=M && M+EM+MH-x-y<num) return false;;
    return true;
}

long long maxSets(long long E, long long EM, long long M, long long MH, long long H) {
	 ll lb=0;
     ll ub=E+EM+M+MH+H;
     while(ub-lb>1){
        ll mid=(lb+ub)/2;
        if(!judge(E,EM,M,MH,H,mid)) ub=mid;
        else lb=mid;
     }
     return lb;
}
}

ARC 37 C問題 億マス計算

制約からして二分探索なんだろうとは思ったが本番では解けなかった。
a,bを最初にソートしておき、付値関数C(x)として次のものを考える。

C(x): a[i]*b[j]<=xとなる組(i,j)がK個以上あればtrue、なければfalseを返す

a[i]*b[pos]<=x , a[i]*b[pos+1]>x のとき、a[i]x なるpos'について
pos>pos' が成り立つ。従ってC(x)はO(N)で計算できる。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;

bool C(vector<ll> &a,vector<ll> &b,int K,ll x){
    int n=a.size();
    ll res=0;
    int pos=n-1;
    REP(i,n){
        while(pos>=0 && b[pos]>x/a[i]){
            pos--;
        }
        res+=pos+1;
    }
    if(res>=K) return true;
    else return false;
}

int main(){
	int N,K;
    cin >> N >> K;
    vector<ll> a(N),b(N);
    REP(i,N) cin >> a[i];
    REP(i,N) cin >> b[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    ll lb=0,ub=a[N-1]*b[N-1]+2;
    while(ub-lb>1){
        ll mid=(lb+ub)/2;
        if(C(a,b,K,mid)) ub=mid;
        else lb=mid;
    }
    cout << ub << endl;
	return 0;
}