ABC024を解いてみた
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; }