snuke21
https://snuke21.contest.atcoder.jp/
すぬけのお誕生日コンテストでした。
上位 6 位の人です。おめでとうございます。
1. cgy4ever (78)
2. semiexp (78)
3. IQモンスター (70)
4. ຣസںƙᘓ (66)
5. yutaka1999 (54)
6. uwi (50)
簡単な解説をします
A
これはやるだけです。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; int main(void){ ll n; cin >> n; ll x = (ll)(sqrt(n * 8.0 + 1.0) / 2.0); if(x * (x + 1) / 2 == n){ cout << x << endl; } else { cout << -1 << endl; } return 0; }
B
前にある s から順に greedy に使うかどうか決定していきます。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) char buf[100010]; int N,K; string s; int cnt[100010]; bool big[100010]; bool alive[100010]; int main(void){ int i; cin >> K; scanf("%s", buf); s = buf; N = s.length(); for(i=N-1;i>=0;i--){ cnt[i] = cnt[i+1]; if(s[i] == 's') cnt[i]++; } for(i=N-1;i>=0;i--){ big[i] = big[i+1]; if(s[i] > 's') big[i] = true; if(s[i] < 's') big[i] = false; } REP(i,N) if(s[i] == 's'){ if(K == 0){ alive[i] = true; } else if(K == cnt[i]){ alive[i] = false; K--; } else if(big[i]){ alive[i] = true; } else { alive[i] = false; K--; } } string ans; REP(i,N) if(s[i] != 's' || alive[i]) ans += s[i]; printf("%s\n", ans.c_str()); return 0; }
C
簡単な bid dp です
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) char buf[20]; int N; int mask[10010]; int dp[(1<<12)]; int main(void){ int i,j; cin >> N; REP(i,N){ scanf("%s", buf); REP(j,12) if(buf[j] == 'o') mask[i] |= (1<<j); } for(i=(1<<12)-1;i>=0;i--) REP(j,N) if((i | mask[j]) > i) dp[i] = max(dp[i], dp[i|mask[j]] + 1); cout << dp[0] << endl; return 0; }
D
たとえば t = "01001" のとき、t が s の subsequence になるのは
s = (1..1)0(0..0)1(1..1)0(1..1)0(0..0)1(任意の文字列)
となるときです。この性質を使うと解けます。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; #define MOD 1000000007ll ll comb[4010][4010]; ll func(int sum, int groups){ if(groups == 0){ if(sum == 0) return 1; return 0; } return comb[sum+groups-1][sum]; } int main(void){ int A,B,C,D,i,j; REP(i,4010) REP(j,i+1){ if(j == 0 || j == i) comb[i][j] = 1; else comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } cin >> A >> B >> C >> D; swap(A, C); C -= A; swap(B, D); D -= B; ll ans = 0; REP(i,C+1) REP(j,D+1){ ll tmp = comb[i+j][i] * func(C-i, B) % MOD * func(D-j, A) % MOD; ans = (ans + tmp) % MOD; } cout << ans * comb[A+B][A] % MOD << endl; return 0; }
E
トーナメントグラフ G の強連結成分の個数は、
G の頂点集合の non-empty subset S であって
S の中から外へ行く辺がないようなものの個数と一致します。
この性質を使うと解けます。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; #define MOD 1000000007ll ll F[100010]; ll power(ll x, ll n){ if(n == 0) return 1; ll y = power(x, n/2); y = y * y % MOD; if(n%2 == 1) y = y * x % MOD; return y; } ll comb(int N, int K){ return F[N] * power(F[K], MOD-2) % MOD * power(F[N-K], MOD-2) % MOD; } int main(void){ int N,i; F[0] = 1; for(i=1;i<=100000;i++) F[i] = F[i-1] * i % MOD; cin >> N; ll ans = 0; REP(i,N){ ll edge = (ll)i * (i-1) / 2 + (ll)(N-i) * (N-i-1) / 2; ll tmp = comb(N, i) * power(2, edge) % MOD; ans = (ans + tmp) % MOD; } cout << ans << endl; return 0; }
F
区間を分割して max + second max を最小化する問題です。
1. max を最小化する場合
2. max が元からあった区間である場合
の二通りがあります。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; int N,K,L; int x[100010]; double min_max(void){ int i,j; double low = 0.0, high = L; REP(i,100){ double mid = (low + high) / 2.0; ll sum = 0; REP(j,N) sum += (ll)(x[j] / mid); if(sum <= K) high = mid; else low = mid; } return high; } int main(void){ int i,j; cin >> L >> N >> K; x[N] = L; REP(i,N) scanf("%d", &x[i]); REP(i,N) x[i] = x[i+1] - x[i]; double ans = 2.0 * min_max(); sort(x, x+N); int l = -1, r = N-1; while(r - l > 1){ int m = (r + l) / 2; ll sum = 0; REP(i,N) sum += (ll)(x[i] - 1) / x[m]; if(sum <= K) r = m; else l = m; } double tmp = x[r]; x[r] = x[N-1]; N--; double tmp2 = min_max(); ans = min(ans, tmp + tmp2); ans /= 2.0; printf("%.12f\n", ans); return 0; }
G
三頂点 (g, s, b) の組であって
辺 s -> g, b -> g, b -> s が存在せず、かつ g, s, b からその他の頂点への変がないものを数えます。
g -> s, g -> b, s -> b が存在するかどうかによって場合わけします。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; int N,M; vector <int> graph[100010]; int deg[100010],deg2[100010]; int main(void){ int i,j,a,b; cin >> N >> M; REP(i,M){ scanf("%d%d", &a, &b); a--; b--; graph[b].push_back(a); } REP(i,N){ set <int> s; REP(j,graph[i].size()) s.insert(graph[i][j]); graph[i].clear(); snuke(s,itr) graph[i].push_back(*itr); } REP(i,N) deg[i] = graph[i].size(); int leaf = 0; REP(i,N) if(deg[i] == 0) leaf++; ll ans = (ll)leaf * (leaf - 1) * (leaf - 2); REP(i,N) if(deg[i] == 1){ int p = graph[i][0]; if(deg[p] == 0) ans += (leaf - 1) * 3; if(deg[p] == 1 && deg[graph[p][0]] == 0) ans++; deg2[p]++; } REP(i,N) if(deg[i] == 2){ int p = graph[i][0], q = graph[i][1]; if(deg[p] == 0 && deg[q] == 0) ans += 2; if(deg[p] == 0 && deg[q] == 1 && graph[q][0] == p) ans++; if(deg[p] == 1 && deg[q] == 0 && graph[p][0] == q) ans++; } REP(i,N) if(deg[i] == 0) ans += (ll)deg2[i] * (deg2[i] - 1); cout << ans << endl; return 0; }
H
C >= A+B ならば YES です。
また、ord 2 で考えると C <= A+B-80 ならば NO であることがわかります。
その他の場合は C+1, C+2, ..., A+B の素因数を全部チェックします。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; ll ord(ll N, ll p){ ll ans = 0; while(N > 0){ N /= p; ans += N; } return ans; } bool check(ll A, ll B, ll C){ if(C >= A + B) return true; if(C < A + B - 80) return false; for(ll x=C+1;x<=A+B;x++){ ll y = x; for(ll p=2;p*p<=y;p++) if(y % p == 0){ while(y % p == 0) y /= p; if(ord(A, p) + ord(B, p) > ord(C, p)) return false; } if(y > 1 && ord(A, y) + ord(B, y) > ord(C, y)) return false; } return true; } int main(void){ ll A,B,C; cin >> A >> B >> C; bool ans = check(A, B, C); cout << (ans ? "YES" : "NO") << endl; return 0; }
I
全ての辺の |dx| + |dy| の和が 4000000 以下である必要があるので、|dx| + |dy| の小さいほうから詰め込みます。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; struct edge {int dx,dy;}; bool operator<(const edge &e, const edge &f){ bool eup = (e.dy > 0 || (e.dy == 0 && e.dx > 0)); bool fup = (f.dy > 0 || (f.dy == 0 && f.dx > 0)); if(eup && !fup) return true; if(!eup && fup) return false; return (ll)e.dx * f.dy > (ll)e.dy * f.dx; } vector <edge> v; int gcd(int x, int y){ return x ? gcd(y%x, x) : y; } int M; int x[100010],y[100010]; int main(void){ int cnt=0,peri=0,s,i,j; // 169, 35242 for(s=1;s<=169;s++) REP(i,s) if(gcd(s, i) == 1){ int dx = i, dy = s-i; REP(j,4){ edge e = {dx, dy}; v.push_back(e); swap(dx, dy); dx = -dx; } } s = 170; REP(i,120) if(gcd(s, i) == 1){ int dx = i, dy = s-i; REP(j,4){ edge e = {dx, dy}; bool bad = false; if(dx == 83 && dy == 87) bad = true; if(dx == -83 && dy == -87) bad = true; if(!bad) v.push_back(e); swap(dx, dy); dx = -dx; } } sort(v.begin(),v.end()); M = v.size(); REP(i,M-1){ x[i+1] = x[i] + v[i].dx; y[i+1] = y[i] + v[i].dy; } int minx = 0, miny = 0; REP(i,M){ minx = min(minx, x[i]); miny = min(miny, y[i]); } REP(i,M){ x[i] -= minx; y[i] -= miny; } int maxx = 0, maxy = 0; REP(i,M){ maxx = max(maxx, x[i]); maxy = max(maxy, y[i]); } int N; cin >> N; if(N > M){ cout << "NO" << endl; return 0; } cout << "YES" << endl; REP(i,N) printf("%d %d\n", x[i], y[i]); return 0; }
J
三つの飲み物の組であって一つが最大の a、他の一つが最大の b、他の一つが最大の c をもつような組を数えるパートが本質的です。これは
(1)
(i, j, k) の組であって a[i] > a[j], a[i] > a[k], b[i] > b[j], b[i] > b[k] をみたすもの
(2)
(i, j, k) の組であって a[i] > a[j], a[i] > a[k], b[i] > b[j], b[i] > b[k], c[i] > c[j], c[i] > c[k] をみたすもの
などの値を足し引きすることによって求められます。
どちらの場合も i を固定して j, k になれるものが何個あるか数えます。
(1) の場合は a でソートした後 BIT でできます。
(2) の場合も分割統治をすれば BIT でできます。
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) typedef long long ll; #define T (1<<17) int tree[T]; void init(void){ int i; REP(i,T) tree[i] = 0; } void add(int pos, int val){ for(int i=pos;i<T;i=((i)|(i+1))) tree[i] += val; } int sum(int pos){ int ans = 0; for(int i=pos;i>0;i=((i)&(i-1))) ans += tree[i-1]; return ans; } int N; int a[100010][3]; int p[100010],q[100010],cnt[100010]; void conquer(int L, int R){ if(R - L == 1) return; int i; int M = (L + R) / 2; vector <pair <int, pair <int, int> > > v(R-L); // p, id, q for(i=L;i<R;i++){ v[i-L].first = p[i]; v[i-L].second.first = i; v[i-L].second.second = q[i]; } sort(v.begin(),v.end()); REP(i,R-L){ int p = v[i].first; int id = v[i].second.first; int q = v[i].second.second; if(id < M){ add(q, 1); } else { cnt[id] += sum(q); } } for(i=L;i<M;i++) add(q[i], -1); conquer(L, M); conquer(M, R); } ll func(int id){ int i; REP(i,N) p[a[i][(id+1)%3]] = a[i][(id+2)%3]; init(); ll ans = 0; REP(i,N){ ll tmp = sum(p[i]); ans += tmp * (tmp - 1) / 2; add(p[i], 1); } return ans; } int main(void){ int i,j; cin >> N; REP(i,N) REP(j,3){ scanf("%d", &a[i][j]); a[i][j]--; } ll ans = N + (ll)N * (N-1) / 2 + (ll)N * (N-1) * (N-2) / 6; REP(i,3) ans -= func(i); REP(i,N){ p[a[i][0]] = a[i][1]; q[a[i][0]] = a[i][2]; } init(); conquer(0, N); REP(i,N){ ans -= cnt[i]; ans += (ll)cnt[i] * (cnt[i] - 1); } cout << ans << endl; return 0; }