ABC011 C問題（123引き算）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）011 C問題をC++で解いてみました。ABC011は、2014年6月21日21:30に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 123引き算（Difficulty : 810（参考値））

問題の詳細は、リンク先をご覧ください。

ABC011 C問題 123引き算

DPで解ける典型問題です。AtCoder Problems による Difficulty は 810（参考値）でした。

解答案

C++ プログラム例（ABC011C）

DP（動的計画法）で解きます。配列 dp[i] は、引き算で i にすることができれば true 、できなければ false とします。

1から100まで小さい数字から dp[i] の値を調べます。もし、dp[i] が true なら、dp[i-3]、dp[i-2]、dp[i-1] を true にします（17ー25行目）。ただし、dp[NG1]、dp[NG2]、dp[NG3] は、true にならず false にします（26ー28行目）。この操作を100回繰り返します。

与えられる N が NG1、NG2、NG3 と一致している場合があります。13～15行目でこの処理を実装します。以下が、C++プログラムです。

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

int main()
{
	int n;
	cin >> n;
	int ng1, ng2, ng3;
	cin >> ng1 >> ng2 >> ng3;

	vector<bool> dp(n + 1, false);
	dp[n] = true;
	dp[ng1] = false;
	dp[ng2] = false;
	dp[ng3] = false;
	for (int i = 0; i < 100; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (dp[j]) {
				for (int k = 1; k <= 3; ++k) {
					if (j - k >= 0) {
						dp[j - k] = true;
					}
				}
			}
		}
		dp[ng1] = false;
		dp[ng2] = false;
		dp[ng3] = false;
	}

	if (dp[0]) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

DP（動的計画法）を使う典型的な問題です。典型問題を解くことにより習熟度を上げていきたいです。

引き続き ABC の問題を紹介していきます。