[ARC162] A - Ekiden Race

[Q] https://atcoder.jp/contests/arc162/tasks/arc162_a

・問題の読み方

20
13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17

往路で1位だった人が、総合13位だった。
往路で2位だった人が、総合2位だった。
往路で3位だった人が、総合7位だった。
往路で4位だった人が、総合1位だった…
と読む。

・考察
総合成績が良かった順に見ていこうと思う。
順位がよくなった人ほど、復路タイムがよいはずだからだ。

総合1: 往路4 // ★ この人がいると、往路1~3位の人は復路賞は取れないことがわかる。
総合2: 往路2 // 往路2位なのでダメ。
総合3: 往路7 // ★ 往路7位よりよかった人は復路賞が取れない。
総合4: 往路8 // ★ 往路8位よりよかった人は復路賞が取れない。
総合5: 往路5 // ダメ
総合6: 往路12 // ★ 
総合7: 往路3
総合8: 往路13 // ★
総合9: 往路6
総合10: 往路10
総合11: 往路19 // ★
総合12: 往路9
総合13: 往路1
総合14: 往路14
総合15: 往路11
総合16: 往路16
総合17: 往路20 // ★
総合18: 往路18
総合19: 往路17
総合20: 往路15

総合順位の良い人順に見て行って、往路の悪い順位が更新された人の数が解答になる。

・実装

int main() {
  ll T;
  cin >> T;

  rep(_t, T) {
    ll N;
    cin >> N;
    vector<ll> V(N);
    rep(i, N) {
      ll a;
      cin >> a;
      --a;
      V[a] = i;  // V[総合順位] = 往路順位
    }
    ll ans = 0;
    ll pre = -1; // 往路順位が最も悪かった値をメモ
    rep(i, N) {
      if (pre < V[i]) { // 往路順位の更新をした人が、復路賞の対象者
        pre = V[i];
        ++ans;
      }
    }
    cout << ans << endl;
  }
}

https://atcoder.jp/contests/arc162/submissions/42720036