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