2016-12-16

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;
}

2016-12-15

ABC025を解いてみた

競技プログラミング ABC

abc025.contest.atcoder.jp

A問題

　入力をソートして(n-1)/5文字目、(n-1)%5文字目が答えの文字列になります。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  vector<char> str;
  string ans = "", temp;
  int n;

  cin >> temp;
  cin >> n;
  for(int i=0; i<5; i++) str.push_back(temp[i]);

  sort(str.begin(), str.end());
  ans += str[(n-1)/5];
  ans += str[(n-1)%5];

  cout << ans << endl;

  return 0;
}

B問題

　d[i]がAからBの範囲内かを判定して条件にそってシミュレーションしていきました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 100

int main(void)
{
  int n, a, b, d[MAX_N], now = 0;
  string temp;

  cin >> n >> a >> b;
  for(int i=0; i<n; i++) {
    cin >> temp >> d[i];
    if(d[i] < a) d[i] = a;
    else if(d[i] > b) d[i] = b;
    if(temp == "West") d[i] *= -1;
    now += d[i];
  }

  if(now < 0) cout << "West " << abs(now) << endl;
  else if(now > 0) cout << "East " << now << endl;
  else cout << now << endl;

  return 0;
}

C問題

　解説を読んでminimax法をつかって実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1e9

int a[3][3], b[2][3], c[3][2];

// minimax法
int minimax(int cnt) {
  // 最終盤面の得点を求める
  if(cnt == 9) {
    int result = 0;
    for(int i=0; i<2; i++) {
      for(int j=0; j<3; j++) {
        if(a[i][j] == a[i+1][j]) result += b[i][j];
      }
    }
    for(int i=0; i<3; i++) {
      for(int j=0; j<2; j++) {
        if(a[i][j] == a[i][j+1]) result += c[i][j];
      }
    }
    return result;
  }
  int turn = cnt%2;
  int ret = (turn == 0 ? -INF : INF);

  for(int i=0; i<3; i++) {
    for(int j=0; j<3; j++) {
      //cout << a[i][j] << endl;
      if(a[i][j] == -1) {
        a[i][j] = turn;
        //　どちらのターンかによってmaxかminを変える
        if(turn == 0) {
          ret = max(ret, minimax(cnt+1));
        } else {
          ret = min(ret, minimax(cnt+1));
        }
        a[i][j] = -1;
      }
    }
  }

  return ret;
}

int main(void)
{
  // 入力
  int sum = 0;
  for(int i=0; i<2; i++) {
    for(int j=0; j<3; j++) {
      cin >> b[i][j];
      sum += b[i][j];
    }
  }
  for(int i=0; i<3; i++) {
    for(int j=0; j<2; j++) {
      cin >> c[i][j];
      sum += c[i][j];
    }
  }

  memset(a, -1, sizeof(a));

  //minimax法を実行
  int ans = minimax(0);
  cout << ans << endl;
  cout << sum - ans << endl;

  return 0;
}

D問題

　ビットDPの実装で詰まったのでできたら追記します…

2016-12-15

ABC026を解いてみた

ABC 競技プログラミング

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;
}

2016-12-13

ABC024を解いてみた

ABC 競技プログラミング

abc024.contest.atcoder.jp

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;
}

2016-12-13

ABC049を解いてみた

ABC 競技プログラミング

abc049.contest.atcoder.jp

A問題

　入力がa, i, u, e, oならvowel、そうでなければconsonantを出力しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

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

  if(str == "a" || str == "i" || str == "u" || str == "e" || str == "o")
    cout << "vowel" << endl;
  else cout << "consonant" << endl;
  return 0;
}

B問題

　入力を配列として全部受け取ってから、問題文の数式のように((i+2)/2)-1と行を求めること（配列は0スタートなのでその分ずれる）で実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int h, w;
  char str[100][100];
  string temp = "";

  cin >> h >> w;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      cin >> str[i][j];
    }
  }

  for(int i=0; i<2*h; i++) {
    for(int j=0; j<w; j++) {
      temp += str[((i+2)/2)-1][j];
    }
    cout << temp << endl;
    temp = "";
  }

  return 0;
}

C問題

　C++の文字列関係をまだ勉強してなかったので文字列操作について知ってるPythonで実装しました。dreamのあとにer, erase, eraserが来る場合で分けて処理しました。

 s = input()
flag = 1
i = 0

while i < len(s):
    if s[i:i+5] == 'dream':
        if s[i+5:i+10] != "erase" and s[i+5:i+7] == "er":
            i += 7
        elif s[i+5:i+11] == "eraser":
            i += 11
        elif s[i+5:i+10] == "erase":
            i += 10
        else:
            i += 5
    elif s[i:i+6] == "eraser":
        i += 6
    elif s[i:i+5] == "erase":
        i += 5
    else:
        flag = 0
        break

