AtCoder が提供しているABC（AtCoder Beginner Contest）291 のD問題をC++とPythonで解いてみました。ABC291は、2023年2月26日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Flip Cards（Difficulty : 720）
問題はリンク先をご覧ください。
DPを使って解くことができます。AtCoder Problems による Difficulty は 720 でした。
解答案
DP（Dynamic Programming: 動的計画法）を使います。
問題の状況から、以下のことが分かります。
- 隣のカードが表裏共に等しい場合は、条件を満たす数は増えない。
- 隣のカードが表裏のどちらかと等しい場合は、条件を満たす数は移行される。
- 隣のカードが表裏共に等しくない場合は、条件を満たす数は2倍になる。
dp[i][j] は、i 枚のカードがある状況で、i 枚目が j = 0 の場合に表、j = 1 の場合に裏としたときの条件を満たす数とします。
- dp[i + 1][0] は、
- Ai+1 と Ai が等しくない場合、dp[i][0] を加える。
- Ai+1 と Bi が等しくない場合、dp[i][1] を加える。
- dp[i + 1][1] は、
- Bi+1 と Ai が等しくない場合、dp[i][0] を加える。
- Bi+1 と Bi が等しくない場合、dp[i][1] を加える。
漸化式の初期値は、以下となります。
- dp[1][0] = 1、dp[1][1] = 1、それ以外の dp[i][j] = 0 とする。
解答は、dp[N][0] + dp[N][1] となります。制約のもとで計算結果は非常に大きくなるため、適宜 998244353 との割った余りを求めていきます。
C++ プログラム例（ABC291D）
上記の漸化式をプログラムとして表現しました。表裏の関係が4通りあります。繰り返しが2通りのループを2重にして表現しました（23、24行目）。
なお、配列の添え字を0から使うため、問題文とは添え字が1少なくなっています。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define MOD 998244353
int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
vector<vector<ull>> dp(n, vector<ull>(2, 0));
dp[0][0] = 1;
dp[0][1] = 1;
for (int i = 1; i < n; ++i) {
for (int pre = 0; pre < 2; ++pre) {
for (int cur = 0; cur < 2; ++cur) {
int pre_data;
int cur_data;
if (pre == 0) {
pre_data = a[i - 1];
} else {
pre_data = b[i - 1];
}
if (cur == 0) {
cur_data = a[i];
} else {
cur_data = b[i];
}
if (cur_data != pre_data) {
dp[i][cur] += dp[i - 1][pre];
dp[i][cur] %= MOD;
}
}
}
}
cout << (dp[n - 1][0] + dp[n - 1][1])% MOD << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC291D）
Python 版は、C++ をそのまま移植しました。あまり Python らしくないプログラムかもしれません。
"""AtCoder Beginner Contest 291 D"""
MOD = 998244353
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
dp = [[0 for i2 in range(2)] for i1 in range(n)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(1, n):
for pre in range(2):
for cur in range(2):
if pre == 0:
pre_data = a[i - 1]
else:
pre_data = b[i - 1]
if cur == 0:
cur_data = a[i]
else:
cur_data = b[i]
if cur_data != pre_data:
dp[i][cur] += dp[i - 1][pre]
dp[i][cur] %= MOD
print((dp[n - 1][0] + dp[n - 1][1]) % MOD)こちらも「AC」と判定されました。
最後に
この問題は、DP を使うことも考えましたが、隣と表裏がどちらも異なる場合、2倍するなどを条件文で表現して解けると考えてしまいました。結果的には、うまく解けず時間切れとなりました。
漸化式に落とし込んで考えたら解くことができました。DP は、まだ慣れていないのだと思います。解説することで理解を深めていきたいです。
引き続き ABC の問題を紹介していきます。
