AtCoder Beginner Contest 152 C - Low Elements
修論を書き上げるため競プロのペースが落ち気味の、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc)にて開催されました、AtCoder Beginner Contest 152 C問題「C - Low Elements」の問題と僕との戦闘記です。
0.はじめに
1.問題文
1 , … , N の順列 P_1 , … , P_N が与えられます。 次の条件を満たす整数 i ( 1 ≤ i ≤ N ) の個数を数えてください。
任意の整数 j ( 1 ≤ j ≤ i ) に対して、 P_i ≤ P_j
2.制約
- 1 ≤ N ≤ 2 × 105
- P_1 , … , P_N は 1 , … , N の順列である。
- 入力はすべて整数である。
3.入力例
- 入力
8 5 7 4 2 6 8 1 3
- 出力
4
4.初見の感想
- 2×105の計算量なのでO(N2)は厳しい
5.学びポイント
- 問題を言い換えると、数列の中で最後の数字が最小値であれば条件を満たす
- for文で前から見ていって、最小値を更新していき更新回数を数えていく
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main(string[] args) { int N = int.Parse(Console.ReadLine()); string[] input = Console.ReadLine().Split(); int[] P = new int[N]; for(int i = 0; i < N; i++) { P[i] = int.Parse(input[i]); } int min = int.MaxValue; int ans = 0; for(int i=0; i < N; i++) { if (min >= P[i]) { min = P[i];ans++; } } Console.WriteLine(ans); } }
7.最後に
この問題が早く解けたので成長を感じます!