ABC030を解いてみた

abc030.contest.atcoder.jp

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;
}