問題
要約
- 無限に広い二次元グリッドの原点(0,0)に高橋君とドローンがいる。
- ドローンは文字列Sに従って移動します。Sは'L'(左)、'R'(右)、'U'(上)、'D'(下)の4種類の命令からなる。
- Sの一部が'?'に破損しています。'?'は元々L、R、U、Dのいずれか。
- ドローンの最終位置(x,y)と高橋君(0,0)との距離は、マンハッタン距離|x|+|y|で表される。
- 整数Tが与えられ、T=1の場合は可能な最大距離を、T=2の場合は可能な最小距離を求める。
変数情報：
- S: ドローンへの命令を表す文字列（一部が'?'に破損）
- T: 求める値の種類を表す整数（1または2）
既存投稿一覧ページへのリンク
独り言
不意打ちで難しい問題やって時間潰すのも楽しいけど着実に勉強していこうと思って、diff値に従って学習中。
2016年の問題ってレベルBでもdiff804あるんだ。
まぁ、やっぱり競技プログラム参加者のレベルが爆上がりしているんでしょうね。
予想だけど、若い参加者がメチャクチャレベルを押し上げてる気がする。
私も、今が学生の頃だったら、かなり高い確率でガチ勢になってただろうし。
アプローチ
ドローンの移動を追跡し、'?'の数をカウントしながら最終位置を計算。
その後、'?'の影響を考慮して最大距離または最小距離を求める。
解法手順
-
入力文字列Sと整数Tを受け取る。
-
ドローンの現在位置を表す変数nowを[0, 0]で初期化する。
-
'?'の数をカウントする変数cntを0で初期化する。
-
Sの各文字について以下の処理を行う：
- 'L'なら、nowのx座標を1減少させる。
- 'R'なら、nowのx座標を1増加させる。
- 'U'なら、nowのy座標を1増加させる。
- 'D'なら、nowのy座標を1減少させる。
- '?'なら、cntを1増加させる。
-
nowの座標から原点(0,0)までのマンハッタン距離distを計算する。
-
Tの値に応じて以下の処理を行う：
- T=1（最大距離）の場合、distにcntを加算する。
- T=2（最小距離）の場合、distからcntを減算する。
- もしdistが負になった場合、distを2で割った余りを取る。
-
最終的なdistを出力する。
ACコード
ac.py
def solve(S, T):
# 移動方向と対応する座標変化を定義
order = ["L", "R", "U", "D", "?"]
direction = [[-1, 0], [1, 0], [0, 1], [0, -1]]
# 2. ドローンの現在位置を表す変数nowを[0, 0]で初期化する
now = [0, 0]
# 3. '?'の数をカウントする変数cntを0で初期化する
cnt = 0
# 4. Sの各文字について処理を行う
for i in range(len(S)):
if S[i] == order[0]: # 'L'の場合
now[0] += direction[0][0]
now[1] += direction[0][1]
if S[i] == order[1]: # 'R'の場合
now[0] += direction[1][0]
now[1] += direction[1][1]
if S[i] == order[2]: # 'U'の場合
now[0] += direction[2][0]
now[1] += direction[2][1]
if S[i] == order[3]: # 'D'の場合
now[0] += direction[3][0]
now[1] += direction[3][1]
if S[i] == order[4]: # '?'の場合
cnt += 1
# 5. nowの座標から原点(0,0)までのマンハッタン距離distを計算する
dist = abs(now[0]) + abs(now[1])
# 6. Tの値に応じて処理を行う
if T == "1": # 最大距離の場合
dist += cnt
else: # 最小距離の場合
dist -= cnt
if dist < 0:
dist %= 2
# 7. 最終的なdistを出力する
print(dist)
if __name__=="__main__":
# 1. 入力文字列Sと整数Tを受け取る
S = input()
T = input()
solve(S, T)
机上トレース
入力例3
-
入力文字列Sと整数Tを受け取る。
S = UUUU?DDR?LLLL
T = 1 -
ドローンの現在位置を表す変数nowを[0, 0]で初期化する。
-
'?'の数をカウントする変数cntを0で初期化する。
-
Sの各文字について以下の処理を行う：
- 'L'なら、nowのx座標を1減少させる。
(0,0) -> (-4,0) - 'R'なら、nowのx座標を1増加させる。
(0,0) -> (-3,0) - 'U'なら、nowのy座標を1増加させる。
(0,0) -> (-3,4) - 'D'なら、nowのy座標を1減少させる。
(0,0) -> (-3,2) - '?'なら、cntを1増加させる。
cnt = 2
- 'L'なら、nowのx座標を1減少させる。
-
nowの座標から原点(0,0)までのマンハッタン距離distを計算する。
dist = 5 -
Tの値に応じて以下の処理を行う：
- T=1（最大距離）の場合、distにcntを加算する。
- T=2（最小距離）の場合、distからcntを減算する。
T = 1なので、マンハッタン距離をcnt分加算する。
-
最終的なdistを出力する。
dist = ans = 7