Educational Codeforces Round 49 D Mouse Hunt
前回のままではさすがに芸が無いからsccの応用問題を解いてみたよ
Problem - 1027D - Codeforces
強連結成分分解→強連結成分どうしの隣接リストを作ってdfsの流れで
#include<cstdio> #include<vector> #include<algorithm> #include<climits> using namespace std; static const int MAX_N = 200000; int N; int c[MAX_N], a[MAX_N]; vector<int> G[MAX_N]; vector<int> rG[MAX_N]; vector<int> vs; bool used[MAX_N]; int cmp[MAX_N]; vector<int> G2[MAX_N]; int num[MAX_N]; bool visited[MAX_N]; void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i]]) dfs(G[v][i]); } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(int i = 0; i < rG[v].size(); i++){ if(!used[rG[v][i]]) rdfs(rG[v][i], k); } } int scc(){ fill(used, used + N, false); vs.clear(); for(int i = 0; i < N; i++){ if(!used[i]) dfs(i); } fill(used, used + N, false); int k = 0; for(int i = vs.size() - 1; i >= 0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } return k; } int dfs2(int s){ if(visited[s]) return 0; visited[s] = true; if(G2[s].size() == 0) return num[s]; int res = 0; for(int i = 0; i < G2[s].size(); i++){ if(visited[G2[s][i]]) continue; res += dfs2(G2[s][i]); } return res; } int main(){ scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d", &c[i]); for(int i = 0; i < N; i++){ scanf("%d", &a[i]); a[i]--; if(i == a[i]) continue; add_edge(i, a[i]); } int n = scc(); fill(num, num + n, INT_MAX); fill(visited, visited + n, false); for(int i = 0; i < N; i++){ num[cmp[i]] = min(num[cmp[i]], c[i]); if(cmp[i] == cmp[a[i]]) continue; G2[cmp[i]].push_back(cmp[a[i]]); } int res = 0; for(int i = 0; i < n; i++){ res += dfs2(i); } printf("%d\n", res); return 0; }
Peking University Online Judge 3180 The Cow Prom
・sccを貼っただけ
・全部の関数を使う必要があるのか
・そもそも本当にsccの問題なのか
などの理由で消化不良、本当に実力はついているのか
#include<cstdio> #include<vector> #include<algorithm> using namespace std; static const int MAX_N = 10000; int N, M; vector<int> G[MAX_N]; vector<int> rG[MAX_N]; vector<int> vs; bool used[MAX_N]; int cmp[MAX_N]; int num[MAX_N]; void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i]]) dfs(G[v][i]); } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(int i = 0; i < rG[v].size(); i++){ if(!used[rG[v][i]]) rdfs(rG[v][i], k); } } int scc(){ fill(used, used + N, false); vs.clear(); for(int i = 0; i < N; i++){ if(!used[i]) dfs(i); } fill(used, used + N, false); int k = 0; for(int i = vs.size() - 1; i >= 0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } return k; } int main(){ scanf("%d %d", &N, &M); for(int i = 0; i < M; i++){ int u, v; scanf("%d %d", &u, &v); u--; v--; add_edge(u, v); } int n = scc(); for(int i = 0; i < N; i++){ num[cmp[i]]++; } int res = 0; for(int i = 0; i < n; i++){ if(num[i] >= 2) res++; } printf("%d\n", res); return 0; }
Peking University Online Judge 3250 Bad Hair Day
やるだけ（すみません調子こきました嘘です）
ループの中でやっていることは
・i番目の人に注目する
・もしスタックが空でない場合、仮にスタックの中にi番目の人より背が低い人がいたら、
その人からはi番目以降に来る人の頭は絶対に見えないので、スタックから出ていってもらう
・スタックの中の人は全員i番目の人の頭が見えるので、スタックの中の人数を答えにプラスする。
・スタックにi番目の人を入れる
#include<cstdio> #include<stack> using namespace std; typedef long long int ll; int N, h; stack<int> sa; int main(){ scanf("%d", &N); ll res = 0LL; for(int i = 0; i < N; i++){ scanf("%d", &h); while(!sa.empty() && sa.top() <= h) sa.pop(); res += sa.size(); sa.push(h); } printf("%lld\n", res); return 0; }
Peking University Online Judge 2409 Let It Bead
昨日のコードを少しだけ弄ってAC
#include<cstdio> #include<vector> using namespace std; typedef long long int ll; static const int MAX_CS = 32; int c, s; vector<ll> va[MAX_CS + 1]; int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); } int main(){ for(int i = 1; i <= MAX_CS; i++){ for(int j = 0; j * i <= MAX_CS; j++){ if(j == 0) va[i].push_back(1LL); else va[i].push_back(va[i].back() * (ll)i); } } for(;;){ scanf("%d %d", &c, &s); if(c == 0 && s == 0) break; ll res = 0; for(int i = 1; i <= s; i++){ if(i == 1 || i == s){ res += va[c][s / i]; }else if(gcd(s, i) != 1){ res += va[c][gcd(s, i)]; }else{ res += c; } } for(int i = 1; i <= s; i++){ if(s % 2 == 0){ if(i % 2 == 0){ res += va[c][s / 2]; }else{ res += va[c][(s - 2) / 2 + 2]; } }else{ res += va[c][(s - 1) / 2 + 1]; } } printf("%lld\n", res / (ll)(s * 2)); } return 0; }
Peking University Online Judge 1286 Necklace of Beads
テストケースに0を忍ばせるとかいうアレ
ポリアの数え上げ定理を使いましたが、反転のパートは想像で書きました（バカなの？）
#include<cstdio> #include<vector> using namespace std; typedef long long int ll; int n; vector<ll> va; int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); } int main(){ for(int i = 0; i <= 24; i++){ if(i == 0) va.push_back(1LL); else va.push_back(va.back() * 3LL); } for(;;){ scanf("%d", &n); if(n == -1) break; if(n == 0){ printf("0\n"); continue; } ll res = 0; for(int i = 1; i <= n; i++){ if(i == 1 || i == n){ res += va[n / i]; }else if(gcd(n, i) != 1){ res += va[gcd(n, i)]; }else{ res += 3; } } for(int i = 1; i <= n; i++){ if(n % 2 == 0){ if(i % 2 == 0){ res += va[n / 2]; }else{ res += va[(n - 2) / 2 + 2]; } }else{ res += va[(n - 1) / 2 + 1]; } } printf("%lld\n", res / (ll)(n * 2)); } return 0; }
Peking University Online Judge 2407 Relatives
オイラーのΦ関数を返すだけ
なぜこの実装でΦ関数が実現できるかを理解することが重要ではないかと（お前誰だよ）
#include<cstdio> using namespace std; typedef long long int ll; ll euler_phi(ll n){ ll res = n; for(ll i = 2; i * i <= n; i++){ if(n % i == 0){ res = res / i * (i - 1); for(; n % i == 0; n /= i); } } if(n != 1) res = res / n * (n - 1); return res; } int main(){ ll n; for(;;){ scanf("%lld", &n); if(n == 0) break; printf("%lld\n", euler_phi(n)); } return 0; }
Aizu Online Judge 1132 Circle and Points
POJ にsubmitしてTLEしたコードを、そのままAOJに投げつけたら通りました(は？)
2点を全通り選んで、その2点を通る半径1の円を描き、それで囲める点の個数の最大値を調べる、という方針で（嘘解法かも知れない）
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; static const int MAX_N = 300; #define EPS (1e-10) class Point{ public: double x, y; Point(double x = 0, double y = 0): x(x), y(y) {} Point operator + (Point p){ return Point(x + p.x, y + p.y);} Point operator - (Point p){ return Point(x - p.x, y - p.y);} Point operator * (double a){ return Point(a * x, a * y);} Point operator / (double a){ return Point(x / a, y / a);} double abs(){ return sqrt(norm());} double norm(){ return x * x + y * y;} bool operator < (const Point &p) const{ return x != p.x ? x < p.x : y < p.y; } bool operator == (const Point &p) const{ return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS; } }; class Circle{ public: Point c; double r; Circle(Point c = Point(), double r = 0.0): c(c), r(r) {} }; typedef Point Vector; int N; Point p[MAX_N]; double arg(Vector p){return atan2(p.y, p.x);} Vector polar(double a, double r){return Point(cos(r) * a, sin(r) * a);} double getDistance(Point a, Point b){ return (a - b).abs(); } pair<Point, Point> getCrossPoints(Circle c1, Circle c2){ double d = (c1.c - c2.c).abs(); double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d)); double t = arg(c2.c - c1.c); return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)); } bool comp(const Point &a, const Point &b){ return a.x < b.x; } int main(){ for(;;){ scanf("%d", &N); if(N == 0) break; for(int i = 0; i < N; i++){ scanf("%lf %lf", &p[i].x, &p[i].y); } sort(p, p + N, comp); int res = 1; for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ if(p[j].x - p[i].x > 2.0) break; else if(getDistance(p[i], p[j]) > 2.0) continue; pair<Point, Point> pp = getCrossPoints((Circle){p[i], 1.0}, (Circle){p[j], 1.0}); Point p1 = pp.first, p2 = pp.second; int cnt1 = 2, cnt2 = 2; for(int k = 0; k < N; k++){ if(k == i || k == j) continue; if(p[k].x - p[j].x > 1.0) break; if(getDistance(p1, p[k]) < 1.0) cnt1++; if(getDistance(p2, p[k]) < 1.0) cnt2++; } res = max(res, max(cnt1, cnt2)); } } printf("%d\n", res); } return 0; }
