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さま、ありがとうございます！😭