AOJ 2730 Line Gimmick (JAG 模擬地区 2015 D) (300 点)

星 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;
}