【AtCoder Beginner Contest 152 C問題】TLEについてと、printデバッグ位置のコツ
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になりますた😭 ボスケテ
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さま、ありがとうございます！😭
Author And Source
この問題について(【AtCoder Beginner Contest 152 C問題】TLEについてと、printデバッグ位置のコツ), 我々は、より多くの情報をここで見つけました https://qiita.com/contengee/items/b170de766b4573df9608著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .