ABC 125

A

A - Biscuit Generator

  • B*T/Aが答え
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int A, B, T;
  cin >> A >> B >> T;
  cout << B * (T / A) << endl;
}

Submission #5139315 - AtCoder Beginner Contest 125

B

B - Resale

  • V[i]-C[i] > 0となるV[i]-C[i]の総和
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int N;
  vector<int> V(N), C(N);
  cin >> N;
  REP(i, N) cin >> V[i];
  REP(i, N) cin >> C[i];
 
  int ans = 0;
  REP(i, N) {
    if (V[i] > C[i]) ans += V[i] - C[i];
  }
  cout << ans << endl;
}

Submission #5141279 - AtCoder Beginner Contest 125

C

C - GCD on Blackboard

  • 左端から順・右端から順に最大公約数を取った配列をL[i], R[i]として持っておく
  • 左端を除いた最大公約数はR[1], 右端を除いた最大公約数はL[N-2], 端以外のi番目を除いた最大公約数はgcd(L[i-1], R[i+1])になるので、この中から最大のものを選ぶ
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
 
int main() {
  int N;
  cin >> N;
  vector<int> A(N), L(N), R(N);
  REP(i, N) cin >> A[i];
  L[0] = A[0];
  R[N - 1] = A[N - 1];
  FOR(i, 1, N) {
    L[i] = gcd(L[i - 1], A[i]);
    R[N - 1 - i] = gcd(R[N - i], A[N - 1 - i]);
  }
  ll ans = max(R[1], L[N - 2]);
  FOR(i, 1, N - 1) { ans = max(ans, gcd(L[i - 1], R[i + 1])); }
  cout << ans << endl;
}

D

D - Flipping Signs

  • 相変わらずDが解けない
  • dp[i][0]をiを選んで反転させない場合、dp[i][1]をiを選んで反転させた場合の最大値とする。
  • このときdp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i]), dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])になる。
    • iを選んで操作しないとき、i-1を選んで操作していなかったらiはそのままで、i-1を操作していたらiは反転している。
    • iを選んで操作するとき、i-1を選んで操作していなかったらiは反転していて、i-1を操作していたらiはそのまま。
  • 答えはdp[N][0]（Nを選ぶことはできない）
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int N;
ll dp[100001][2];
 
int main() {
  cin >> N;
  vector<ll> A(N);
  REP(i, N) { cin >> A[i]; }
  dp[0][0] = 0;
  dp[0][1] = numeric_limits<ll>::min() / 2;
  FOR(i, 1, N + 1) {
    dp[i][0] = max(dp[i - 1][0] + A[i - 1], dp[i - 1][1] - A[i - 1]);
    dp[i][1] = max(dp[i - 1][0] - A[i - 1], dp[i - 1][1] + A[i - 1]);
  }
  cout << dp[N][0] << endl;
}

Submission #5163661 - AtCoder Beginner Contest 125