SRM 641 Div1 Medium ShufflingCardsDiv1

最終状態から、初期状態に戻していく方針で考察していく。

まず、0回のシャッフルで良い場合は 0 を返す。
それ以外の場合は、
0-origin で偶数番目のカードについて、初期状態で先頭 N 枚に来るカード (すなわち N 以下の数が書かれたのカード) の枚数を X とする。
手で考察すると、以下のような結果が得られる。

1 回のシャッフルで X = N になる。
2 回のシャッフルで X = ceil((N+1)/2) になる。
N が偶数のときは、3回のシャッフルで X は任意の整数にできる。
N が奇数のときは、3回のシャッフルで X は 1 以上の整数にでき、4回のシャッフルで X は任意の整数にできる。

class ShufflingCardsDiv1 {
	public:
	int shuffle(vector <int> a) {
		int n = a.size();
		bool ok = true;
		rep(i, n) if(a[i]!=i+1) ok = false;
		if(ok) return 0;
		int cnt = 0;
		rep(i, n/2) if(a[i*2]<=n/2) cnt++;
		if(cnt==n/2) return 1;
		if(cnt==(n/2+1)/2) return 2;
		if(n/2%2==0 || cnt>0) return 3;
		return 4;
	}
};

SRM 633 Div1 Medium DoubleTree

まず根を 1 つ固定して考える。すると、頂点 x を用いるならば、x の親の頂点 y を用いるという制約がある上でできるだけスコアが大きくなるように頂点集合を選ぶ問題になる。
これは典型最小カット問題 (燃やす埋める問題) なので、最大フローを計算することで答えが求まる。

根を固定することがポイントで、根を固定しないでグラフを構成しようとすると、頂点 x と 頂点 y を用いるならば、その間の頂点を用いるという制約になり、これは最小カットに帰着することができない。

#define N 55
vector<int> g1[N], g2[N], sc;
bool used[N];
int n, s, t;

class DoubleTree {
public:
	void dfs(int u, vector<int> g[N]){
		used[u] = true;
		for(auto &&v: g[u]){
			if(used[v]) continue;
			add_edge(v, u, INF);
			dfs(v, g);
		}
	}
	ll solve(int r){
		rep(i, V) G[i].clear();
		ll sum = 0;
		rep(i, n){
			if(sc[i]<0) add_edge(i, t, -sc[i]);
			else add_edge(s, i, sc[i]), sum += sc[i];
		}
		mset(used, 0);
		dfs(r, g1);
		mset(used, 0);
		dfs(r, g2);
		return sum-max_flow(s, t);
	}
	int maximalScore( vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> sc_) {
		sc=sc_;
		n = sc.size();
		rep(i, n-1){
			g1[a[i]].pb(b[i]);
			g1[b[i]].pb(a[i]);
			g2[c[i]].pb(d[i]);
			g2[d[i]].pb(c[i]);
		}
		s = n; t = s+1;
		ll res = 0;
		rep(i, n) chmax(res, solve(i));
		return res;
	}
};

SRM 632 Div1 Medium CandyCupRunningCompetition

辺の容量にものすごく差がある場合の max flow を解く。
辺 i の容量は、3^i で、コストが大きい辺から greedy に使っていけばよい。(容量の小さい辺を通るフローのために容量を残しても解は大きくならないので)

容量が大きい方から辺を追加していき、その辺の容量を使い切るようなフローが存在する場合は、フローを流して辺を削除すればよい。
フローが存在するかの判定には Union-FInd Tree を用いて、辺を削除する場合は、辺の追加をキャンセルすることで実装すると見通しが良くなる。

#define L 2010
ll th[L]; // 3^i
	int findMaximum( int N, vector <int> A, vector <int> B ) {
		UF uf;
		uf.init(N);
		int m = A.size();
		th[0] = 1;
		rep(i, m) th[i+1] = th[i]*3%mod;
		ll res = 0;
		for(int i = m-1; i >= 0; i--){
			ll a = uf.find(0), b = uf.find(N-1), c = uf.find(A[i]), d = uf.find(B[i]);
			if((a==c&&b==d)||(a==d&&b==c)){
				(res+=th[i])%=mod;
			} else uf.unite(A[i], B[i]);
		}
		return res;
	}

SRM 591 Div1 Med PyramidSequences

editorial にわかりやすく解法が纏まっているが、良問なので(できるだけ)自力で解く方が良さそう。
https://apps.topcoder.com/wiki/display/tc/SRM+591

一応ヒントを出すと、整数のペアなので、それに対する典型手法を用いると見通しが良くなります。(editorial の 2 行目にその手法が書いてあります。)

class PyramidSequences {
	public:
	long long distinctPairs(ll N, ll M) {
		ll n2 = N-1, m2 = M-1;
		ll g = __gcd(n2, m2);
		ll n3 = n2/g, m3 = m2/g;
		ll d = (n3-1)*(m3-1)/2;
		return n2*m2/g-d+1;
	}
};

SRM 590 Div1 Med XorCards

