読者です 読者をやめる 読者になる 読者になる

VKPC2011のソース

参加記は

ここ→VKPC 2011 参加記 - kyuridenamidaのチラ裏

A

404 Not Found

次元nがいくつかだけ分かってないのでそれを全探索する。(適当)

logを使うとO(1)で求まるけどそんなことはしなかった。

#include <iostream>
using namespace std;
long long b_pow(long long x,long long n){
	return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;
}

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	int ans = 0;
	for(int i = 1 ; i <= 100 ; i++){
		if( a*b_pow(c,i) == b){
			cout << i << endl;
			break;
		}
	}
}

B

404 Not Found

制約が恐いので、冗長なソースを書いた。

#include <iostream>
#include <map>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

map<string,int> need;
map<string,int> get;
int main(){
	int m,n;
	cin >> m;
	rep(i,m){
		string a; cin >> a;
		need[a] = true;
	}
	cin >> n;
	rep(i,n){
		string a,b;
		cin >> a >> b;
		get[a.substr(0,a.length()-1)] = true;
	}
	EACH(it,need){
		if(get[it->first] == false){
			cout << "no" << endl;
			return 0;
		}
	}
	cout << "yes" << endl;
}

C

404 Not Found

2^20の全探索で通る。

#include <iostream>
using namespace std;


int v[100];
int main(){
	int ans = 999;
	long long m,n,a;
	cin >> m >> n;
	for(int i = 0 ; i < m ; i++) cin >> v[i];
	for(int i = 0 ; i < (1<<m) ; i++){
		long long ok = 0;
		for(int j = 0 ; j < m ; j++){
			if(i>>j&1){
				ok += v[j];
			}
		}
		if(ok == n) ans = min(ans,__builtin_popcount(i));
	}
	if(ans == 999) cout << "NA" << endl;
	else cout << ans << endl;
}

D

404 Not Found

問題文通りにソートして、シミュレートして、クエリに対しては二分探索しました。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)

int main(){
	vector< pair<int,int> > data;
	int n; cin >> n;
	for(int i = 0 ; i < n ; i++){
		int a,b;
		cin >> a >> b;
		data.push_back(make_pair(a,b));
	}
	sort(data.begin(),data.end());
	vector<int> foo;
	int cur = 0;
	for(int i = 0 ; i < n ; i++){
		if(data[i].first <= cur){
			cur += data[i].second;
		}else{
			cur += data[i].first - cur;
			cur += data[i].second;
		}
		foo.push_back(cur);
	}
	int m;
	cin >> m;
	rep(i,m){
		int t;
		cin >> t;
		cout << (upper_bound(foo.begin(),foo.end(),t) - foo.begin())<< endl;
	}
}

E

404 Not Found

一番コストが掛かりそうな部分は、たどり着いていないところの更新。

これを愚直にやろうとするとTLEするので、部分問題に分けてDPすることが必要。

移動の仕方的に、xかyを優先して適当にソートすると、次に通った地点が要素の隣に来るので、

それを使ってDP。

DPテーブルのループは合計で高々O(mn)なので、間に合う。ソース中のDTってなんだヨ・・・。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

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

struct DT{
	int x,y;
	DT(int x_,int y_){ x = x_ , y = y_;}
};

bool operator < (const DT &a,const DT &b){
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}

int dt[1003][1003];
int dp[1003][1003];


int f(int sx,int sy,int gx,int gy){
	memset(dp,0,sizeof(dp));
	dp[sy][sx] = 1;
	for(int i = sy ; i <= gy ; i++){
		for(int j = sx ; j <= gx ; j++){
			dp[i][j] %= 1000000007;
			if(dt[i][j])continue;
			dp[i+1][j] += dp[i][j];
			dp[i][j+1] += dp[i][j];
		}
	}
	return dp[gy][gx];
}
int main(){
	int m,n,k;
	cin >> m >> n >> k;
	vector<DT> yes;
	
	yes.push_back(DT(0,0));
	yes.push_back(DT(m,n));
	
	rep(i,k){
		int r,x,y;
		cin >> x >> y >> r;
		if(r==1){
			yes.push_back(DT(x,y));
		}else if(r==2){
			dt[y][x] = 1;
		}
	}
	sort(yes.begin(),yes.end());
	long long ans = 1;
	for(int i = 0 ; i < yes.size()-1 ; i++){
		int sx = yes[i].x , sy = yes[i].y;
		int gx = yes[i+1].x , gy = yes[i+1].y;
		ans = ans * f(sx,sy,gx,gy) % 1000000007;
	}
	cout << ans << endl;
	
}

F

404 Not Found

KUPCの練習セッションのAの強化版。本番のテストケースだと、logと強引な定数項改善で通ったりしてほげ。

最悪計算量は、O( |S|^2 * N log |S|^2 )くらいで、がんばると通る。通らないケースを作るのは結構大変である。

([23:31追記]うちの先輩の尺取法による解法が賢い(2011-08-28 - 2冊の本を3等分))

#include <iostream>
#include <set>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)

