AtCoder が提供しているABC（AtCoder Beginner Contest）349 のE問題をC++で解いてみました。ABC349は、2024年4月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Weighted Tic-Tac-Toe（Difficulty : 1464）
問題はリンク先をご覧ください。
ABC349 E問題 Weighted Tic-Tac-Toe
重み付きの三目並べを解きます。AtCoder Problems による Difficulty は 1464 でした。
解答案
三目並べは、双方が最善を尽くせば引き分けになります。ただし、先手がかなり有利なゲームです。前日の記事で、三目並べを解くプログラムを紹介しました。
重みを付けることによって、後手必勝の場合があり得るのは、非常に興味深い結果です。
C++ プログラム例（ABC349E）
三目並べを解くプログラムをベースにしました（プログラムはここで紹介しています）。
元のプログラムとの違いは以下となります。
- 判定関数 judge に、点数計算をして判定結果を返す処理を追加しました（今回の最大の改造点です）。
- 今回の問題は制約から引き分けがありません。これによってかなり楽になっています。
- enum の値などの定義を O と X から T（Takahashi）と A（Aoki）に変更しました。
再帰関数（バックトラック）を使って勝敗が決まるまで手を進めて、全通りを調べるという基本的な構造は同じです。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef enum {T_WIN, A_WIN, NOTYET} RESULT;
typedef enum {T, A, EMPTY} BOARD;
vector<ll> a(9);
RESULT judge(vector<BOARD> b)
{
RESULT result = NOTYET;
// column
for (int i = 0; i < 3; ++i) {
if ((b[3 * i] == b[3 * i + 1])&&(b[3 * i] == b[3 * i + 2])) {
if (b[3 * i] == T) {
result = T_WIN;
} else if (b[3 * i] == A) {
result = A_WIN;
}
}
}
// row
for (int i = 0; i < 3; ++i) {
if ((b[i] == b[i + 3])&&(b[i] == b[i + 6])) {
if (b[i] == T) {
result = T_WIN;
} else if (b[i] == A) {
result = A_WIN;
}
}
}
// diagonal
if (((b[0] == b[4])&&(b[0] == b[8]))
||((b[2] == b[4])&&(b[2] == b[6]))) {
if (b[4] == T) {
result = T_WIN;
} else if (b[4] == A) {
result = A_WIN;
}
}
if (result != NOTYET) {
return result;
}
bool done = true;
ll t_point = 0;
ll a_point = 0;
for (int i = 0; i < 9; ++i) {
if (b[i] == EMPTY) {
done = false;
} else if (b[i] == T) {
t_point += a[i];
} else if (b[i] == A) {
a_point += a[i];
}
}
if (!done) {
result = NOTYET;
} else if (t_point > a_point) {
result = T_WIN;
} else {
result = A_WIN;
}
return result;
}
RESULT rec(int n, vector<BOARD> b)
{
RESULT result;
result = judge(b);
if (result == NOTYET) {
bool this_t = false;
bool this_a = false;
for (int i = 0; i < 9; ++i) {
RESULT this_result = NOTYET;
if (b[i] == EMPTY) {
if (n % 2 == 0) {
b[i] = T;
} else {
b[i] = A;
}
this_result = rec(n + 1, b);
b[i] = EMPTY;
}
if (this_result == T_WIN) {
this_t = true;
}
if (this_result == A_WIN) {
this_a = true;
}
}
if (n % 2 == 0) {
if (this_t) {
result = T_WIN;
} else {
result = A_WIN;
}
}
if (n % 2 == 1) {
if (this_a) {
result = A_WIN;
} else {
result = T_WIN;
}
}
}
return result;
}
int main()
{
for (int i = 0; i < 9; ++i) {
cin >> a[i];
}
vector<BOARD> b(9, EMPTY);
RESULT result = rec(0, b);
if (result == T_WIN) {
cout << "Takahashi" << endl;
} else {
cout << "Aoki" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
C++ の解説で長くなってしまったので、Python 版の紹介は省略します。
最後に
この記事で紹介したプログラムは、enum を導入するなど、丁寧に実装しています。競技プログラミングの実装としては、タイプ量が多いかもしれません（まぁ、このブログで紹介しているプログラムは、全体的にタイプ量は多くなっていますが）。バックトラックを学ぶつもりでコンテスト後に書いたプログラムであることを留意していただけたらと思います。
この問題を通じて多くのことを学ぶことができました。
引き続き ABC の問題を紹介していきます。
