AtCoder Beginner Contest D - Flip and Adjust
問題はこちら
回答
bit全探索は無理なため、効率化を行う
全探索の効率化はDPが考えられる
a,bをものの重さと考えた時に、Sがとれる重さの限界と考えた
ここで、ナップザック系と考えた
まず全てaをとる前提で、Sからaの合計の差分を引く
そしてb-aを求めていき、Sからaの合計の差分がbを選択することで0(★)になるように、bを0/1ナップザックの要領でとるか否か考えていけばいいのかと思った
dp[i][j] : i番目のカードがjの時の★のスコア
として考えていったいたが、スコアが3,-3となったときに、どちらがいいスコアなのか優劣をつけられず、わからなくなった
解説を見ると、3.-3のようなスコアの状態も分けてdpで解いていた
dp[i][j] : iまで見た時に、合計がjにできるかどうか ※dp配列内の値はbool
ちなみに、数の集合からいくつかとって、指定の値になるかどうかという、部分和問題はdpしかないとのこと
コードは以下
特に、今回ABの配列を0-indexed, dpの2配列のy方向の配列を1-indexedとしているためミスりやすい
AB[j][i-1] : dp[j][i-1]→dp[j][i]に行くための値なため、しっかりそのことが意識から離れないように、しっかりコードにコメント書きながらコーディングするのが、ミスを減らすコツ
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>
int N, S;
int main()
{
std::cin.tie(0);
std::ios::sync_with_stdio(false);
std::cin >> N >> S;
std::vector<std::vector<int>> AB = std::vector<std::vector<int>>(2, std::vector<int>(N));
for (int i = 0; i < N; i++) {
// 0 : A, 1 : B
std::cin >> AB[0][i] >> AB[1][i];
}
// dp[i][j] : iまで見たときに値jを算出できるか
// デフォルトはfalse
std::vector<std::vector<bool>> dp = std::vector<std::vector<bool>>(N + 1, std::vector<bool>(S + 1));
// まだ見ていなくても、値0は作ることができる
dp[0][0] = true;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= S; j++) {
// 例えば、a=1, b=2の時、
// dp[1][0 + 1] = dp[0][0](true)
// dp[1][0 + 2] = dp[0][0](true)
// となる, その後、jのループが進むと、以下の★の部分で、値の書き換えが発生してしまう
// dp[1][1 + 1] = dp[0][1](false ★)
// dp[1][1 + 2] = dp[0][1](false)
// 以下でそれを防止
// 今後も、安全(確実)なコードを意識
if (!dp[i][j]) {
continue;
}
// A(表)について
if (j + AB[0][i] <= S) {
// 状態遷移 : i→i+1, j→j+A[i]
dp[i + 1][j + AB[0][i]] = dp[i][j];
}
if (j + AB[1][i] <= S) {
// 状態遷移 : i→i+1, j→j+B[i]
dp[i + 1][j + AB[1][i]] = dp[i][j];
}
}
}
// Nまで見たときに、Sを作れなかったらアウト
if (!dp[N][S]) {
std::cout << "No" << std::endl;
return 0;
}
// 経路の復元
// i=N, j=Sから逆にたどる
std::string ans;
std::vector<std::string> HL{ "H", "T" };
int gVal = S;
for (int i = N; i >= 1; i--) {
// 各iでtrueへのパスを少なくとも1つ見つける
// A,Bのループ
for (int j = 0; j < 2; j++) {
// 1つ前のiにおける値
// AB : 0-indexed
// AB[j][i-1] : dp[j][i-1]→dp[j][i]に行くための値
int tmpGVal = gVal - AB[j][i - 1];
if (tmpGVal < 0) {
continue;
}
// dp[j][i]→dp[tmpGVal][i-1]の状態にさかのぼったときに、dp[tmpGVal][i-1]に到達できる
if (dp[i - 1][tmpGVal]) {
ans += HL[j];
gVal = tmpGVal;
break;
}
}
}
std::reverse(ans.begin(), ans.end());
std::cout << "Yes" << std::endl;
std::cout << ans << std::endl;
return 0;
}
ABも1-indexedにした方が整理しやすい?
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>
int N, S;
int main()
{
std::cin.tie(0);
std::ios::sync_with_stdio(false);
std::cin >> N >> S;
// AB[j][i] : i-1→iに遷移するときの貰えるスコア
std::vector<std::vector<int>> AB = std::vector<std::vector<int>>(2, std::vector<int>(N+1));
for (int i = 1; i <= N; i++) {
// 0 : A, 1 : B
std::cin >> AB[0][i] >> AB[1][i];
}
// dp[i][j] : iまで見たときに値jを算出できるか
// デフォルトはfalse
std::vector<std::vector<bool>> dp = std::vector<std::vector<bool>>(N + 1, std::vector<bool>(S + 1));
// まだ見ていなくても、値0は作ることができる
dp[0][0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= S; j++) {
// 例えば、a=1, b=2の時、
// dp[1][0 + 1] = dp[0][0](true)
// dp[1][0 + 2] = dp[0][0](true)
// となる, その後、jのループが進むと、以下の★の部分で、値の書き換えが発生してしまう
// dp[1][1 + 1] = dp[0][1](false ★)
// dp[1][1 + 2] = dp[0][1](false)
// 以下でそれを防止
// 今後も、安全(確実)なコードを意識
if (!dp[i-1][j]) {
continue;
}
// AB[j][i] : i-1→iに遷移するときの貰えるスコア
// A(表)について
if (j + AB[0][i] <= S) {
// 状態遷移 : i-1→i, j→j+A[i]
dp[i][j + AB[0][i]] = dp[i-1][j];
}
if (j + AB[1][i] <= S) {
// 状態遷移 : i-1→i, j→j+B[i]
dp[i][j + AB[1][i]] = dp[i-1][j];
}
}
}
// Nまで見たときに、Sを作れなかったらアウト
if (!dp[N][S]) {
std::cout << "No" << std::endl;
return 0;
}
// 経路の復元
// i=N, j=Sから逆にたどる
std::string ans;
std::vector<std::string> HL{ "H", "T" };
int gVal = S;
for (int i = N; i >= 1; i--) {
// 各iでtrueへのパスを少なくとも1つ見つける
// A,Bのループ
for (int j = 0; j < 2; j++) {
// 1つ前のiにおける値
// AB : 1-indexed
// AB[j][i] : dp[j][i-1]→dp[j][i]に遷移するときの貰えるスコア
int tmpGVal = gVal - AB[j][i];
if (tmpGVal < 0) {
continue;
}
// dp[j][i]→dp[tmpGVal][i-1]の状態にさかのぼったときに、dp[tmpGVal][i-1]に到達できる
if (dp[i - 1][tmpGVal]) {
ans += HL[j];
gVal = tmpGVal;
break;
}
}
}
std::reverse(ans.begin(), ans.end());
std::cout << "Yes" << std::endl;
std::cout << ans << std::endl;
return 0;
}