公式
A - 数直線上の出会い / Meeting on a Number Line 解説
by
A - 数直線上の出会い / Meeting on a Number Line 解説
by
MMNMM
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
この問題は、時刻 \(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)
投稿日時:
最終更新:
