Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

A. Mezo Playing Zoma (Codeforces Round #613 Div. 2)

問題

https://codeforces.com/contest/1285/problem/A

問題概要

あなたは数直線上にいて、現在地はx = 0である。

あなたにはN個の命令が与えられて、Lなら左(x = x - 1)、Rなら右(x = x + 1)に移動しなければならないが、命令を任意に無視することもできる。

N個の命令を受けた後であなたが最終的に取りうる座標の個数はいくつになるか。

解説

Lだけをすべて無視した場合の最終地点はx = Rの個数、Rだけをすべて無視した場合の最終地点はx = Lの個数で、これが上限下限になります。

その間に含まれる位置でとどまることは、その位置についた以降の命令をすべて無視することで可能なので、最終的な答えはLの個数 + Rの個数 + 1(原点の分で+1)となります。

おまけ

考え方としては上記解説で間違ってないと思いますが、解説を書いていて気づいたことがあります。

LとR以外の命令がないので、Lの個数 + Rの個数とはつまりNそのものです。つまりNだけみれば命令を見て数え上げする必要などないのでした。(Editorialの解法もそうなってました。)