UTPC2012
東京大学プログラミングコンテスト2012 に先週参加してました。
期末テストから解放されたので記事書きます。
A:100
B:100
C:50
F:0.52
合計 250.52
順位 66位
でした。
実力相応です。
A
#include <cstdio> #include <algorithm> using namespace std; int y, m, d; bool u[4]; int a[4]; bool solve(int n, int s){ if(n == 4){ if(s == y) return true; else return false; } bool f = false; for(int i = 0; i < 4; i++){ if(!u[i]){ u[i] = true; f = f||solve(n+1, s * 10 + a[i]); u[i] = false; } } return f; } int main(){ scanf("%d/%d/%d", &y, &m, &d); a[0] = m/10; a[1] = m%10; a[2] = d/10; a[3]=d%10; fill(u, u + 4, false); if(solve(0,0)) printf("yes\n"); else printf("no\n"); return 0; }
B
#include <cstdio> #include <iostream> #include <string> #include <algorithm> using namespace std; string str; int L; bool u[8]; char s[9]; bool c(){ int p = -1; for(int i = 0; i < 8; i++){ char l = s[i]; int j; for(j = L-1; str[j] != l && j >= 0; j--){;} if(!(p <= j)) return false; p = j; } return true; } bool solve(int n){ if(n == 8){ //printf("%s\n",s); if(c()){ printf("%s\n",s); return true; }else{ return false; } } for(int i = 0; i < 8; i++){ if(!u[i]){ u[i] = true; s[n] = 'A' + i; if(solve(n + 1)) return true; u[i] = false; } } return false; } int main(){ cin >> str; L = str.size(); fill(u, u + 8, false); solve(0); return 0; }
C(50)
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100; int N, M; int a[MAX_N][MAX_N]; bool u[MAX_N]; bool ua[MAX_N][MAX_N]; bool c(int v){ bool f = true; for(int i = 0; i < N; i++){ if(a[v][i] == 1){ if(!u[i]){ ua[v][i] = true; ua[i][v] = true; u[i] = true; f = f&&c(i); }else if(!ua[v][i]){ return false; } } } return f; } int main(){ scanf("%d %d", &N, &M); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){ if(i != j)a[i][j] = 1; } for(int i = 0; i < M; i++){ int s, t; scanf("%d %d", &s, &t); s--; t--; if(a[s][t] == 1){ a[s][t] = 0; a[t][s] = 0; }else{ a[s][t] = 1; a[t][s] = 1; } bool f = true; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++) for(int k = 0; k < N; k++) ua[j][k] = false; fill(u, u+MAX_N, false); u[i] = true; f = f && c(i); } if(f) printf("yes\n"); else printf("no\n"); } return 0; }
F(0.52)
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll A, B; ll mod_pow(ll a, ll n){ ll ret = 1; ll t = a; while(n){ if(n&1) ret = ret * t % B; t = t * t % B; n >>= 1; } return ret; } int main(){ scanf("%lld %lld", &A, &B); for(int i = 1; i < 50; i++){ if(mod_pow(A, i) == 0){ for(int j = 0; j < 26 ; j++){ printf("%c", 'a' + j); for(int k = 1; k <= i; k++){ printf("a"); } puts(""); } return 0; } } return 0; }
Cの解きなおし
C(100)
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 1001; int N, M; vector<int> G[MAX_N]; bool u[MAX_N]; bool c(int p, int v){ u[v] = true; for(int i = 0; i < G[v].size(); i++){ int t = G[v][i]; if(t == p) continue; if(u[t]) return false; if(!c(v, t)) return false; } return true; } int main(){ scanf("%d %d", &N, &M); int n = N * (N - 1) / 2; if(M < n - (N - 1) || N > 1000){ for(int i = 0; i < M; i++) puts("no"); return 0; } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(i == j) continue; G[i].push_back(j); } } for(int i = 0; i < M; i++){ int s, t; scanf("%d %d", &s, &t); s--; t--; bool f = false; for(int j = 0; j < G[s].size(); j++){ if(G[s][j] == t){ f = true; vector<int>::iterator it = G[s].begin() + j; G[s].erase(it); break; } } if(f){ for(int j = 0; j < G[t].size(); j++){ if(G[t][j] == s){ vector<int>::iterator it = G[t].begin() + j; G[t].erase(it); break; } } n--; }else{ G[t].push_back(s); G[s].push_back(t); n++; } if(n < N){ fill(u, u + MAX_N, false); bool b = true; for(int i = 0; i < N; i++){ if(!u[i] && !c(-1, i)){ b = false; break; } } if(b) puts("yes"); else puts("no"); }else{ puts("no"); } } return 0; }