AT_abc035_b [ABC035B] ドローン

[problemUrl]: https://atcoder.jp/contests/abc035/tasks/abc035_b 無限に広い二次元グリッドの原点 $ (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 $ 点が得られる。 ### Sample Explanation 1 \- ドローンが最終的にいる可能性がある位置は $ (-2,1),\ (-1,0),\ (-1,2),\ (0,1) $ の $ 4 $ つです。ドローンと高橋君の距離 $ |x|+|y| $ のうち最大値は $ 3 $ となります。 - このケースは部分点の追加制約を満たします。 ### Sample Explanation 2 \- ドローンが最終的にいる可能性がある位置は $ (1,0),\ (-1,0),\ (0,1),\ (0,-1) $ の $ 4 $ つです。ドローンと高橋君の距離 $ |x|+|y| $ のうち最大値は $ 1 $ となります。 - このケースは部分点の追加制約を満たします。 ### Sample Explanation 3 \- このケースは部分点の追加制約を満たします。 ### Sample Explanation 4 \- このケースは部分点の追加制約を満たしません。