参加記は
ここ→VKPC 2011 参加記 - kyuridenamidaのチラ裏
A
次元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
制約が恐いので、冗長なソースを書いた。
#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
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
問題文通りにソートして、シミュレートして、クエリに対しては二分探索しました。
#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
一番コストが掛かりそうな部分は、たどり着いていないところの更新。
これを愚直にやろうとすると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
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
解けてない。
I
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
解けてない。
K
幅優先探索するだけ。実は頭悪い実装をしている。状態数は初期状態を入れて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
実験すると√っぽいことが分かる。なぜか。
- ある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; }