ABC024を解いてみた

abc024.contest.atcoder.jp

A問題

　条件に沿って実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int a, b, c, k, s, t, ans = 0;
  cin >> a >> b >> c >> k;
  cin >> s >> t;

  if(s+t >= k) ans = s*(a-c)+t*(b-c);
  else ans = s*a+t*b;

  cout << ans << endl;

  return 0;
}

B問題

　a[i+1]-a[i]がt未満かどうかで場合分けしました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 100000

int main(void)
{
  int n, t, a[MAX_N], ans=0;

  //入力
  cin >> n >> t;
  for(int i=0; i<n; i++) cin >> a[i];

  for(int i=0; i<n-1; i++) {
    if(a[i+1]-a[i] < t) ans += a[i+1]-a[i];
    else ans += t;
  }
  ans += t;

  //出力
  cout << ans << endl;

  return 0;
}

C問題

　蟻本で見たことがあるような気がしてセグメントツリーを使うのかと考えてもO(NDK)の解法しか思いつかず、解説を見てできるだけ始点から終点に近づく方向に進める貪欲でO(DK)で実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_D 10000
#define MAX_K 100

int main(void)
{
  int n, d, k, l[MAX_D], r[MAX_D], s[MAX_K], t[MAX_K];
  cin >> n >> d >> k;
  for(int i=0; i<d; i++) cin >> l[i] >> r[i];
  for(int i=0; i<k; i++) cin >> s[i] >> t[i];

  for(int i=0; i<k; i++) {
    //今たどり着けるもっとも進んだ頂点
    int now = s[i];
    for(int j=0; j<d; j++) {
      // sからtへ増える方向なら
      if(s[i] <= t[i]) {
        if(l[j] <= now && now <= r[j]) now = r[j];
        if(now >= t[i]) {
          cout << j+1 << endl;
          break;
        }
      // sからtへ減る方向なら
      } else {
        if(l[j] <= now && now <= r[j]) now = l[j];
        if(now <= t[i]) {
          cout << j+1 << endl;
          break;
        }
      }
    }
  }

  return 0;
}

D問題

　解説を見て実装しました。組み合わせの考え方からr, cをA, B, Cで表す。MOD内での計算方法を使ってr, cを計算する。MODで除算はフェルマーの小定理と二分累乗法を使えば高速に計算可能。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

ll binpow(ll x, ll e)
{
  ll a = 1, p = x;
  while(e > 0)
  {
    if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
    else {a = (a*p) % MOD; e--;}
  }

  return a % MOD;
}

int main(void)
{
  ll a, b, c;
  cin >> a >> b >> c;

  ll ab = a*b%MOD, bc = b*c%MOD, ca = c*a%MOD;
  ll c_deno = (ca-bc+ab+MOD)%MOD, r_deno = (ab-bc+ca+MOD)%MOD;
  ll c_deno_inv = binpow(c_deno, MOD-2), r_deno_inv = binpow(r_deno, MOD-2);

  ll _c = ((bc-ab+MOD)*c_deno_inv)%MOD, r = ((bc-ca+MOD)*r_deno_inv+MOD)%MOD;

  cout << r << " " << _c << endl;

  return 0;
}