AtCoder Beginner Contest 152 C - Low Elements

修論を書き上げるため競プロのペースが落ち気味の、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc)にて開催されました、AtCoder Beginner Contest 152 C問題「C - Low Elements」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

1 , … , N の順列 P_1 , … , P_N が与えられます。 次の条件を満たす整数 i ( 1 ≤ i ≤ N ) の個数を数えてください。

任意の整数 j ( 1 ≤ j ≤ i ) に対して、 P_i ≤ P_j

2.制約

• 1 ≤ N ≤ 2 × 10⁵
• P_1 , … , P_N は 1 , … , N の順列である。
• 入力はすべて整数である。

3.入力例

• 入力

8
5 7 4 2 6 8 1 3

• 出力

4

4.初見の感想

• 2×10⁵の計算量なのでO(N²)は厳しい

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.最後に

この問題が早く解けたので成長を感じます！