ABC030を解いてみた
A問題
if文で比較しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { double a, b, c, d; cin >> a >> b >> c >> d; if(b/a > d/c) cout << "TAKAHASHI" << endl; else if(b/a < d/c) cout << "AOKI" << endl; else cout << "DRAW" << endl; return 0; }
B問題
短針が5分刻み以外にも移動することと小さい方の角度を取得することに気をつけて実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 int main(void) { int n, m; cin >> n >> m; n %= 12; double angle = abs(n*30 + m*0.5 - m*6); angle = min(angle, 360-angle); cout << fixed << setprecision(6) << angle << endl; return 0; }
C問題
乗れる中で最も早い飛行機に乗る貪欲で解きました。計算量はO(n)のはずです。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 #define N_MAX 100000 #define M_MAX 100000 int main(void) { int n, m, x, y; cin >> n >> m; cin >> x >> y; ll a[N_MAX], b[M_MAX]; for(int i=0; i<n; i++) {cin >> a[i];} for(int i=0; i<m; i++) cin >> b[i]; // true ならAにいる bool isA = true; int ans=0, i=0, j=0; ll now=0; while(i < n && j < m) { if(isA) { // a[i]がnow以上になるまで while(a[i] < now) { i++; //乗れる飛行機がもうない if(i == n) {cout << ans << endl; return 0;} } now = a[i] + x; isA = false; } else { // b[j]がnow以上になるまで while(b[j] < now) { j++; // 乗れる飛行機がもうない if(j == m) {cout << ans << endl; return 0;} } now = b[j] + y; ans++; isA = true; } } return 0; }
D問題
10^10000ってlong longでも受け取れないしどうするんだ…?とか思って分からなかったので自力では部分点まで実装。
//部分点 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 #define MAX_N 100000 int main(void) { int n, a, b[MAX_N]; ll k; cin >> n >> a; a--; cin >> k; for(int i=0; i<n; i++) {cin >> b[i]; b[i]--;} //ループに入るまで bool toLoop[MAX_N] = {false}; int c_num = a, toLoop_num = 0; vector<int> v_toLoop; while(true) { toLoop[c_num] = true; toLoop_num++; v_toLoop.push_back(c_num); c_num = b[c_num]; if(toLoop[c_num]) break; //cout << "toLoop_num:" << toLoop_num << " c_num:" << c_num << endl; } //ループ中 bool loop[MAX_N]; int loop_num = 0; vector<int> v; while(true) { loop[c_num] = true; loop_num++; v.push_back(c_num); c_num = b[c_num]; if(loop[c_num]) break; //cout << "loop_num:" << loop_num << " c_num:" << c_num << endl; } if(toLoop_num > k) cout << v_toLoop[k]+1 << endl; else cout << v[(k-toLoop_num)%loop_num]+1 << endl; return 0; }
string型で入力を受け取って、桁ごとに計算することでMODを計算できる(by解説)で実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 #define MAX_N 100000 int main(void) { int n, a, b[MAX_N]; string k; cin >> n >> a; a--; cin >> k; for(int i=0; i<n; i++) {cin >> b[i]; b[i]--;} //ループに入るまで bool toLoop[MAX_N] = {false}; int c_num = a, toLoop_num = 0; vector<int> v_toLoop; while(true) { toLoop[c_num] = true; toLoop_num++; v_toLoop.push_back(c_num); c_num = b[c_num]; if(toLoop[c_num]) break; //cout << "toLoop_num:" << toLoop_num << " c_num:" << c_num << endl; } //ループ中 bool loop[MAX_N]; int loop_num = 0; vector<int> v; while(true) { loop[c_num] = true; loop_num++; v.push_back(c_num); c_num = b[c_num]; if(loop[c_num]) break; //cout << "loop_num:" << loop_num << " c_num:" << c_num << endl; } /* cout << "loop_num:" << loop_num << " toLoop_num:" << toLoop_num << endl; for(int i=0; i<toLoop_num; i++) cout << v_toLoop[i] << " "; cout << endl; for(int i=0; i<loop_num; i++) cout << v[i] << " "; cout << endl; */ //kが6桁あればn<=10^5だし閉路に入る気がした if(k.size() < 7) { int num_k = stoi(k); int c_num = a; for(int i=0; i<num_k; i++) c_num = b[c_num]; cout << c_num + 1 << endl; return 0; } ll k_mod_c = 0; for(int i=0; i<k.size(); i++) k_mod_c = (k_mod_c*10+k[i]-'0')%loop_num; while(k_mod_c < toLoop_num) k_mod_c += loop_num; c_num = a; for(int i=0; i<k_mod_c; i++) c_num = b[c_num]; cout << c_num+1 << endl; return 0; }