活動日記 day 36
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
活動日記 day 35
活動内容 :
部活動紹介
コンテスト (チーム戦)
コンテスト : Virtual Arena: Room 3408
A - Water Rate
#include <iostream> #include <algorithm> using namespace std; int A = 0, B = 0; int C = 0, D = 0; int P = 0; int main(void){ cin >> A; cin >> B; cin >> C; cin >> D; cin >> P; int x = A * P; int y = (P <= C) ? B : B + D*(P-C); cout << min(x,y) << endl; }
B - Christmas Party
#include <iostream> #include <vector> using namespace std; int N = 0; int M = 0; int main(void){ cin >> N; cin >> M; vector<int> A(M, 0); vector<int> P(N, 0); int target = 0; int count = 0; int x = 0; int z = 0; for(int i=0; i<M; ++i){ cin >> A[i]; } for(int i=0; i<M; ++i){ target = A[i]; count = 0; for(int j=0; j<N; ++j){ cin >> x; if(x == target){ P[j] += 1; count++; } } P[target - 1] += (N - count); } for(int i=0; i<N; ++i){ cout << P[i] << endl; } }
C - Weather Forecaster
#include<iostream> using namespace std; int main(){ //scanf("%d",&n); int h,w; cin>>h>>w; char cloud[h][w]; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ cin>>cloud[i][j]; } } for(int i = 0; i < h; i++){ int j=0; while(cloud[i][j] != 'c'&&j<w){ cout << -1; j++; if(j<w){ cout<<" "; } } int count = 0; while(j<w){ if(cloud[i][j] == 'c'){ //int count = 0; count=0; cout<<count; } else{ count++; cout<<count; } j++; if(j<w){ cout<<" "; } } cout << endl; } //input finish return 0; }
D - Silk Road
#include <iostream> #include <algorithm> #include <climits> using namespace std; int N = 0, M = 0; int D[1000] = {0}; int C[1000] = {0}; int memo[1001][1001]; long dp(int i, int j){ if(memo[i][j] != -1){ return memo[i][j]; } if(j > M){ return memo[i][j] = INT_MAX; } if(i == N){ return memo[i][j] = 0; } long x = dp(i, j+1); long y = dp(i+1, j+1); if(x == INT_MAX && y == INT_MAX){ return memo[i][j] = INT_MAX; }else if(x == INT_MAX){ return memo[i][j] = C[j] * D[i] + y; }else if(y == INT_MAX){ return memo[i][j] = x; }else{ return memo[i][j] = min(x, C[j] * D[i] + y); } } int main(void){ fill(memo[0],memo[1000], -1); cin >> N >> M; for(int i=0; i<N; ++i){ cin >> D[i]; } for(int j=0; j<M; ++j){ cin >> C[j]; } cout << dp(0, 0) << endl; }
E - 3-Primes Problem
#include <iostream> #include <climits> #include <vector> using namespace std; int main() { int prime[1000]; for(int i=0;i<1000;i++){ prime[i]=1; } prime[0] = 0;// 1 is not prime for (int i = 0; i < 1000; i++) { if (prime[i] == 1) { //cout<<"hogehoge"<<endl; for (int j = (i + 1); (i + 1) * j <= 1000; j++) { prime[(i + 1) * j - 1] = 0; } } } int count = 0; for(int i = 0; i < 1000; i++){ if(prime[i] == 1){ count++; } } int number[count], n = 0; for(int i = 0; i < 1000; i++){ if(prime[i] == 1){ number[n] = i + 1; n++; } } int t=0; cin>>t; vector<int> a(t, 0); for(int i=0;i<t;i++){ cin>>a[i]; } for(int i=0;i<t;i++){ for(int j = 0; j < count; j++){ for(int k = 0; k < count; k++){ for(int l = 0; l < count; l++){ if(a[i] == number[j] + number[k] + number[l]){ cout << number[j] << " " << number[k] << " " << number[l] << endl; goto LABEL; } } } } LABEL: continue; } return 0; }
活動日記 day 34
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
A - 25個の文字列
N-1を5で割った商と余りを1文字目と2文字目のインデックスに指定すれば解くことができます。
(全列挙したものをソートしても解くことは可能です。)
#include <iostream> using namespace std; int main() { string S; int N; cin >> S >> N; cout << S[(N - 1) / 5] << S[(N - 1) % 5] << endl; return 0; }
B - 双子とスイカ割り
1行ずつシミュレートしましょう。
#include <iostream> using namespace std; int main() { int N, A, B; cin >> N >> A >> B; int sum = 0; for(int i = 0; i < N; i++){ string s; int d; cin >> s >> d; if(d < A) d = A; else if(d > B) d = B; if(s == "West") sum += d; else sum -= d; } if(sum == 0) cout << 0 << endl; else if(sum > 0) cout << "West " << sum << endl; else cout << "East " << -sum << endl; return 0; }
C - 双子と○×ゲーム
未定
D - 25個の整数
未定
E - ウサギとカメ
未定
活動日記 day 33
活動内容 :
コンテスト (チーム戦)
コンテスト : Virtual Arena: Room 3394
A - Selection of Participants of an Experiment
全探索で解けます。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cassert> #include<cstring> #include<climits> #include<sstream> #include<deque> #include<vector> #include<algorithm> #include<set> #include<map> #include<bitset> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int a[1001]={0}; int main() { int n; while(scanf("%d",&n),n!=0){ for(int i=0;i<n;++i){ scanf("%d ",&a[i]); } int minimum = INT_MAX; for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if(abs(a[i] - a[j]) < minimum)minimum = abs(a[i] - a[j]); } } printf("%d\n",minimum); } return 0; }
B - Look for the Winner!
入力を捨てるのを忘れないようにしましょう。
#include <iostream> #include <stdio.h> using namespace std; int main() { while (true) { LABEL: int array[30] = {0}; int n; int top = 0; int topalpha = 0; int next = 0; int nextalpha = 0; int amari = 0; cin >> n; if (n == 0) { return 0; } char temp; for (int i = 0; i < n; i++) { cin >> temp; temp = temp - 65; array[temp]++; //top sagashi for (int j = 0; j < 30; j++) { if (top < array[j]) { top = array[j]; topalpha = j; } } //2nd sagashi for (int j = 0; j < 30; j++) { if (next < array[j] && j != topalpha) { next = array[j]; nextalpha = j; } } amari = n - i - 1; char hoge; if (top <= next + amari) { //mada wakaran continue; } else { //win top or tie if (top == next) { cout << "TIE" << endl; for (int j = 0; j < amari; j++) { cin >> hoge; } goto LABEL; } else { printf("%c ", 65 + topalpha); printf("%d\n", i + 1); for (int j = 0; j < amari; j++) { cin >> hoge; } goto LABEL; } } } printf("TIE\n"); } return 0; }
E - Arithmetical CAPTCHA
全探索です。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cassert> #include<cstring> #include<climits> #include<sstream> #include<deque> #include<vector> #include<algorithm> #include<set> #include<map> #include<bitset> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int n[5]; char op[] = {'+','-','='}; bool check(deque<char> &ops) { bool found = false; rep(i,3) if( ops[i] == '=' ) { found = true; break; } if( !found ) return false; set<int> S; int v = n[0]; rep(i,3) { if( ops[i] == '+' ) { v += n[i+1]; } else if( ops[i] == '-' ) { v -= n[i+1]; } else { S.insert(v); v = n[i+1]; } } S.insert(v); return S.size() == 1; } bool dfs(int cur,deque<char> &deq) { if( cur >= 3 ) { return check(deq); } rep(i,3) { deq.push_back(op[i]); if( dfs(cur+1,deq) ) return true; deq.pop_back(); } return false; } void compute() { deque<char> deq; assert( dfs(0,deq) ); cout << n[0] << " "; rep(i,3) { cout << deq[i] << " " << n[i+1]; if( i != 2 ) cout << " "; } puts(""); } int main() { int T,CNT=1; cin >> T; while( T-- ) { cout << "Case #" << CNT++ << ": "; rep(i,4) cin >> n[i]; compute(); } return 0; }
コメント:
蟻本を読んでSG定理を復習しようと思います。
活動日記 day 32
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
A - 動物園
問題文中にある通りに実装します
def main(): A,B,C,K = map(int,input().split()) S,T = map(int,input().split()) ans = S * A + T * B if S + T >= K: ans -= (S+T) * C print(ans) if __name__ == "__main__": main()
B - 自動ドア
1秒ごとにシミュレーションすると間に合わないので、
イベント点のみのシミュレートし答えを計算します
import sys def main(): N,T = map(int,input().split()) A = [int(input()) for _ in range(N)] ans,pre = 0, 0 for v in A: if pre < v: ans += T pre = v + T else: ans += ( v + T - pre ) pre = v + T print(ans) if __name__ == "__main__": main()
C - 民族大移動
未来
D - 動的計画法
未来
C - だれじゃ
未来
活動日記 day 31
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
A - 加算王
文字列として入力を受け取り、1桁目と2桁目の和を出力します。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int main() { string s; cin >> s; cout << ( s[0] - '0' + s[1]- '0' ) << endl; return 0; }
B - 手芸王
あらかじめ100以下のアクセサリーを作成し、連想配列等にそのアクセサリーの情報を保持しておきます。
入力で与えられた文字列が連想配列内に存在すれば、その値を出力します。
無ければ-1です。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int main() { string s = "b"; map<string,int> mp; mp[s] = 0; REP(n,1,110) { if( n % 3 == 0 ) { s = "b" + s + "b"; mp[s] = n; } else if( n % 3 == 1 ) { s = "a" + s + "c"; mp[s] = n; } else { s = "c" + s + "a"; mp[s] = n; } } int n; cin >> n; cin >> s; if( mp.count(s) ) { cout << mp[s] << endl; } else { cout << -1 << endl; } return 0; }
C - 収集王
まず各行と各列ごとに、飴の出現回数を数えます。
次に行iについて、K - (行iの飴の出現回数) 個 だけ飴が出現している列の数を数えます。
その際に、行iに含まれる飴の出現回数は各列の飴の出現回数から引いておく必要があります。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; #define MAX 100100 int R,C,K,N,r[100100],c[100100]; ll cR[MAX],cC[MAX]; deque<int> deq[MAX]; map<int,ll> mR,mC; void compute() { rep(i,R) ++mR[cR[i]]; rep(i,C) ++mC[cC[i]]; long long ans = 0; rep(i,C) { int v1 = cC[i]; int v2 = K - v1; if( v2 < 0 ) continue; rep(j,(int)deq[i].size()) { int dex = deq[i][j]; int v = cR[r[dex]]; --mR[v]; ++mR[v-1]; } ans += (ll)mR[v2]; rep(j,(int)deq[i].size()) { int dex = deq[i][j]; int v = cR[r[dex]]; ++mR[v]; --mR[v-1]; } } cout << ans << endl; } int main() { cin >> R >> C >> K; cin >> N; rep(i,N) { cin >> r[i] >> c[i]; --r[i], --c[i]; deq[c[i]].push_back(i); ++cR[r[i]]; ++cC[c[i]]; } compute(); return 0; }
D - 射撃王
答えとなる値を二分探索で決め打ちします。
つまり、全ての風船を破壊した際に発生するペナルティの最大値 x を二分探索で決めます。
x が決まれば、各風船をペナルティがx以下になるような時間で破壊できるかどうか判定ができます。
(各風船iについて H[i] + ti * S[i] <= x となるような ti の最大値を求め、それらの風船をti以下の時間帯で割ることができるかどうか判定すれば良いです )
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; #define MAX 100100 int N; long long H[MAX], S[MAX]; bool check(ll maxi) { map<ll,int> cnt; rep(i,N) { if( H[i] > maxi ) return false; ll t = ( maxi - H[i] ) / S[i]; ++cnt[t]; } ll sum = 0; for(auto v : cnt) { sum += (ll)v.second; if( sum > v.first + 1 ) return false; } return true; } int main() { cin >> N; rep(i,N) cin >> H[i] >> S[i]; // 最小をもとめる ll L = 0, R = LLONG_MAX-10LL; while( L + 1 < R ){ ll M = ( L + R ) / 2; assert( M >= 0LL ); if( check(M) ) R = M; else L = M; } if( check(L) ) cout << L << endl; else if( check((L+R)/2) ) cout << (ll)((L+R)/2) << endl; else cout << R << endl; return 0; }
E - タコヤ木
- 1が連続していくる区間ごとに、それを満たすような割り当てが何通りあるのかを考えます。
(各区間について組み合わせの数を求めれば、それらを掛け合わせたものが最終的な組み合わせの数になります)
つまり、a -1 -1 ... -1 bのような区間について、何通りの割りあてがあるのかを考えます。
さて、問題の見方を少し変えてみると次のような問題になります。
0以上の整数であるc個の変数の総和がb - a以下になる組み合わせは何通りか?
これは重複組み合わせで求めることができるので、求めましょう。
(例) 2 -1 -1 9 について考える。
これは2個の変数の総和が7以下になるような組み合わせを求める問題として考えることができる。
そのような組み合わせの数は
7+2C2 = 36
O O O O O O O の間に | | を入れるアレ
その際には逆元を求める必要があります。
ちなみに80点まではよくある式を少しいじるタイプのDPでとけます。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; #define MAX 2010 ll mod = 1000000007; long long extgcd(long long a,long long b,long long& x,long long& y) { long long d = a; if(b != 0) { d = extgcd(b,a%b,y,x); y -= (a/b)*x; } else x = 1,y = 0; return d; } long long mod_inv(long long a,long long m) { long long x,y; extgcd(a,m,x,y); return (m+x%m)%m; } int N,A[MAX]; void compute() { vector<int> vec,num; rep(i,N) if( A[i] != -1 ) { vec.push_back(A[i]); int cur = i + 1; while( cur < N && A[cur] == -1 ) ++cur; num.push_back(cur-i-1); } long long ans = 1; rep(i,(int)vec.size()-1) { int a = vec[i+1] - vec[i]; int b = num[i]; long long denom = 1, numer = 1; REP(j,1,b+1) { ( denom *= ( (ll)( a + b - ( j - 1 ) ) % mod ) ) %= mod; ( numer *= (ll)j ) %= mod; } ( ans *= ( ( denom * mod_inv(numer,mod) ) % mod ) ) %= mod; } cout << ans << endl; } int main() { cin >> N; rep(i,N) cin >> A[i]; compute(); return 0; }
おまけ (80点をとるためのDPコード)
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; #define MAX 2010 ll mod = 1000000007; int N,A[MAX], pre[MAX],nex[MAX]; long long dp[MAX][2100]; void compute() { nex[0] = A[0], nex[N-1] = A[N-1]; pre[0] = A[0], pre[N-1] = A[N-1]; for(int i=N-2;i>=1;--i) { if( A[i] == -1 ) nex[i] = nex[i+1]; else nex[i] = A[i]; } REP(i,1,N-1) { if( A[i] != -1 ) pre[i] = A[i]; else pre[i] = pre[i-1]; } dp[0][A[0]] = 1; REP(i,1,N) { REP(j,1,nex[i]+1) { dp[i][j] = ( dp[i][j-1] + dp[i-1][j] ) % mod; } rep(j,pre[i]) dp[i][j] = 0; } cout << dp[N-1][A[N-1]] << endl; } int main() { cin >> N; rep(i,N) cin >> A[i]; compute(); return 0; }
活動日記 day 30
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
A - Best Body
実際にN日間の第10の変化を計算してベストボディーである日を数えます。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int n,s,t; int w; int main() { int cnt = 0; cin >> n >> s >> t; cin >> w; int cur = w; if( s <= cur && cur <= t ) ++cnt; rep(i,n-1) { int a; cin >> a; cur = cur + a; if( s <= cur && cur <= t ) ++cnt; } cout << cnt << endl; return 0; }
B - Bumble Bee
i番目より前に訪れた花の種類を配列等で保持し、i番目の花の種類がすでに存在するかどうかを判定します。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int n, A[100010]; bool found[100010]; int main() { cin >> n; int cnt = 0; rep(i,n) { cin >> A[i]; if( found[A[i]] ) ++cnt; found[A[i]] = true; } cout << cnt << endl; return 0; }
C - Blue Bird
答えとなる閉路は家1を端点に持つ辺をちょうど2本含みます。
そのため、家1から出ている辺を全て取り除いた状態のグラフの全点間の最短経路をワーシャルフロイドやdijkstraで求めた後に
どの2つの辺を答えとなる閉路に含めるか全パターン試します。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; struct Edge { int t,v; }; struct Data { int cur, c; bool operator < ( const Data & data ) const { if( c != data.c ) return c > data.c; return cur < data.cur; } }; int V,E; vector<Edge> G[400]; vector<int> ID[400]; int mini[400]; int dijkstra(int e) { rep(i,V) mini[i] = INT_MAX; int dst = G[0][e].t; if( dst == 0 ) return INT_MAX; mini[0] = 0; priority_queue<Data> Q; Q.push((Data){0,0}); while(!Q.empty()) { Data d = Q.top(); Q.pop(); if( d.cur == dst ) return d.c + G[0][e].v; rep(i,(int)G[d.cur].size()) { int nex = G[d.cur][i].t; if( ID[d.cur][i] == ID[0][e] ) continue; if( mini[nex] > d.c + G[d.cur][i].v ) { mini[nex] = d.c + G[d.cur][i].v; Q.push((Data){nex,mini[nex]}); } } } return INT_MAX; } void compute() { int ans = INT_MAX; rep(i,(int)G[0].size()) { ans = min(ans,dijkstra(i)); } if( ans == INT_MAX ) puts("-1"); else cout << ans << endl; } int main() { cin >> V >> E; rep(i,E) { int s,t,v; cin >> s >> t >> v; --s, --t; G[s].push_back((Edge){t,v}); G[t].push_back((Edge){s,v}); ID[s].push_back(i); ID[t].push_back(i); } compute(); return 0; }
D - Big Bang
問題文中の処理を行ったとしても、その点集合において変化しない情報について考えます。
例えば、最も近い2点は処理後も変化しません。
そのため、処理前と処理後の最も近い2点間の距離を求め、処理後の距離で処理前の距離を割ればPが求まります。
その他にも、点集合の凸包をとってできた凸多角形の重心と各点との距離からもPを求めることができます。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) #define EPS (1e-8) #define equals(a,b) (fabs((a)-(b))<EPS) using namespace std; struct Point { int x,y; bool operator < ( const Point &p ) const { if( x != p.x ) return x < p.x; return y < p.y; } }; #define MAX 100010 bool cmp_y(const Point &a,const Point &b) { return a.y < b.y; } //#define pow2(x) ((x)*(x)) //double mydist(Point a,Point b) { return sqrt(pow2(a.x-b.x)+pow2(a.y-b.y)); } double mydist(Point a,Point b) { //double dx = ((a.x - b.x)*(a.x-b.x)); //double dy = ((a.y - b.y)*(a.y-b.y)); double dx = (a.x - b.x); double dy = (a.y - b.y); dx = dx * dx; dy = dy * dy; return sqrt(dx+dy); //return sqrt(dx+dy); } double closest_pair(Point *ps,int n) { if( n <= 1 ) return INT_MAX; int m = n / 2; double x = ps[m].x; double d = min(closest_pair(ps,m),closest_pair(ps+m,n-m)); inplace_merge(ps,ps+m,ps+n,cmp_y); vector<Point> vec; rep(i,n) { if( fabs(x-ps[i].x) >= d ) continue; for(int j=(int)vec.size()-1;j>=0;--j) { double dy = fabs(ps[i].y-vec[j].y); if( dy >= d ) break; d = min(d,mydist(ps[i],vec[j])); } vec.push_back(ps[i]); } return d; } int n; Point A[MAX], B[MAX]; void compute() { sort(A,A+n); double mini1 = closest_pair(&A[0],n); sort(B,B+n); double mini2 = closest_pair(&B[0],n); printf("%.10f\n",mini2/mini1); } int main() { cin >> n; rep(i,n) cin >> A[i].x >> A[i].y; rep(i,n) cin >> B[i].x >> B[i].y; compute(); return 0; }
E - ロミオとジュリエット
木の直径を求めれば良いです。
木の直径の求め方はday 27のセットにも出ましたね。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; #define MAX_V 100010 int V; vector<int> G[MAX_V]; typedef pair<int,int> ii; ii visit(int p,int v) { ii r(0,v); rep(i,(int)G[v].size()) { int e = G[v][i]; if(e != p) { ii t = visit(v,e); t.first += 1; if(r.first < t.first) r = t; } } return r; } int diameter() { ii r = visit(-1,0); ii t = visit(-1,r.second); cout << r.second + 1 << " " << t.second + 1 << endl; return t.first; } int main() { cin >> V; rep(i,V-1) { int s,t; cin >> s >> t; --s, --t; G[s].push_back(t); G[t].push_back(s); } diameter(); return 0; }