Codeforces Round #113 (Div. 2)

A.
成績が良い順にソートして、上からk番目のチームと同じ成績のチームがいくつあるかを答える問題。

struct team{
	int s,t;
	team(int s,int t)
	: s(s), t(t){}
};

bool operator < (const team& a, const team& b)
{
	return a.s < b.s || a.s == b.s && a.t > b.t;
}

map <team,int> data;
priority_queue <team> p;

int main(){
	int n,k;
	cin>>n>>k;
	
	for(int i = 0; i < n; i++){
		int a,b;
		cin>>a>>b;
		team te(a,b);
		
		p.push(te);
		data[te]++;
	}
	
	for(int i = 1; i < k; i++){
		p.pop();
	}
	cout<<data[p.top()]<<endl;
	
	return 0;
}

B.
幾何らしい

C.
単調増加する数列がある。真ん中に来ないといけない数字xがあって、xが中央に来るまで、数字を追加する。
追加する回数の最小値を求めよ。

xより大きい数字、等しい数字、小さい数字の個数をそれぞれ数えれば解けます。xがない場合はxを追加して、xがある場合と同じ処理をします。

xがどの範囲に存在するかを考えて、それの端点が中央にくるようにすれば解けます。

int main(){
	int n,to;
	cin>>n>>to;
	
	int d = 0,u = 0;
	
	for(int i = 0; i < n; i++){
		int a;
		cin>>a;
		if(a<to) d++;
		else if(a>to) u++;
	}
	
	int j = n-d-u,ans = 0;
	if(!j){
		ans++;
		j++;
		n++;
	}
	
	int left = d+1,right = d+j,point = (n+1)/2;
	int r = 0;
	/*入力が小さいので愚直に解く*/
	if(left>point){
		while(left>point){
			r++;
			n++;
			point = (n+1)/2;
		}
	}else while(right<point){
		r++;
		right++;
		n++;
		point = (n+1)/2;
	}
	
	ans += r;
	
	cout<<ans<<endl;
	
	
	return 0;
}

D.
Unopened

E.
点A,B,C,Dがあって、t=0の時に点Dにいる。1秒ごとに現在の点以外に移動する。t=nの時に点Dに戻ってくる経路はいくつあるか。

1 <= n <= 10^7 なのでDP(配列を使わなくても良い)で解けます。

勘違いして、行列を実装しました。実装したことが無かったので勉強になりましたが、コンテストなので、蟻本などを参照したほうが良かったかもしれません。

typedef long long ll;
const ll mod = 1000000007;

struct mat{
	ll a,b,c,d;
	mat(ll a,ll b, ll c, ll d)
	: a(a),b(b),c(c),d(d){}
	
};

void pow(mat &X){
	ll apd = (X.a+X.d) % mod;
	ll bmc = (X.b*X.c) % mod;
	X.b = (X.b*apd)%mod;
	X.c = (X.c*apd)%mod;
	X.a = (X.a*X.a+bmc)%mod;
	X.d = (X.d*X.d+bmc)%mod;
}

void mul(mat &A, const mat &B){
	ll a = A.a;
	ll b = A.b;
	ll c = A.c;
	ll d = A.d;
	A.a = (a*B.a+b*B.c)%mod;
	A.b = (a*B.b+b*B.d)%mod;
	A.c = (c*B.a+d*B.c)%mod;
	A.d = (c*B.b+d*B.d)%mod;
}

int main(){
	
	int n;
	cin>>n;
	n--;
	
	mat A(0,1,3,2);
	mat R(1,0,0,1);
	
	for(;n;n>>=1){
		if(n&1) mul(R,A);
		pow(A);
	}
	cout<<R.c<<endl;
	//cout<<R.a<<' '<<R.b<<' '<<R.c<<' '<<R.d<<endl;
	
	return 0;
}

DPする場合

t=nの時にDにいるような経路の総数をp_n、
A,B,Cにいるようなのをq_nとおくと、

p_0 = 1,q_0 = 0

p_(n+1) = q_n
q_(n+1) = 3*p_n + 2*q_n

となるので、これを実装すれば解けます(説明しませんでしたが、行列の場合はこれを行列にするだけです)。

o-o-o