全く分からず、Editorial を見ながら通した。
xor なので、GF(2) での連立方程式の解の個数と対応している。解の個数は、2^(自由度) = 2^(n-rank) となっている。
rank を求める必要があり、難しい版の gauss-jordan を実装する必要がある。

#define N 60
vector<ll> a;
int n;
ll lim;

class XorCards {
	public:
	ll rank(vector<ll> &A, int m){
		int cnt = 0;
		rep(i, m){
			ll k = cnt;
			while(k<N-1){
				if(1&(A[k]>>i)) break;
				k++;
			}
			if(1&(A[k]>>i));
			else continue;
			swap(A[cnt], A[k]);
			rep(j, N){
				if(j!=cnt && (1LL&(A[j]>>i))) A[j]^=A[cnt];
			}
			cnt++;
		}
		rep(i, N) if(A[i]==(1LL<<(m))) return -1;
		int res = 0;
		rep(i, N) if(A[i]) res++;
		return res;
	}
	ll calc(ll l, int b){
		vector<ll> c(a);
		rep(i, n) c[i]>>=b;
		c.pb(l);
		vector<ll> A(N, 0);
		for(int i = 0; i < N; i++) rep(j, n+1) A[i] |= (1LL&(c[j]>>i))<<j;
		ll r = rank(A, n);

		return r==-1?0:1LL<<(n-r);
	}
	long long numberOfWays(vector<long long> number, long long limit) {
		a = number; lim = limit;
		n = a.size();
		sort(all(a)); reverse(all(a));
		ll res = calc(lim, 0);
		rep(i, N){
			if(1LL&(lim>>i)) res += calc((lim>>i)^1LL, i);
		}
		return res;
	}
};

ARC 009 C

C - 高橋君、24歳

問題概要

Nコのポストに手紙を届ける。Kコの手紙だけ正しくないポストに届き、すべてのポストに手紙が1コずつ届く。このとき、ポストと手紙の対応関係は mod 1777777777 (素数) で何通りか。(2 <= N <= 1e18, 2 <= K <= 1e6)

• ヒント1

正しく届かない手紙・ポストの集合を固定して考える。

• ヒント2

正しく届かない手紙・ポストの集合は K なので、まずは N = K の場合で解くことを考える。
すると、ポスト・手紙がそれぞれ K コあり、どれも正しく届かない届き方のが何通りあるのか計算する問題になる。
これは、正しく届く手紙の集合に関する包除原理で計算することができる。

#define N 2000000
ll inv[N], fact[N], ifact[N], be[N];
 
ll comb(ll a, ll b){
	return fact[a+b]*ifact[a]%mod*ifact[b]%mod;
}
 
ll comb_nk(ll n, ll k){
	return comb(n-k, k);
}
 
ll pow_mod(ll a, ll r, ll m){
	ll x = 1;
	while(r){
		if(r&1) (x*=a)%=m;
		(a*=a)%=m;
		r>>=1;
	}
	return x;
}
 
void init_fact(ll n = N){
    inv[1] = 1;
    for(int i = 2; i < n; i++) inv[i] = inv[mod%i] * (mod - mod/i) % mod;
	fact[0] = ifact[0] = 1;
	for(int i = 1; i < n; i++){
		fact[i] = (fact[i-1]*i)%mod;
		ifact[i]=(ifact[i-1]*inv[i])%mod;
	}
}

int main(){
	init_fact();
	ll n, k;
	cin>>n>>k;
	ll res = 0;
	rep(i, k+1){
		(res+=fact[k-i]*comb_nk(k, i)%mod*(i%2?-1:1))%=mod;
	}
	(res*=ifact[k])%=mod;
	rep(i, k) (res*=(n-i)%mod)%=mod;
	res += mod;
	cout<<res%mod<<endl;
	return 0;
}

CODE FESTIVAL 2016 Grand Final G

FESTIVA (256^0 の位)
+ (AVITSE+F) + (AVITSE+FF)+ (AVITSE+FFFF) +... +(AVITSE+FF...FF) (256^1 の位)
+ (AVITS + E) + ... (AVITS + EE...EE) (256^2 の位)
...
+ AA...AA (256^7 の位)
のような文字列を考えると、256進数と対応する。
文字数は、高々 1960 + 255*8 = 4000 文字となり制約を満たす。(256^8 >= 1e9 なので、実際にはこれよりも文字数が小さく構成される。)

#define M 256
int main(){
	ll x;
	cin>>x;
	vector<int> res; res.reserve(5000);
	rep(i, 7) res.pb(i);
	rep(i, 8){
		ll y = x%M;
		if(i==7) y = x;
		rep(k, y) res.pb(7);
		x /= M;
		if(i==7) break;
		rep(j, 8){
			for(int k = 6; k >= i+1; k--) res.pb(k);
			rep(k, 1<<j) res.pb(i);
		}
	}
	string s, fes = "FESTIVAL";
	rep(i, res.size()) s += fes[res[i]];
	cout<<s<<endl;
	return 0;
}