活動日記 day 31
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
A - 加算王
文字列として入力を受け取り、１桁目と２桁目の和を出力します。
コード :
#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; }
