星 1 個ついてるし、面白かった。「予想」を正しく立てられるかどうかがポイント。最初はカッコ列系の考察するのかと思って迷走した。
問題概要
>><><<<
みたいな文字列が与えられる。最初にどこを踏んでも良い。踏んだパネルは消えて、その矢印の方向に突き進む。突き進んで場外に出るまでに踏むパネルの枚数を最大化せよ。
制約
解法
通り全部試すような解法は間に合わない。
カッコ列系の問題かとも思ったけど、微妙に違う。
ちょっとよく考えてみると
> ... <
で囲われているものは、必ず、全部消費した上でどちら向きにも放出できることがわかる (示そうと思えば数学的帰納法で示せる)。
よって、
- ... [>...] (左から見て最初の「>」から右全部)
- [...<] ... (右から見て最初の「<」から左全部)
のうち長い方を採用すればよい。
#include <iostream> #include <string> using namespace std; int N; string S; int main() { cin >> N >> S; int firstRight = N, lastLeft = -1; for (int i = 0; i < N; ++i) { if (S[i] == '>') firstRight = min(firstRight, i); else lastLeft = max(lastLeft, i); } int res = 0; if (firstRight < N) res = max(res, N - firstRight); if (lastLeft > -1) res = max(res, lastLeft + 1); cout << res << endl; }