AtCoder

ABC293 C問題(Make Takahashi Happy)を解く

AtCoder_ABC293_C

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で示されていました。解いている人へのヒントになっていました。ひどい勘違いをしていました。

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

COMMENT

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

CAPTCHA