ferinの競プロ帳

競プロについてのメモ

ABC029を解いてみた

abc029.contest.atcoder.jp

A問題

 文字列の最後にsを連結しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

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

  cout << s + 's' << endl;

  return 0;
}

B問題

 全ての文字列についてrが含まれているか全探索しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

int main(void)
{
  string s[12];
  for(int i=0; i<12; i++) cin >> s[i];

  int ans = 0;

  for(int i=0; i<12; i++) {
    for(int j=0; j<s[i].size(); j++) {
      if(s[i][j] == 'r') {ans++; break;}
    }
  }

  cout << ans << endl;

  return 0;
}

C問題

 8重のforループを書く気はしなかったので深さ優先探索で全列挙しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

int n;
char s[3] = {'a', 'b', 'c'}, ans[10];

int dfs(int i) {
  if(i == n) {cout << ans << endl; return 0;}

  for(int j=0; j<3; j++) {
    ans[i] = s[j];
    dfs(i+1);
  }

  return 0;
}

int main(void)
{
  cin >> n;
  dfs(0);

  return 0;
}

D問題

 9まで、99まで、999まで…に1が出てくる数を求め、この数と各桁の数に応じて場合分けして全パターンを求めました。
昔算数でこんな問題解いた気がします。解説の解法がシンプルでわかりやすかった。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

//10のべき乗を求める
ll mypow(int i) {
  ll ret = 1;
  for(int j=0; j<i; j++) ret *= 10;
  return ret;
}

int main(void)
{
  ll memo[15], n, ans = 0;
  cin >> n;

  //桁数を求める
  int digit = 0;
  ll _n = n;
  while(_n > 0) {
    _n /= 10;
    digit++;
  }

  // 9まで、99まで、999まで…に含まれる1の数を求める
  memo[0] = 1;
  for(int i=1; i < digit; i++) {
    memo[i] = mypow(i) + (memo[i-1]*10);
  }

  int temp;
  for(int i=digit-1; i > 0; i--) {
    // i桁目の数
    temp = n / mypow(i);
    if(temp >= 2) {
      ans += mypow(i) + temp*memo[i-1];
    } else if(temp == 1) {
      // a = n % 10^i
      ll a = n - temp*mypow(i);
      ans += a + memo[i-1] + 1;
    }
    // temp * 10^i までに含まれるiの数が求められている
    n -= temp * mypow(i);
  }

  // 1の位が1以上なら1の数はプラス1
  if(n >= 1) {ans++;}

  cout << ans << endl;

  return 0;
}

ABC028を解いてみた

abc028.contest.atcoder.jp

A問題

 条件に合わせて分岐して出力しました。Perfectのスペル間違えてWA出したので気をつけたい。

#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 n;
  cin >> n;

  if(n <= 59) cout << "Bad" << endl;
  else if(n <= 89) cout << "Good" << endl;
  else if(n <= 99) cout << "Great" << endl;
  else cout << "Perfect" << endl;

  return 0;
}

B問題

 文字コードでint(s[i])-int('A')が0,1,2,3,4,5になるのを使いました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

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

  int a[6]={0};
  for(int i=0; i<s.size(); i++) {
    a[int(s[i])-int('A')]++;
  }

  cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << " " << a[5] << endl;

  return 0;
}

C問題

 5C3なら全探索でも余裕そうなので、1番大きい、2番目に大きい、3番目に大きい数字を記録しつつ全ての組み合わせについて全探索しました。

#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[5];
  cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

  int ret = 0, max1 = -INF, max2 = -INF, max3 = -INF;
  for(int i=0; i<5; i++) {
    for(int j=i+1; j<5; j++) {
      for(int k=j+1; k<5; k++) {
        ret = a[i] + a[j] + a[k];
        if(ret > max1) {
          max3 = max2;
          max2 = max1;
          max1 = ret;
        } else if(ret > max2) {
          max3 = max2;
          max2 = ret;
        } else if(ret > max3) {
          max3 = ret;
        }
      }
    }
  }

  cout << max3 << endl;

  return 0;
}

D問題

 全ての数字が異なる場合、kが一つとkより小さい数が一つ、kより大きい数が一つになります。3P3=6より(k-1)*(n-k)*6通りのパターンが存在します。同じ数が2つの場合、kが二つとk以外の数が一つになります。3P1=3より(n-1)*3通りのパターンが存在します。同じ数が3つの場合、kが3つになります。これは1通りしかありません。答えは {(k-1)*(n-k)*6+(n-1)*3+1}/(n*n*n) になります。
 数学っぽく解くだけだったのでそんなに手こずらなかったです。doubleとintで何回かWA出したので気をつけたい。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

int main(void)
{
  double n, k;
  cin >> n >> k;
  double ans = (k-1)*(n-k)*6 + (n-1)*3 + 1;
  cout << fixed << setprecision(15) << ans/(n*n*n) << endl;

  return 0;
}

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

ABC025を解いてみた

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の実装で詰まったのでできたら追記します…

ABC026を解いてみた

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);
  //直属の部下がいなければ給料は1
  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波を足し合わせたグラフになるので、上下に振れながら大きくなっていくグラフになります。答えが小数になる関数の探索なので2分探索かなと目処を立てて実装しました。最小の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;
}

ABC024を解いてみた

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

ABC049を解いてみた

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の問題が出てしまってちょっとショック。実装でつまってるので解けたら追記。