if(flag == 1):
    print("YES")
else:
    print("NO")

D問題

　解いた過去問でUnion-Find木の問題があったのに勉強を後回しにしていたらUnion-Findの問題が出てしまってちょっとショック。実装でつまってるので解けたら追記。

2016-12-13

ABC023を解いてみた

ABC 競技プログラミング

abc023.contest.atcoder.jp

A問題

　string型で入力を受けとり1桁ずつに区分けし加算していきました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int x, ans = 0;
  string str;
  cin >> str;

  for(int i=0; i<str.size(); i++) {
    ans += (int(str[i])-48); //文字コード
  }

  cout << ans << endl;

  return 0;
}

B問題

　手順の回数は (n-1)/2 回となります。問題文の処理をこの回数分行い、できた文字列と与えられた文字列を比較しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n;
  string s, comp = "b";

  cin >> n;
  cin >> s;

  for(int i=1; i<=(n-1)/2; i++) {
    if (i % 3 == 1) comp = "a" + comp + "c";
    else if(i % 3 == 2) comp = "c" + comp + "a";
    else comp = "b" + comp + "b";
  }

  if(s == comp) cout << (n-1)/2 << endl;
  else cout << -1 << endl;

  return 0;
}

C問題

　部分点解法しか思い浮かばなかったので解説を見て実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 100000

int main(void)
{
  int r, c, k;
  cin >> r >> c >> k;
  int n;
  cin >> n;

  vector<int> y(n), x(n), countrow(r, 0), countcol(c, 0);
  for(int i=0; i<n; i++) {
    cin >> y[i] >> x[i];
    y[i]--; x[i]--;
    //列、行ごとの飴の数
    //countrow[i] = j i行目にj個の飴
    countrow[y[i]]++; countcol[x[i]]++;
  }

  //特定の飴の個数の行、列の数
  //numrow[i] = j 飴の数がi個の行がj個
  vector<ll> numrow(n+1, 0), numcol(n+1, 0);
  for(int i=0; i<r; i++) numrow[countrow[i]]++;
  for(int i=0; i<c; i++) numcol[countcol[i]]++;

  ll sum = 0;
  for(int i=0; i<=k; i++) sum += numrow[i]*numcol[k-i];
  for(int i=0; i<n; i++) {
    //飴がある場所を起点としていて合計がk, k+1のとき
    if(countrow[y[i]] + countcol[x[i]] == k) sum--;
    else if(countrow[y[i]] + countcol[x[i]] == k+1) sum++;
  }

  cout << sum << endl;

  return 0;
}

D問題

　思い浮かばなかったので解説を見て実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n;
  cin >> n;
  vector<ll> h(n), s(n);
  for(int i=0; i<n; i++) cin >> h[i] >> s[i];

  ll hmax = *max_element(h.begin(), h.end()), smax = *max_element(s.begin(), s.end());
  //一番大きいxとしてありえるのはmax(h)+max(s)*n
  ll left=0, right=hmax+smax*n, mid=(left+right)/2;
  bool flag = true;
  vector<ll> t(n);

  //二分探索
  while( right-left > 1)
  {
    flag = true; mid=(left+right)/2;
    // midのとき条件を満たすかを確かめる
    for(int i=0; i<n; i++) {
      if(mid < h[i]) t[i] = -1;
      else t[i] = (mid-h[i])/s[i];
    }
    sort(t.begin(), t.end());
    for(int i=0; i<n; i++) {
      //貪欲的に考えていって成り立たないt[i]が存在するなら条件は満たさない
      if(t[i] < i) {
        flag = false;
        break;
      }
    }

    //条件を満たすなら
    if(flag) {right = mid;}
    //条件を満たさないなら
    else {left = mid;}
  }

  cout << right << endl;
  return 0;
}

2016-12-10

ABC040を解いてみた

ABC 競技プログラミング

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木を知らなかったので蟻本で勉強して出直してきます…

ferinの競プロ帳

競プロについてのメモ

ABC027を解いてみた

A問題

B問題

C問題

D問題

ABC025を解いてみた

A問題

B問題

C問題

D問題

ABC026を解いてみた

A問題

B問題

C問題

D問題

ABC024を解いてみた

A問題

B問題

C問題

D問題

ABC049を解いてみた

A問題

B問題

C問題

D問題

ABC023を解いてみた

A問題

B問題

C問題

D問題

ABC040を解いてみた

A問題

B問題

C問題

D問題