初心者がAtCoder過去問精選１０問をC++で解いた

はじめに

最近競技プログラミングに興味を持ち，AtCoderのABC123に参加してみました．しかし，思うように解けなかったため，AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～で紹介されてる問題をC++で解いてみました.
上記記事で紹介された問題の概要とそのプログラムを掲載いたします．プログラムの説明などは不要かと思ったので書きませんでしたが，わかりづらいなと思ったら逐次追記します．
とはいえ，競技プログラミングを初めてまだ１週間しか経っていない(2019/4/14現在)上，プログラミング歴も短いので，変な書き方をしているところも多いと思います．なにかあればコメント欄で教えていただけたらなと思います．
プログラムの作成はMacBookProでvimを用いています．

第1問: ABC 086 A - Product

二つの入力の積が偶数か奇数かを答える問題．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int a, b;
  cin >> a >> b;
  if(a%2==0){
    cout << "Even" << endl;
  }else{
    if(b%2==0){
      cout << "Even" << endl;
    }else{
      cout << "Odd" << endl;
    }
  }
  return 0;
}

乗算してから偶奇を求めるより，場合分けした方が良い気がする．

第2問: ABC 081 A - Placing Marbles

入力文字列に'1'が何個含まれているかを答える問題．

#include <bits/stdc++.h>
using namespace std;

int main(){
  string str;
  cin >> str;
  int count;
  for(int i=0; i<str.length(); i++){
    if(str[i] == '1'){
      count ++;
    }
  }
  cout << count << endl;
  return 0;
}

string型の要素数と各要素を確認するだけだった．

第3問: ABC 081 B - Shift Only

複数の入力整数すべてを割り切れる２の乗数を求める問題．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  int i;
  cin >> n;
  vector<int> a(n);
  for(i=0; i<n; i++){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int counter = 0;
  int temp = a[0];
  while(temp%2 == 0){
    temp = temp >> 1;
    counter++;
  }
  if(counter == 0){
    cout << 0 << endl;
    return 0;
  }
  int division = 1 << counter;
  while(1){
    for(i=0; i<a.size(); i++){
      if(a[i]%division != 0){
        break;
      }
      if(i == a.size()-1){
        cout << counter << endl;
        return 0;
      }
    }
    division = division >> 1;
    counter--;
  }
}

全てを割り切れる数ということは少なくとも公倍数であるため，ソートして一番小さいものを割り切れる２の乗数から計算を開始した．
２の指数を増減する際には*や/ではなくシフト演算子を用いた．

第4問: ABC 087 B - Coins

500円玉A枚，100円玉B枚，50円玉C枚を好きな枚数選び出した1組み合わせのうち，値段がX円になるものの数を答える問題．
ただし，同じ種類の硬貨を区別しないものとする．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int a, b, c, x;
  cin >> a >> b >> c >> x;
  int pat = 0;
  int aStt = ( x - 100*b - 50*c ) / 500;
  if(aStt<0){
    aStt = 0;
  }
  for(int aIdx=aStt; aIdx<a+1; aIdx++){
    int aTemp = 500*aIdx;
    if(aTemp > x){
      break;
    }
    int bStt = ( x - 500*aIdx - 50*c ) / 100;
    if(bStt < 0){
      bStt = 0;
    }
    for(int bIdx=bStt; bIdx<b+1; bIdx++){
      int bTemp = aTemp + 100*bIdx;
      if(bTemp > x){
        break;
      }
      if((x-bTemp)<=50*c){
        pat++;
      }
    }
  }
  cout << pat << endl;
  return 0;
}

総当たり的なプログラムになってしまった．

第5問: ABC 083 B - Some Sums

1以上N以下の整数のうち，１０進法での各桁の和Sが$A\leqq S\leqq B$となる整数の個数を求める問題．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, a, b;
  cin >> n >> a >> b;
  int count = 0;
  int sum = 0;
  for(int i=1; i<=n; i++){
    int temp = i;
    int sumTemp = 0;
    while(temp!=0){
      sumTemp += temp % 10;
      temp /= 10;
    }
    if(a <= sumTemp && sumTemp <= b){
      sum += i;
    }
  }
  cout << sum << endl;
  return 0;
}

各桁を取り出す計算をした．

第6問: ABC 088 B - Card Game for Two

