AtCoder が提供しているABC（AtCoder Beginner Contest）376 B問題をC++とPythonで解いてみました。ABC376は、2024年10月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Hands on Ring (Easy)（Difficulty : 290）
問題の詳細は、リンク先をご覧ください。
ABC376 B問題 Hands on Ring (Easy)
条件分岐を丁寧に実装していきます。AtCoder Problems による Difficulty は 290 でした。
解答案
C++ プログラム例（ABC376B）
以下の8通りに場合分けして処理します。
- $L$ を動かす場合
- $L < T$ の場合
- $L < R < T$ の場合、動く量は、$L+N-T$ となります。
- 上記ではない場合、動く量は、$T-L$ となります。
- $T < L$ の場合
- $T < R < L$ の場合、動く量は、$T+N-L$ となります。
- 上記ではない場合、動く量は、$L-T$ となります。
- $L < T$ の場合
- $R$ を動かす場合
- $R < T$ の場合
- $R < L < T$ の場合、動く量は、$R+N-T$ となります。
- 上記ではない場合、動く量は、$T-R$ となります。
- $T < R$ の場合
- $T < L < R$ の場合、動く量は、$T+N-R$ となります。
- 上記ではない場合、動く量は、$R-T$ となります。
- $R < T$ の場合
上記の分岐を実装したのが、以下のC++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
int L = 1;
int R = 2;
int result = 0;
for (int i = 0; i < q; ++i) {
char h;
int t;
cin >> h >> t;
if (h == 'L') {
if (L < t) {
if ((L < R) && (R < t)) {
result += L + n - t;
} else {
result += t - L;
}
} else {
if ((t < R) && (R < L)) {
result += t + n - L;
} else {
result += L - t;
}
}
L = t;
} else {
if (R < t) {
if ((R < L) && (L < t)) {
result += R + n - t;
} else {
result += t - R;
}
} else {
if ((t < L) && (L < R)) {
result += t + n - R;
} else {
result += R - t;
}
}
R = t;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC376B）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 376 B"""
n, q = map(int, input().split())
L = 1
R = 2
result = 0
for i in range(q):
h, t = input().split()
t = int(t)
if h == 'L':
if L < t:
if L < R < t:
result += L + n - t
else:
result += t - L
else:
if t < R < L:
result += t + n - L
else:
result += L - t
L = t
else:
if R < t:
if R < L < t:
result += R + n - t
else:
result += t - R
else:
if t < L < R:
result += t + n - R
else:
result += R - t
R = t
print(result)こちらも「AC」と判定されました。
最後に
この問題は、実装が面倒に感じて後回しにしました。このような問題を素早く解くこともレート向上には必要かもしれません。
引き続き ABC の問題を紹介していきます。
