ABC040を解いてみた

abc040.contest.atcoder.jp

A問題

　n-1とx-nのうち小さい方を出力しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n = 0, x = 0;
  cin >> n >> x;

  if(x-1 >= n-x) cout << n-x << endl;
  else cout << x-1 << endl;
  
  return 0;
}

B問題

　1からsqrt(n)まで四角形の1辺を探索し、もう1辺を求めコストを算出しました。そのうち最小となるコストを出力しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n, j, cost, mincost = 300000;
  cin >> n;

  for(int i = 1; i <= sqrt(n); i++)
  {
    j = n/i;
    cost = abs(i-j) + n - i*j;
    mincost = min(mincost, cost);
  }

  cout << mincost << endl;
  return 0;
}

C問題

　dp[i] = (i番目まで移動するのにかかる最小コスト)　という変数で、DPを行って求めました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 100000

int main(void)
{
  int n, a[MAX_N], dp[MAX_N];

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

  dp[0] = 0;
  dp[1] = abs(a[1]-a[0]);
  for(int i=2; i<n; ++i)
  {
    dp[i] = min(dp[i-1] + abs(a[i]-a[i-1]), dp[i-2] + abs(a[i]-a[i-2]));
  }

  cout << dp[n-1] << endl;

  return 0;
}

D問題

　Union-Find木を知らなかったので蟻本で勉強して出直してきます…