AtCoder が提供しているABC（AtCoder Beginner Contest）346 のD問題をC++とPythonで解いてみました。ABC346は、2024年3月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Gomamayo Sequence（Difficulty : 845）
問題はリンク先をご覧ください。
前からと後ろからのコストを計算しておき、合わせて最小値を求めます。AtCoder Problems による Difficulty は 845 でした。
解答案
以下を先に計算しておきます。
- 左から “010101…” のような文字列にするためのコストを left01 として求めておきます。
- 左から “101010…” のような文字列にするためのコストを left10 として求めておきます。
- 右から “…10101010” のような文字列にするためのコストを right01 として求めておきます。
- 右から “…01010101” のような文字列にするためのコストを right10 として求めておきます。
良い文字列にするためには、leftXX と rightYY を組み合わせて、同じ文字になる文字が ‘0’ となる場合（”00″ が現れる）と ‘1’ となる場合（”11″ が現れる）を求めて、その最小値が解となります。
C++ プログラム例（ABC346D）
コードは少し長くなりました。特に4つの配列を求める下準備が長くなりました（17ー73行目）。二つの配列を組み合わせて、最小値を求めます（75ー101行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1ULL << 60)
int main()
{
int n;
string s;
cin >> n >> s;
vector<ll> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
vector<ll> left01(n);
vector<ll> left10(n);
if (s[0] == '0') {
left01[0] = 0;
left10[0] = c[0];
} else {
left01[0] = c[0];
left10[0] = 0;
}
for (int i = 1; i < n; ++i) {
if (i % 2 == 0) {
if (s[i] == '0') {
left01[i] = left01[i - 1];
left10[i] = left10[i - 1] + c[i];
} else {
left01[i] = left01[i - 1] + c[i];
left10[i] = left10[i - 1];
}
} else {
if (s[i] == '0') {
left01[i] = left01[i - 1] + c[i];
left10[i] = left10[i - 1];
} else {
left01[i] = left01[i - 1];
left10[i] = left10[i - 1] + c[i];
}
}
}
vector<ll> right01(n);
vector<ll> right10(n);
if (s[n - 1] == '0') {
right01[n - 1] = 0;
right10[n - 1] = c[n - 1];
} else {
right01[n - 1] = c[n - 1];
right10[n - 1] = 0;
}
for (int i = n - 2; i >= 0; --i) {
if ((n - 1 - i) % 2 == 0) {
if (s[i] == '0') {
right01[i] = right01[i + 1];
right10[i] = right10[i + 1] + c[i];
} else {
right01[i] = right01[i + 1] + c[i];
right10[i] = right10[i + 1];
}
} else {
if (s[i] == '0') {
right01[i] = right01[i + 1] + c[i];
right10[i] = right10[i + 1];
} else {
right01[i] = right01[i + 1];
right10[i] = right10[i + 1] + c[i];
}
}
}
ll result = INF;
for (int i = 0; i < n - 1; ++i) {
ll t1, t2;
if (i % 2 == 0) {
t1 = left01[i];
t2 = left10[i];
if ((n - 1 - (i + 1)) % 2 == 0) {
t1 += right01[i + 1];
t2 += right10[i + 1];
} else {
t1 += right10[i + 1];
t2 += right01[i + 1];
}
} else {
t1 = left10[i];
t2 = left01[i];
if ((n - 1 - (i + 1)) % 2 == 0) {
t1 += right01[i + 1];
t2 += right10[i + 1];
} else {
t1 += right10[i + 1];
t2 += right01[i + 1];
}
}
result = min(result, t1);
result = min(result, t2);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC346D）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 346 D"""
INF = 1 << 60
n = int(input())
s = input()
c = list(map(int, input().split()))
left01 = [0] * n
left10 = [0] * n
if s[0] == '0':
left01[0] = 0
left10[0] = c[0]
else:
left01[0] = c[0]
left10[0] = 0
for i in range(1, n):
if i % 2 == 0:
if s[i] == '0':
left01[i] = left01[i - 1]
left10[i] = left10[i - 1] + c[i]
else:
left01[i] = left01[i - 1] + c[i]
left10[i] = left10[i - 1]
else:
if s[i] == '0':
left01[i] = left01[i - 1] + c[i]
left10[i] = left10[i - 1]
else:
left01[i] = left01[i - 1]
left10[i] = left10[i - 1] + c[i]
right01 = [0] * n
right10 = [0] * n
if s[n - 1] == '0':
right01[n - 1] = 0
right10[n - 1] = c[n - 1]
else:
right01[n - 1] = c[n - 1]
right10[n - 1] = 0
for i in range(n - 2, -1, -1):
if (n - 1 - i) % 2 == 0:
if s[i] == '0':
right01[i] = right01[i + 1]
right10[i] = right10[i + 1] + c[i]
else:
right01[i] = right01[i + 1] + c[i]
right10[i] = right10[i + 1]
else:
if s[i] == '0':
right01[i] = right01[i + 1] + c[i]
right10[i] = right10[i + 1]
else:
right01[i] = right01[i + 1]
right10[i] = right10[i + 1] + c[i]
result = INF
for i in range(0, n - 1):
if i % 2 == 0:
t1 = left01[i]
t2 = left10[i]
if (n - 1 - (i + 1)) % 2 == 0:
t1 += right01[i + 1]
t2 += right10[i + 1]
else:
t1 += right10[i + 1]
t2 += right01[i + 1]
else:
t1 = left10[i]
t2 = left01[i]
if (n - 1 - (i + 1)) % 2 == 0:
t1 += right01[i + 1]
t2 += right10[i + 1]
else:
t1 += right10[i + 1]
t2 += right01[i + 1]
result = min(result, t1)
result = min(result, t2)
print(result)こちらも「AC」と判定されました。
最後に
公式解説では、すっきりとプログラムを書いていました。わたしのプログラムは長くなりましたが、自分の考えでコーディングしたので、そのまま、この記事で紹介することにしました。
引き続き ABC の問題を紹介していきます。
