ABC023を解いてみた

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