https://ferin-tech.hatenablog.com/entry/2016/12/15/220606

abc026.contest.atcoder.jp

A問題

　x=1からx=a-1まで全探索で実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int a, ret = 0, maxret = -1;
  cin >> a;

  for(int x=1; x<a; x++) {
    ret = x*(a-x);
    maxret = max(maxret, ret);
  }

  cout << maxret << endl;

  return 0;
}

B問題

　外から奇数番目の円を足して、偶数番目の円を引く包除原理っぽい感じで解きました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 1000
#define PI 3.1415926535

int main(void)
{
  int n, ans = 0;
  vector<int> r;
  //入力
  cin >> n;
  for(int i=0; i<n; i++) {
    int temp;
    cin >> temp;
    r.push_back(temp);
  }

  //包除原理（？）
  sort(r.begin(), r.end(), greater<int>());
  for(int i=0; i<n; i++) {
    int sign = (i%2 ? -1: 1);
    ans += sign * r[i] * r[i];
  }

  cout << setprecision(11) << ans * PI << endl;

  return 0;
}

C問題

　深さ優先探索で全探索しました。N<=20なので実行時間は余裕ありそうな設定になってそう。配列の境界の扱いを間違えて一回WA出したのは気をつけたいです。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 20
#define INF 1e9

int n, lis[MAX_N][MAX_N], dp[MAX_N];

//社員numberの給料を返す
int dfs(int number){
  vector<int> subordinate;
  //直属の部下の番号
  for(int i=0; i<n; i++) if(lis[number][i] == 1) subordinate.push_back(i);
  //直属の部下がいなければ給料は１
  if(subordinate.empty()) return dp[number] = 1;

  int maxret = -INF, minret = INF;
  for(int i=0; i<subordinate.size(); i++) {
    maxret = max(maxret, dfs(subordinate[i]));
    minret = min(minret, dfs(subordinate[i]));
  }

  return dp[number] = maxret + minret + 1;
}

int main(void)
{
  cin >> n;
  if(n == 1) {
    cout << "1" << endl;
    return 0;
  }
  memset(lis, 0, sizeof(lis));
  //入力　隣接行列にする
  for(int i=1; i<n; i++) {
    int temp;
    cin >> temp;
    lis[temp-1][i] = 1;
  }

  int ans = dfs(0);
  //for(int i=0; i<n; i++) cout << "i:" << i << " dp:" << dp[i] << endl;
  cout << ans << endl;

  return 0;
}

D問題

　直線とsin波を足し合わせたグラフになるので、上下に振れながら大きくなっていくグラフになります。答えが小数になる関数の探索なので２分探索かなと目処を立てて実装しました。最小のtを求めるコードを書きましたが最小に限定されてなかったに解き終わった後で気づきました…

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define PI 3.14159265359

double a, b, c;

// f(x)
double f(double t) {
  return a*t + b*sin(c*t*PI);
}

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

  //一周期ごとに区切って
  double left = 1/(2*c), right = 5/(2*c);
  for(right=5/(2*c); right<110; right += (2/c)) {
    if(f(right) >= 100) break;
    left = right;
  }

  //二分探索
  while(abs(f(left)-100) > 0.000001) {
    double mid = (left+right)/2;
    double fmid = f(mid);
    if( fmid > 100) {
      right = mid;
    } else if( fmid < 100) {
      left = mid;
    }
  }

  cout << fixed << setprecision(15) << left << endl;

  return 0;
}