AtCoder

ABC291 D問題(Flip Cards)を解く

AtCoder_ABC291_D

AtCoder が提供しているABC(AtCoder Beginner Contest)291 のD問題をC++とPythonで解いてみました。ABC291は、2023年2月26日21:00に実施されました。

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

D問題 Flip Cards(Difficulty : 720)

問題はリンク先をご覧ください。

ABC291 D問題 Flip Cards

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 は、まだ慣れていないのだと思います。解説することで理解を深めていきたいです。

ABC291 について、引き続き、E問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA