printデバッグを入れる位置で混乱していませんか？

お久しぶりです。宇宙意志です。

今回はいつものように書き捨てのSeleniumではなく、ABC152-C問題を見ていきたいと思います。別にリングフィット購入の自動転売で大儲けしようとしたのにLambdaが動かなくてキレていた訳ではないです。

今回の趣旨ですが考え方とデバッグの位置を說明です、まだTLE（時間切れ）で解けていません。

問題の概要

１．N個の順列がバラバラに並んでいます
２．前からiを走査させます
３．走査中のiよりも手前にある順列全て（ここではjと定義されてます）と比較して、~~j!>=i!~~ j>=iが常に成立するならi １つに付き１カウント
４．条件が成立するiの合計カウントを求める

という問題です。

解法の考え方

１．まずこの問題を聞いた時に、2重for文を使って配列のiの位置を記憶させて、
　jを配列として左端からiの位置まで走査すれば良いな、というのはすぐに思いつくと思います。

２．順列の並べ替え
　ここもすぐに気付かなければなりません。この問題はタイムアウトを狙っています。ですから、
　順列は常に　n >= m の時常に n! >= m!　が成立するので、n>mの確認をすれば順列を計算する必要はないと分かります。
　これで問題は単なる大小比較になりました。ここで順列の計算を始めると大量にTLE（時間切れ）が出てしまいます。

　@mui_nyan さまからコメントでご指摘が合ったためyoutubeの解説動画で確認しました。順列という言葉に
　特に意味はなく、普通の順番のランダムの数値という事のようです。申し訳ございませんでした。
　（2020/03/24 15:56 修正）

　また、j用の配列を左端からiまでを走査する時、途中で条件不成立ならbreakさせよう。（TLEを避けるため）
　というのも思いつきます。

３．いつカウントを加えればいいの？
　これについて考えなければなりません。
　jの配列を全て比較し終わった時に条件不成立ならcount++したい。という事は、
　j用のfor分をぐるぐる回してバターになっている時はcountはいじれない。
　最後に加えたい。という事は、フラグ（良い名前をつけましょう）を使って保持して、
　for文が終わった時点でcount++するかしないか判定すれば良い。
　
　ここまで分かれば解けたも同然です。
　解けたも同然というのは内心的効果意思であって、解けたという事実を示したものでありません。（民法）

以下、コメントを入れたソースを見ていきましょう。

import java.io.*;
import java.util.*;

public class Main {

    void submit() {

        int N = nextInt();
        int[] P = new int[N];

        for(int i=0; i<N; i++){
            P[i] = nextInt();
        }

上は入力値を入れてるだけですね。~~順列にする必要がないのは上記で説明した通りです。~~

        int total = 1;

        if(N==1){
            out.println(total);
            return;
        }

最初に与えられた総数が1の時は特別で、i,jと2重配列を作りようがないのです。
こういう所で無理してネストを増やしてがんばってはいけません。
ソースを見やすくします。最初に貰った数値が１つだけの時はreturnして終了させて、ネストを減らします。

※以下のソースコードは解法の追記で書き直しています

        for(int i=1; i<N; i++){
            /*** big_flgとかいう分かりにくい名前はやめて、リーダブルコードを読みましょう！！！ ***/
            boolean big_flg= true;

            /*** jを走査しています。i以下を比較する配列なので、初期位置は int j=0になります ***/
            for(int j=0; j<=i; j++){

                /*** 今回見て欲しいデバッグ部分１です。比較対象になる整数を全て出力しています。 ***/
                out.println("P[i]: "+ P[i]);
                out.println("P[j]: "+ P[j]);

                if(P[i]<=P[j]){
                    big_flg = true;
                }else{
                    big_flg = false;
                    /*** 計算量を減らすために、駄目だと分かり次第breakして２重ループを抜けて次のiに進みます。
　　　　　　　　　　　　　  ちなみにcontinueも処理とネスト減らしの為によく使います ***/
                    break;
                }
            }

大体コメントに書いたのですが、for文の２重配列で比較しているだけです。で、問題は、「エラーが出た時どうすれば良いのかわからないよドラえもん！」という方です。

今回記載しているように、常にデバッグ値は急いでいても、「"名前：数値」という形で出してあげましょう。

out.println("P[i]: "+ P[i]);
out.println("P[j]: "+ P[j]);

このように書く事で、いわゆるprintデバッグの精度を上げる事が出来ます。

            /*** 今回見て欲しいデバッグ部分２です。結局出てきた時のフラグはどっちなの？　成立？　不成立？を見ています ***/
            out.println("big_flg: "+ big_flg);                    

            if(big_flg){
                total++;
            }

        }
        out.println(total);
    }

で、のび太さんはまたデバッグする時にどこでデバッグするの？どの位置でフラグの値を知りたいの？という事が重要です。
これに関しては一言でいうと、if文の前に入れましょう。大体if文に入る前に間違ってます。

printデバッグはどこに入れれば良いのか

二重for文で実装時に間違えるケースはそんなに多くなくて、

１．forの境界値で間違えてる
２．if文の条件が間違えてる
３．if文に入るフラグが間違えてる

の３つです。１．２は余程複雑な条件でなければすぐに気付きます。
そもそも複雑な条件は作ってはいけません。
だから３です。C問題が解けない方は、３のデバッグの仕方を鍛えましょう、と言っています。

以下はトップコーダーのパクリなのでおまじない。気にしません。わたしのソースにSystem.out.println()ではなく、
out.println()で出力しているのはこのおまじないによります。

    void preCalc() {

    }

    void stress() {

    }

    void test() {

    }

    Main() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        preCalc();
        submit();
        //stress();
        //test();
        out.close();
    }

    static final Random rng = new Random();

    static int rand(int l, int r) {
        return l + rng.nextInt(r - l + 1);
    }

    public static void main(String[] args) throws IOException {
        new Main();
    }

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }

    long nextLong() {
        return Long.parseLong(nextToken());
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
}

まとめたソースは以下。

ちなみにこれでもTLEになりますた😭　ボスケテ

abc152_c.java

import java.io.*;
import java.util.*;

public class Main {

    void submit() {

        int N = nextInt();
        int[] P = new int[N];

        for(int i=0; i<N; i++){
            P[i] = nextInt();
        }

        int total = 1;

        if(N==1){
            out.println(total);
            return;
        }

        for(int i=1; i<N; i++){
            boolean big_flg= true;
            for(int j=0; j<=i; j++){
                //out.println("P[i]: "+ P[i]);
                //out.println("P[j]: "+ P[j]);
                if(P[i]<=P[j]){
                    big_flg = true;
                }else{
                    big_flg = false;
                    break;
                }
            }
            //out.println("big_flg: "+ big_flg);                    
            if(big_flg){
                total++;
            }
        }
        out.println(total);
    }

    void preCalc() {

    }

    void stress() {

    }

    void test() {

    }

    Main() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        preCalc();
        submit();
        //stress();
        //test();
        out.close();
    }

    static final Random rng = new Random();

    static int rand(int l, int r) {
        return l + rng.nextInt(r - l + 1);
    }

    public static void main(String[] args) throws IOException {
        new Main();
    }

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }

    long nextLong() {
        return Long.parseLong(nextToken());
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
}

という訳で、今回は以上です。

最期に

java8で回答された優秀な方の解法がたんまりありますので、table右側の詳細で見てみて下さい。
https://atcoder.jp/contests/abc152/submissions?f.Task=abc152_c&f.Language=3016&f.Status=AC&f.User=

今回は以上になります。
・デバッグの位置に気を遣おうね
・名前は表示しようね
という２点でした。

それでは、また会いましょう。

解法の追記（2020/03/24 15:57）

数時間ぶりにお久しぶりです。宇宙意志です。
@swordone さまより (i番目までの最小値)>(i+1番目の値)の個数を数えれば済むというアドバイスを頂きましたので、
解説動画も見て確認しました。上記の手法だとTLEしないという事です。という事で実装しました。

min を保持して、そこから走査すれば計算量が減らせるという事です。以下のようになります。

        int min=P[0];
        for(int i=1; i<N; i++){
            if(min >= P[i]){
                min = P[i];
                count++;
            }
        }
        out.println(count);
    }

大分スッキリしましたね！　これがパッと思いつけば良いんですが、本番では工夫せずに素直に実装してTLEを出してしまうのが筆者の実力という事でしょうか……ぴえん😭

という事で、コメント頂いたお二人の方、ありがとうございました！

追々記（2020/03/24 20:30）

java用にソースのシンタックスハイライト(今知った)を修正して頂きました！　@altさま、ありがとうございます！😭