2019/04/19
はじめに
最近競技プログラミングに興味を持ち，AtCoder の ABC123 に参加してみました．しかし，思うように解けなかったため， AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～で紹介されてる問題を C++で解いてみました. 上記記事で紹介された問題の概要とそのプログラムを掲載いたします．プログラムの説明などは不要かと思ったので書きませんでしたが，わかりづらいなと思ったら逐次追記します． とはいえ，競技プログラミングを初めてまだ１週間しか経っていない(2019/4/14 現在)上，プログラミング歴も短いので，変な書き方をしているところも多いと思います．なにかあればコメント欄で教えていただけたらなと思います． プログラムの作成は MacBookPro で vim を用いています．
第 1 問:
二つの入力の積が偶数か奇数かを答える問題．
#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 問:
入力文字列に'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 問:
複数の入力整数すべてを割り切れる２の乗数を求める問題．
#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 問:
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 問:
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 問:
$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 問:
大きさを 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 問:
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 問:
与えられた文字列 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 問:
停止することができない旅行者が，与えられた時刻 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;
}