ABC022を解いてみた
A問題
N日目のとき、適正体重かどうかを判定しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { int n=0, s=0, t=0, w=0, a[1000], ans=0; cin >> n >> s >> t; cin >> w; for(int i=1; i<n; ++i) cin >> a[i]; if(s <= w && w <= t) ++ans; for(int i=1; i<n; ++i) { w += a[i]; if(s <= w && w <= t) ++ans; } cout << ans << endl; return 0; }
B問題
たどった花の種類別に数を数えて2個以上になった種類は、その数-1が受粉するという方針で実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 100000 int main(void) { int n=0, a=0, lis[MAX_N]={}, ans=0; cin >> n; for(int i=0; i<n; ++i) { cin >> a; lis[a-1] += 1; } for(int i=0; i<MAX_N; ++i) { //if(i < 30) cout << "lis: " << lis[i] << endl; if(lis[i] >= 2) ans += (lis[i]-1); } cout << ans << endl; return 0; }
C問題
もっとも短い経路の閉路を探すアルゴリズムが思いつかなかったので解説見て実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 999999999 #define MAX_N 300 int main(void) { //lis1が1に隣接する頂点へのコスト int n, m, u, v, l, d[MAX_N][MAX_N]={}, lis1[MAX_N]={}, ret = 0, minret = INF; //lisが1に隣接する頂点番号のリスト vector<int> lis; bool flag = true; // dの初期化 fill( d[0], d[MAX_N], INF); for(int i=1; i<MAX_N; ++i) d[i][i] = 0; //入力 cin >> n >> m; for(int i=0; i<m; ++i) { cin >> u >> v >> l; if(u != 1 && v != 1) {d[u-1][v-1] = l; d[v-1][u-1] = l;} else if(u == 1) {lis1[v-1] = l; lis.push_back(v);} else {lis1[u-1] = l; lis.push_back(u);} } //ワーシャルフロイド // d[i][j] で頂点iから頂点jへの最短距離 for(int k=0; k<n; ++k) { for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } // lis の中から2つを選択 for(int i=0; i < lis.size()-1; ++i) { for(int j=i+1; j < lis.size(); ++j) { ret = lis1[lis[i]-1] + lis1[lis[j]-1] + d[lis[i]-1][lis[j]-1]; //cout << "lis[i]:" << lis[i]-1 << " lis[j]:" << lis[j]-1 << " lis1[lis[i]]" << lis1[lis[i]-1] << " lis1[lis[j]]" << lis1[lis[j]-1] << " d" << d[lis[i]-1][lis[j]-1] << " ret:" << ret << endl; minret = min(minret, ret); } } //たどり着けるパターンがなかったら-1を出力 if(minret == INF) minret = -1; cout << minret << endl; return 0; }
D問題
回転行列を使ってやるのかなとか考えてても実装方法が思い浮かばなかったので、解説見て実装しました。N点の重心と最遠点の比率による方法をつかいました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 100000 int main(void) { int n, ax[MAX_N], ay[MAX_N], bx[MAX_N], by[MAX_N]; double agx=0.0, agy=0.0, bgx=0.0, bgy=0.0, adist=0.0, bdist=0.0, maxadist=0.0, maxbdist=0.0; cin >> n; for(int i=0; i<n; i++) cin >> ax[i] >> ay[i]; for(int i=0; i<n; i++) cin >> bx[i] >> by[i]; for(int i=0; i<n; i++) { agx += ax[i]; agy += ay[i]; bgx += bx[i]; bgy += by[i]; } agx /= n; agy /= n; bgx /= n; bgy /= n; //cout << agx << " " << agy << " " << bgx << " " << bgy << endl; for(int i=0; i<n; i++) { adist = pow(ax[i] - agx, 2) + pow(ay[i] - agy, 2); maxadist = max(maxadist, adist); bdist = pow(bx[i] - bgx, 2) + pow(by[i] - bgy, 2); maxbdist = max(maxbdist, bdist); } //cout << "maxa:" << maxadist << " maxb:" << maxbdist << endl; cout << setprecision(12) << sqrt(maxbdist)/sqrt(maxadist) << endl; return 0; }