string v[1000];
set<string> ok;
int main(){
	set<string> yj[1000];
	int n;cin >> n;
	rep(i,n){
		cin >> v[i];
	}
	rep(x,n){
		for(int i = 0 ; i < v[x].size() ; i++){
			string s;
			for(int j = i ; j < v[x].size(); j++){
				s += v[x][j];
				yj[x].insert(s);
			}
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n-1; j++){
			if(v[j].length() > v[j+1].length()){
				swap(v[j],v[j+1]);
			}
		}
	}
	int ans = 0;
	for(int i = 0 ; i < v[0].size() ; i++){
		string s;
		for(int j = i ; j < v[0].size(); j++){
			s += v[0][j];
			if(s.size() <= ans) continue;
			if(ok.count(s))continue;
			bool f = true;
			rep(k,n){
				f &= yj[k].count(s);
				if(!f)break;
			}
			ok.insert(s);
			if(f) ans = max<int>(ans,s.size());
		}
	}
	cout << ans << endl;
}

G,H

404 Not Found

404 Not Found

解けてない。

I

404 Not Found

Xに1000とか入った上で、「ADD X X」とか「ADD X Y」-「ADD Y X」を繰り返すと、指数的に値が大きくなって、long longですら収まらなくなることが分かる。

多倍長が必要。

負の数含む多倍長どうしようもなかったのでJavaに逃げた。使い方を学ぶ。

import java.math.BigInteger;
import java.util.*;
class Main {
	class hoge{
		void run(){
			Scanner sc=new Scanner(System.in);
			BigInteger x=new BigInteger("0");
			BigInteger y=new BigInteger("0");
			String srr;
			while(true){
				if(!sc.hasNext()){
					System.out.println(x.toString());
					System.out.println(y.toString());
					return;
				}
				String str = sc.next();
				if(str.equals("INC")){
					String a = sc.next();
					if(a.equals("X")){
						x = x.add(new BigInteger("1"));
					}else{
						y = y.add(new BigInteger("1"));
					}
				}else if(str.equals("DEC")){
					String a = sc.next();
					if(a.equals("X")){
						x = x.subtract(new BigInteger("1"));
					}else{
						y = y.subtract(new BigInteger("1"));
					}
				}else if(str.equals("ADD")){
					String a = sc.next();
					String b = sc.next();
					if(a.equals("X")){
						if(b.equals("X")){
							x = x.add(x);
						}else if(b.equals("Y")){
							x = x.add(y);
						}else{
							x = x.add(new BigInteger(b));
						}
					}else{
						if(b.equals("X")){
							y = y.add(x);
						}else if(b.equals("Y")){
							y = y.add(y);
						}else{
							y = y.add(new BigInteger(b));
						}
					}

				}else if(str.equals("SUB")){
					String a = sc.next();
					String b = sc.next();
					if(a.equals("X")){
						if(b.equals("X")){
							x = x.subtract(x);
						}else if(b.equals("Y")){
							x = x.subtract(y);
						}else{
							x = x.subtract(new BigInteger(b));
						}
					}else{
						if(b.equals("X")){
							y = y.subtract(x);
						}else if(b.equals("Y")){
							y = y.subtract(y);
						}else{
							y = y.subtract(new BigInteger(b));
						}
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		new Main().new hoge().run();
	}
}

J

404 Not Found

解けてない。

K

404 Not Found

幅優先探索するだけ。実は頭悪い実装をしている。状態数は初期状態を入れてO(n+1)通り。

移動する時間・ダイバージェンスは絶対的な値ということに気づかないと難しく見えるが、ちゃんと読めればとても簡単。

#include <iostream>
#include <queue>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int d1[1000],t1[1000],d2[1000],t2[1000];

struct NODE{
	int d,t,r;
	NODE(int a,int b,int c){d = a , t = b , r = c;}
};
bool operator < (const NODE &a , const NODE &b){
	return a.d == b.d ? a.t < b.t : a.d < b.d;
}

int main(){
	int N;
	cin >> N;
	rep(i,N){
		cin >> d1[i] >> t1[i] >> d2[i] >> t2[i];
	}
	queue<NODE> Q;
	Q.push(NODE(0,0,0));
	map<NODE, bool > done;
	while(Q.size()){
		NODE q = Q.front(); Q.pop();
		if(done[q]) continue;
		else done[q] = true;
		if(q.d >= 1000000){
			cout << q.r << endl;
			return 0;
		}
		rep(i,N){
			if(q.t <= t1[i] && q.d == d1[i] ){
				Q.push(NODE(d2[i],t2[i],q.r+1));
			}
		}
	}
	cout << -1 << endl;
}

L

404 Not Found

実験すると√っぽいことが分かる。なぜか。

  • あるn番目に着目したとき、そこは(nの1を除いた約数の個数)回反転する。
  • (約数の個数-1)が奇数になるとβ世界、偶数ならα世界。そしてそのような性質を持つ数は平方数である。
  • なぜならば、約数は基本的にペアが居て、9,16とかの平方数の時だけ、(3,3),(4,4)などのダブるペアが生じるので、奇数個になる。そこから-1したら偶数になる。
  • よって、基本的にはn未満の平方数の数を数える問題に帰着でき、「α世界の数はnを除くと、floor(√(n-1))個だから、移動する回数はn回」。
#include <iostream>
using namespace std;

int main(){
	long long n;
	cin >> n;
	cout << (long long)(sqrt(n)-EPS) << endl;
}