A - Shuffled Equation
O(logN)
配列Aをソートして、
A[i] * A[i+1] == A[i+2]
を判定します。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N = 3;
vector<int> A(N);
rep(i, N) cin >> A[i];
sort(A.begin(), A.end());
if(A[0] * A[1] == A[2]){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
B - Who is Missing?
O(NM)
配列Aをソートしましょう。
1~N+1までループAをします。
ループA内で1~MまでループBをします。
i == A[j]
の判定が一つでもtrueの時、Aの要素として含まれているので出力結果に含めない。
出力結果の要素の数は、N - A.size()です。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N, M;
cin >> N >> M;
vector<int> A(M);
rep(i, M) cin >> A[i];
sort(A.begin(), A.end());
cout << N - A.size() << endl;
repx(i, 1, N+1){
int ok = 1;
rep(j, M) if(i == A[j]) ok = 0;
if(ok) cout << i << " ";
}
cout << endl;
return 0;
}
C - Bib
O(P)
配列Pと配列Qの間を補完する配列を用意しましょう。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N;
cin >> N;
vector<int> P(N), Q(N), mid(N);
rep(i, N) cin >> P[i], P[i]--;
rep(i, N) cin >> Q[i], Q[i]--;
rep(i, N) mid[Q[i]] = i;
rep(i, N) cout << Q[P[mid[i]]] + 1 << " ";
cout << endl;
return 0;
}
D - Doubles
O(N*N*K_i)
100*100*100000=10^9
もしかして全探索で間に合うのでは？というのがスタート地点でした。
２つのサイコロを判定するためにO(N^2)のループをしましょう。
i, jの変数を使用したループとして、
jの目の種類を個数を連想配列mpへ探索しましょう。
A_iの目の要素をmpのキーとして探索し、個数の合計cntを求めます。
ans = max(ans, (double)cnt/(double)(K[i]*K[j]));
にて、「2つのサイコロの出目が等しくなる確率の最大値」を求めることができます。
少数8桁は、
fixed << setprecision((n))
で求めることができます。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N;
cin >> N;
vector<vector<ll>> A;
vector<ll> K(N);
rep(i, N){
cin >> K[i];
A.push_back(vector<ll>(K[i]));
rep(j, K[i]){
cin >> A[i][j];
}
}
double ans = 0.0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
map<ll, ll> mp;
int M = A[j].size();
for(int k=0; k<M; k++) mp[A[j][k]]++;
ll cnt = 0;
for(auto a:A[i]){
if(mp.find(a) != mp.end()) cnt+=mp[a];
}
ans = max(ans, (double)cnt/(double)(K[i]*K[j]));
}
}
cout << fixed_setprecision(8) << ans << endl;
return 0;
}
E - Cables and Servers
勉強中
C++