AtCoder が提供しているABC（AtCoder Beginner Contest）294 のE問題をC++とPythonで解いてみました。ABC294は、2023年3月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 2xN Grid（Difficulty : 792）
問題はリンク先をご覧ください。
二つのデータ列を比較しながら解く問題です。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 の問題を紹介していきます。
