はじめに

---

以前、コーディングの勉強も兼ねてAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～で紹介されてる問題を C++で解いた。当時から１年ほど経過した今、同じ問題を解く事で、コーディングの変化が見えるのではないかと考え、解き直してみた。また、AtCoder では過去問を提出・採点する事もできるので、その変化も記録として残してみようと思う。

TL;DR

---

• if()の条件で||,&&があっても難なく読めるようになった
• range-based-forを使えるようになった
• イテレータの概念を知った
• algorithmライブラリを使えるようになった
• コードの文字数に対する情報量が上がった（気がする）
• コードの部分を再利用性のある関数に書き出す事ができるようになった
• 処理に不必要な変数を間引く事が出来るようになった

第 1 問:

---

ABC 086 A - Product

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

Before

---

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

After

---

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

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

Diff

---

if()-elseの条件を１つにまとめた。Before の時にも||で OR 条件にできることは知っていたが、||の可読性が悪いと考えていた。しかし、コードに慣れてきたところ、複数条件が気にならなくなった。

プログラミングの練度によって同じ時間で多くのソースコードを脳内処理できるのだろう。if()をネストすると、冗長な表現になり、文字数に対する情報が減るので慣れていないうちはif()をネストしがちなのかもしれない。

第 2 問:

---

ABC 081 A - Placing Marbles

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

Before

---

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

After

---

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

int main(){
	string str;
	cin >> str;
	cout << count(str.begin(), str.end(), '1') << endl;
	return 0;
}

Diff

---

algorithmライブラリを使えるようになった。Before 時点では、イテレータも知らなかったので、ここはポイントであろう。 また、vectorの入力に range-base-for を使うようになった。 処理内容は同じと思われるため実行時間は変化がなかったが、コード長が短縮された。

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

After

---

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

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto& e : a) cin >> e;
	int counter = -1;
	bool isDividable = true;
	while(isDividable){
		for(auto& e : a){
			if( e == 0 ) isDividable = false;
			if( e%2 == 0 ) e /= 2;
			else isDividable = false;
		}
		counter++;
	}
	cout << counter << endl;
	return 0;
}

Diff

---

Before より After の方がコード長が短く、また、可読性が高く感じる。 tempなどの再読性の低い変数はしないように心がけたい（実は、普段は使っている）。

第 4 問:

---

ABC 087 B - Coins

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

Before

---

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

After

---

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

int main(){
	int a, b, c, x;
	cin >> a >> b >> c >> x;
	int pattern = 0;
	for(int i=0; i<=a; ++i){
		int money = 500*i;
		if(money > x) break;
		for(int j=0; j<=b; ++j){
			if(money > x) break;
			if(x-money <= 50*c) pattern++;
			money += 100;
		}
	}
	cout << pattern << endl;
	return 0;
}

Diff

---

第 5 問:

---

ABC 083 B - Some Sums

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

Before

---

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

After

---

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

int digitSum(int num){
	int sum = 0;
	while(num != 0){
		sum += num % 10;
		num /= 10;
	}
	return sum;
}

int main(){
	int n, a, b;
	cin >> n >> a >> b;
	int sum = 0;
	for(int i=0; i<=n; ++i){
		if( a<=digitSum(i) && digitSum(i)<=b ) sum += i;
	}
	cout << sum << endl;
	return 0;
}

Diff

---

プログラムの部分を、再利用性のある関数（digitSum()）に書き出す事ができるようになった。 その際、全体のコード長はそこまで短くならないのだが、他の処理が必要となった時には大きなコード長削減が見込めるだろう。

第 6 問:

---

ABC 088 B - Card Game for Two

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

Before

---

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

int main(){
	int n;
	cin >> n;
	vector<int> a(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;
}

After

---

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

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto& e : a) cin >> e;
	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;
}

Diff

---

自分でもびっくりするほど何も変わらなかった。

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

After

---

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

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

Diff

---

自分でもびっくりするほど変化がなかった。

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

After

---

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

int main(){
	int n, y;
	cin >> n >> y;
	for(int i=0; 10000*i<=y; ++i){
		for(int j=0; 10000*i+5000*j<=y; ++j){
			if( 10000*i+5000*j+1000*(n-i-j) == y ){
				cout << i << " " << j << " " << n-i-j << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;
	return 0;
}

Diff

---

割り算を減らす事で3msの計算時間削減を果たした。

第 9 問:

---

ABC 049 C - Daydream

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

Before

---

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

After

---

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

int main(){
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	for(size_t i=0; i<s.length(); ++i){
		if( s.substr(i,5) == "maerd" ){
			i += 4;
			continue;
		}
		if( s.substr(i,7) == "remaerd" ){
			i += 6;
			continue;
		}
		if( s.substr(i,5) == "esare" ){
			i += 4;
			continue;
		}
		if( s.substr(i,6) == "resare" ){
			i += 5;
			continue;
		}
		cout << "NO" << endl;
		return 0;
	}
	cout << "YES" << endl;
	return 0;
}

Diff

---

可読性だけでなく、コード長・実行時間・メモリ共に Before の方が優れていた。また、After の方が可読性が落ちたと思う。

第 10 問:

---

ABC 086 C - Traveling

当時のプログラムを実行したところ、ACにならなかった(RE)ので、この問題は比較不可能

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

Before

---

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

After

---

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

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

Diff

---

RE が AC になったのは大きな進歩だと思う（前回は出来た気満々だった）。 ソースコード的な成長で言うと、処理に不必要な（冗長になる）変数を間引く事ができるようになった。