$i$番目のカードに数値$a_i$の書かれたN枚のカードを交互にとっていくゲームで，お互いが最高点を取れるよう努める際に，両者の点数差は何点になるかを求める問題．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  vector<int> a(n);
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  sort(a.begin(), a.end(), greater<int>());
  int alice = 0;
  int bob = 0;
  for(int i=0; i<n; i+=2){
    alice += a[i];
    bob += a[i+1];
  }
  cout << alice - bob << endl;
  return 0;
}

ソートしてAliceとBobに交互に加算していき，その差を出力した．

第7問: ABC 085 B - Kagami Mochi

大きさをd[i]として与えられたN個餅を積み重ねてできる鏡餅を最大何段積めるか求める問題．
ただし，鏡餅は下の段より小さい鏡餅しか置けないものとされている．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> d(n);
  for(int i=0; i<n; i++){
    cin >> d[i];
  }
  sort(d.begin(), d.end());
  int count = 1;
  for(int i=1; i<n; i++){
    if(d[i] != d[i-1]){
      count ++;
    }
  }
  cout << count << endl;
  return 0;
}

ソートして，配列の要素の前後が等しいかそうでないかを確認し，等しくないものの個数を計算して出力した．

第8問: ABC 085 C - Otoshidama

10000円，5000円，1000円札に対して，値段Yと枚数Nの組み合わせが現実的にあり得るか求める問題．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, y;
  cin >> n >> y;
  int aEnd = y / 10000;
  for(int a=0; a<=aEnd; a++){
    int aTemp = y - 10000*a;
    int bEnd = aTemp / 5000;
    for(int b=0; b<=bEnd; b++){
      int c = (aTemp - 5000*b)/1000;
      if(a + b + c == n){
        cout << a << " " << b << " " << c << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
  return 0;
}

Y円になるa,b,cの組み合わせを求めて，a+b+c＝nであれば各値を出力．そうなる組み合わせが存在しなければ-1 -1 -1を出力．

第9問: ABC 049 C - Daydream

与えられた文字列Sが，４つの単語（"dream","dreamer","erase","eraser"）を連ねることで表すことができるか答える問題．

#include <bits/stdc++.h>
using namespace std;

string str[4] = {"maerd", "remaerd", "esare", "resare"};

int main(){
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  for(int i=0; i< s.size();){
    for(int j=0; j<4; j++){
      if(s.substr(i,str[j].size()) == str[j]){
        i += str[j].size();
        break;
      }
      if(j == 3){
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  cout << "YES" << endl;
  return 0;
}

実は，解説をチラッとみてしまった．
この問題は，組み合わせる各文字列が合体してしまう．これらの文字列およびSを反転することで合体を防ぎ，組み合わせが存在するかを調べることができる．

第10問: ABC 086 C - Traveling

この問題は、解けたと思っていたが誤解答でした。当時は、既に終わった問題をAtCoderに提出できることを知らなかったため、サンプル入出力のみをテストして、正答できたと勘違いしていました。すみませんでした。

停止することができない旅行者が，与えられた時刻tと位置(x,y)に存在することができるか答える問題．
ここで，時刻tでの位置が(x,y)である時にt+1での位置は(x+1,y),(x-1,y),(x,y+1),(x,y-1)のどれかであるものとする．

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, i;
  cin >> n;
  int pastEO = 0;
  int currEO = 0;
  int timeEO = 0;
  int necessaryMove = 0;
  vector<int> t(n), x(n), y(n);
  t[0] = x[0] = y[0] = 0;
  for(i=1; i<n+1; i++){
    cin >> t[i] >> x[i] >> y[i];
  }
  for(i=1; i<n+1; i++){
    necessaryMove = abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);
    if(necessaryMove > t[i] - t[i-1]){
      cout << "No" << endl;
      return 0;
    }
    timeEO = (t[i]-t[i-1])%2;
    currEO = (x[i]+y[i])%2;
    if(pastEO == currEO){
      if(timeEO != 0){
        cout << "No" << endl;
        return 0;
      }
    }else{
      if(timeEO == 0){
        cout << "No" << endl;
        return 0;
      }
    }
    pastEO = currEO;
  }
  cout << "Yes" << endl;
  return 0;
}

図に偶数回でいける位置，奇数回でいける位置を色分けして書いたらわかりやすかった．

エクセルでかっこよく書いたのだが，実際に解く時に書いたのは紙に手書きで黒丸白丸をかいただけのお粗末なグラフである．