B - ドローン Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

無限に広い二次元グリッドの原点 (0, 0) に高橋君と 1 台のドローンがいます。このドローンは文字列が与えられた時、文字列の先頭から末尾までのそれぞれの文字を 1 つの命令と解釈して順に実行します。命令は以下の 4 種類です。

  • L 現在のドローンの位置を (x, y) として (x-1, y) に移動する
  • R 現在のドローンの位置を (x, y) として (x+1, y) に移動する
  • U 現在のドローンの位置を (x, y) として (x, y+1) に移動する
  • D 現在のドローンの位置を (x, y) として (x, y-1) に移動する

今、ドローンに何らかの命令が与えられ、どこかへと移動しました。高橋君はドローンに送られた命令を表す文字列である S を手に入れたものの、いくつかの箇所は破損し?になり分からなくなってしまいました。ただし、?が元々はL、R、U、Dのいずれかの文字だったことが分かっています。

ドローンと高橋君の距離はドローンの位置を (x,y) としてマンハッタン距離 |x|+|y| で表されます。求める値の種類を表す整数 T が与えられるので、移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、 T=1 ならば最大値を、 T=2 ならば最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

S
T
  • 1 行目にドローンに与えられた命令を表す文字列 S(1≦|S|≦10^5) が与えられる。ここで、 |S| は文字列 S の長さを表す。
  • S はL、R、U、D、?の 5 種類の文字のみからなる。
  • 2 行目に求める値の種類を表す整数 T (1≦T≦2) が与えられる。

出力

  • T=1 ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最大値を 1 行に出力せよ。
  • T=2 ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最小値を 1 行に出力せよ。
  • 改行を忘れないこと。

部分点

この問題には部分点が設定されている。

  • T=1 のデータセットに全て正解した場合 100 点が与えられる。
  • 追加制約のないデータセットに正解した場合、追加で 1 点が与えられ、合計 101 点が得られる。

入力例 1

UL?
1

出力例 1

3
  • ドローンが最終的にいる可能性がある位置は (-2,1), (-1,0), (-1,2), (0,1) の 4 つです。ドローンと高橋君の距離 |x|+|y| のうち最大値は 3 となります。
  • このケースは部分点の追加制約を満たします。

入力例 2

UD?
1

出力例 2

1
  • ドローンが最終的にいる可能性がある位置は (1,0), (-1,0), (0,1), (0,-1) の 4 つです。ドローンと高橋君の距離 |x|+|y| のうち最大値は 1 となります。
  • このケースは部分点の追加制約を満たします。

入力例 3

UUUU?DDR?LLLL
1

出力例 3

7
  • このケースは部分点の追加制約を満たします。

入力例 4

UULL?
2

出力例 4

3
  • このケースは部分点の追加制約を満たしません。