公式

A - 数直線上の出会い / Meeting on a Number Line 解説 by MMNMM


初心者の方へ

この問題は、時刻 \(1,\) 時刻 \(2,\ldots,\) 時刻 \(T\) における高橋君・青木君のそれぞれの座標を計算し、同じ座標にいる時刻がいくつあるかを数えることで解くことができます。

座標を計算するときには、毎回初期位置から計算するのではなく、直前の時刻における座標をもとにすることで十分高速にすべての時刻における座標を計算することができます。

実装例は以下のようになります。

#include <iostream>
using namespace std;

int main() {
    int T, X, Y;
    string A, B;
    cin >> T >> X >> Y >> A >> B;

    int ans = 0;
    for (int i = 0; i < T; ++i) { // それぞれの時刻について
        // 直前の座標から移動する
        X += A[i] == 'L' ? -1 : A[i] == 'R' ? 1 : 0;
        Y += B[i] == 'L' ? -1 : B[i] == 'R' ? 1 : 0;

        // 座標が一致していたら答えを増やす
        if (X == Y) {
            ans += X == Y;
        }
    }

    cout << ans << endl;
    return 0;
}
T, X, Y = map(int, input().split())
A = input()
B = input()

ans = 0
for a, b in zip(A, B): # それぞれの時刻について
    # 直前の座標から移動する
    X += -1 if a == 'L' else 1 if a == 'R' else 0
    Y += -1 if b == 'L' else 1 if b == 'R' else 0
    
    # 座標が一致していたら答えを増やす
    if X == Y:
        ans += 1

print(ans)

投稿日時:
最終更新: