ABC027を解いてみた

abc027.contest.atcoder.jp

A問題

　長方形は向かい合っている辺の長さが等しいです。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  int a, b, c;
  cin >> a >> b >> c;
  if(a == b) cout << c << endl;
  else if(b == c) cout << a << endl;
  else if(c == a) cout << b << endl;

  return 0;
}

B問題

　一つの島にいるべき人数はわかるので橋より左の島、右の島にいるべき合計人数は求められます。各橋について調べていくO(N)で求められます。accumulateは積極的に使っていきたいです。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define MAX_N 100

// lからrまで足す
int sum(vector<int> v, int l, int r) {
  int ret = 0;
  for(int i=l; i<=r; i++) ret += v[i];
  return ret;
}

int main(void)
{
  int temp, n;
  cin >> n;
  vector<int> a;
  for(int i=0; i<n; i++) {
    cin >> temp;
    a.push_back(temp);
  }
  if(accumulate(a.begin(), a.end(), 0) % n != 0) {cout << -1 << endl; return 0;}
  int num = accumulate(a.begin(), a.end(), 0)/n;

  int ans = 0;
  for(int i=1; i<n; i++) {
    if(sum(a, 0, i-1) != i*num
        || sum(a, i, n-1) != (n-i)*num) {
      ans++;
    }
    //cout << "i:" << i << " left:" << sum(a, 0, i-1) << " right:" << sum(a, i, n-1) << endl;
  }

  cout << ans << endl;

  return 0;
}

C問題

　nimとかgrundy数とかで考えたがわからなかったので解説見て実装しました。木の深さが奇数なら先手は2x+1、後手は2xを選びます。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  ll n;
  cin >> n;

  int depth = 0;
  for(ll i = n; i > 0; i /= 2) depth++;

  // true だったら 先手の番
  int turn = true;
  ll i = 1;
  //cout << "i:" << i << " turn:" << turn << endl;
  while(i <= n) {
    if(depth % 2 == 0) {
      if(turn) i *= 2;
      else i = 2*i+1;
    } else {
      if(turn) i = 2*i+1;
      else i *= 2;
    }
    turn = !turn;
    //cout << "i:" << i << " turn:" << turn << endl;
  }

  if(turn) cout << "Takahashi" << endl;
  else cout << "Aoki" << endl;

  return 0;
}

D問題

　解説見て実装しました。考察力つけたい。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

// lからrまで足す
int sum(vector<int> v, int l, int r) {
  int ret = 0;
  for(int i=l; i<=r; i++) ret += v[i];
  return ret;
}

int main(void)
{
  string s;
  cin >> s;

  vector<int> v;
  int plusnum=0, minusnum=0;
  for(int i=s.size()-1; i>=0; i--) {
    if(s[i] == '+') plusnum++;
    else if(s[i] == '-') minusnum++;
    else v.push_back(plusnum-minusnum);
    //cout << "plus:" << plusnum << " minus:" << minusnum << endl;
  }
  sort(v.begin(), v.end());
  cout << sum(v, v.size()/2, v.size()-1) - sum(v, 0, v.size()/2-1) << endl;

  return 0;
}