AtCoder が提供しているABC（AtCoder Beginner Contest）293 のC問題をC++とPythonで解いてみました。ABC293は、2023年3月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Make Takahashi Happy（Difficulty : 431）
問題はリンク先をご覧ください。
ABC293 C問題 Make Takahashi Happy
組み合わせを使い、左上から右下までの経路を全検索します。AtCoder Problems による Difficulty は 431 でした。
解答案
左上から右下までの通り数は、高校数学（数学A「場合の数」）で学びます。
- 下への H – 1 回の移動と右への W – 1 回の移動、合計 H + W – 2 回移動します。
- H + W – 2 回の移動から、下への移動 H – 1 個を取る組み合わせ数が、左上から右下までの通り数となります。
- H + W – 2 回の移動から、右への移動 W – 1 個を取る組み合わせ数も、左上から右下までの通り数となります。
通る道が決まれば、マスにある数字を set コンテナに登録して、最後にコンテナの大きさを調べることにより、「嬉しくなる」か調べることができます。
C++ プログラム例（ABC293C）
bit全検索で解く方法を解説します。2H＋W-2 通りすべて調べます。bit全検索のコードパターンは、18、26、27行目となります。
bitに従い、1が立っていれば下に移動して、0であれば右に移動します。配列外参照を避けるためにガード処理を追加しています（29－32行目、37－40行目）。
移動するマスにある数字は set コンテナ passed に格納していきます（24、34、42行目）。最後に set コンテナの大きさが H + W – 1 であれば、解答 result を増やします（45行目）。
最終的な C＋＋プログラムは、以下となります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int h, w;
cin >> h >> w;
vector<vector<int>> a(h, vector(w, 0));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> a[i][j];
}
}
int result = 0;
for (ull bit = 0; bit < (1ULL << (h + w - 2)); ++bit) {
int count_h = 0;
int count_w = 0;
int now_h = 0;
int now_w = 0;
set<int> passed;
passed.insert(a[now_h][now_w]);
bool stop_flag = false;
for (ull i = 0; i < (h + w - 2) && !stop_flag ; ++i) {
if ((bit & (1LL << i)) != 0) {
++count_h;
if (count_h > h - 1) {
stop_flag = true;
continue;
}
++now_h;
passed.insert(a[now_h][now_w]);
} else {
++count_w;
if (count_w > w - 1) {
stop_flag = true;
continue;
}
++now_w;
passed.insert(a[now_h][now_w]);
}
}
if (passed.size() == h + w - 1) {
++result;
}
}
cout << result << endl;
return 0;
}組み合わせを得るために next_permutation を使ったバージョンも紹介します。
next_permutation の引数に渡す配列 dir は、W – 1 個の 0 と、H – 1 個の 1 を含むよう定義します（18－24行目、42行目）。
横に W – 1 回、下に H – 1 回しか動かないため、配列外参照が発生しません。移動先の数字を set コンテナ passed に格納して（30、37行目）、最後に passed の要素数を確認します（39行目）。
全体的にすっきりと書けています。また、ビット全検索よりも少ない実行時間（約5分の1）で判定することができました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int h, w;
cin >> h >> w;
vector<vector<int>> a(h, vector(w, 0));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> a[i][j];
}
}
int result = 0;
vector<int> dir;
for (int i = 0; i < w - 1; ++i) {
dir.push_back(0);
}
for (int i = 0; i < h - 1; ++i) {
dir.push_back(1);
}
do {
int now_h = 0;
int now_w = 0;
set<int> passed;
passed.insert(a[now_h][now_w]);
for (int i = 0; i < (h + w - 2); ++i) {
if (dir[i] == 0) {
++now_w;
} else {
++now_h;
}
passed.insert(a[now_h][now_w]);
}
if (passed.size() == h + w - 1) {
++result;
}
} while (next_permutation(dir.begin(), dir.end()));
cout << result << endl;
return 0;
}どちらも、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC293C）
Python では、itertools.combinations を使いました。要素数 H + W – 2 個のリスト dir を定義します。それを参照して、次の組み合わせ v を求めて、マスの移動に使います（10、11、17行目）。
"""AtCoder Beginner Contest 293 C"""
import itertools
h, w = map(int, input().split())
a = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
a[i] = list(map(int, input().split()))
result = 0
dir = [i for i in range(h + w - 2)]
for v in itertools.combinations(dir, h - 1):
now_h = 0
now_w = 0
passed = set()
passed.add(a[now_h][now_w])
for i in range(h + w - 2):
if i in v:
now_h += 1
else:
now_w += 1
passed.add(a[now_h][now_w])
if len(passed) == h + w - 1:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
この問題は、コンテスト中に解けませんでした。
組み合わせを使うことは分かっていましたが、制約の最大値 218 通りを 1018 通りと勘違いして、計算量を下げることができずに時間切れしました。結果的には、218 通りの全検索でも間に合いました。
組み合わせとしての最大の通り数 18C9（=48620通り）が、入力例2で示されていました。解いている人へのヒントになっていました。ひどい勘違いをしていました。
引き続き ABC の問題を紹介していきます。
