AtCoder

ABC294 E問題(2xN Grid)を解く

AtCoder_ABC294_E

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

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

E問題 2xN Grid(Difficulty : 792)

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

ABC294 E問題 2xN Grid

二つのデータ列を比較しながら解く問題です。AtCoder Problems による Difficulty は 792 でした。

解答案

マス目の長さ $L$ の制約が $1 \leqq L \leqq 10^{12}$ となっているため、1マスづつ比較する方法では間に合いません。上の列(v1、L1)も下の列(v2、L2)も連長圧縮されているため、圧縮された情報から解答を求めます。

C++ プログラム例(ABC294E)

変数の定義を以下とします。

  • 連長圧縮データの境目までの距離: remain_n1、remain_n2
  • 参照している連長圧縮データのインデックス: cur_n1、cur_n2
  • いま見ているマス目:cur_p
  • 解答(一致しているマス目の数): result

remain_n1 と remain_n2 の大きさの関係によって、以下の処理を行います。

  • remain_n1 の方が少ない:続きは、上の列の次の連長圧縮のデータを参照する。
  • remain_n2 の方が少ない:続きは、下の列の次の連長圧縮のデータを参照する。
  • 等しい場合:続きは、上の列も下の列も次の連長圧縮のデータを参照する。

L1とL2は、L1[n1]またはL2[n2]とアクセスする場合があるため、配列の領域を1個余分に確保しています(12、17行目)。

参照する変数が多いため、プログラムは長くなりましたが、上の条件分岐をそのままコードに変換しています。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int main()
{
	ull L;
	int n1, n2;
	cin >> L >> n1 >> n2;
	vector<int> v1(n1);
	vector<ull> L1(n1 + 1);
	for (int i = 0; i < n1; ++i) {
		cin >> v1[i] >> L1[i];
	}
	vector<int> v2(n2);
	vector<ull> L2(n2 + 1);
	for (int i = 0; i < n2; ++i) {
		cin >> v2[i] >> L2[i];
	}

	ull result = 0;
	ull cur_pos = 0;
	int cur_n1 = 0;
	ull remain_n1 = L1[0];
	int cur_n2 = 0;
	ull remain_n2 = L2[0];
	while (cur_pos < L) {
		if (remain_n1 < remain_n2) {
			cur_pos += remain_n1;
			if (v1[cur_n1] == v2[cur_n2]) {
				result += remain_n1;
			}
			remain_n2 -= remain_n1;
			++cur_n1;
			remain_n1 = L1[cur_n1];
		} else if (remain_n1 > remain_n2) {
			cur_pos += remain_n2;
			if (v1[cur_n1] == v2[cur_n2]) {
				result += remain_n2;
			}
			remain_n1 -= remain_n2;
			++cur_n2;
			remain_n2 = L2[cur_n2];
		} else {
			cur_pos += remain_n1;
			if (v1[cur_n1] == v2[cur_n2]) {
				result += remain_n1;
			}
			++cur_n1;
			remain_n1 = L1[cur_n1];
			++cur_n2;
			remain_n2 = L2[cur_n2];
		}
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC294E)

Python は、C++ のプログラムを移植しました。

"""AtCoder Beginner Contest 294 E"""
L, n1, n2 = map(int, input().split())
v1 = [0] * n1
L1 = [0] * (n1 + 1)
for i in range(n1):
    v1[i], L1[i] = map(int, input().split())
v2 = [0] * n2
L2 = [0] * (n2 + 1)
for i in range(n2):
    v2[i], L2[i] = map(int, input().split())

result = 0
cur_pos = 0
cur_n1 = 0
remain_n1 = L1[0]
cur_n2 = 0
remain_n2 = L2[0]
while cur_pos < L:
    if remain_n1 < remain_n2:
        cur_pos += remain_n1
        if v1[cur_n1] == v2[cur_n2]:
            result += remain_n1
        remain_n2 -= remain_n1
        cur_n1 += 1
        remain_n1 = L1[cur_n1]
    elif remain_n1 > remain_n2:
        cur_pos += remain_n2
        if v1[cur_n1] == v2[cur_n2]:
            result += remain_n2
        remain_n1 -= remain_n2
        cur_n2 += 1
        remain_n2 = L2[cur_n2]
    else:
        cur_pos += remain_n1
        if v1[cur_n1] == v2[cur_n2]:
            result += remain_n1
        cur_n1 += 1
        remain_n1 = L1[cur_n1]
        cur_n2 += 1
        remain_n2 = L2[cur_n2]

print(result)

こちらも「AC」と判定されました。

最後に

コンテストで初めてE問題が解けました。結果的に Difficulty は高くない問題でしたが、解けた瞬間は、うれしく感じました。

引き続き ABC に挑戦して、解説記事を書いていくつもりです。

COMMENT

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

CAPTCHA