Paizaの平方分割がタイムアウトになる。

Question

問題リンク

https://paiza.jp/works/mondai/query_primer/query_primer__square_division

現状

現在PaizaにおいてJavaの学習を進めています。

その中で平方分割について学んでおり、「長さ10000の数列Aと3つの区間が与えられ、その区間に置けるそれぞれの最大値を出力する」という問題で実行時間を縮めることができずに困っています。

該当のソースコード

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        int K = sc.nextInt();
        
        int[] array = new int[10000];
        int[] rangeMax = new int[100];
        
        for(int i=0; i<10000; i++){
            array[i] = sc.nextInt();
        }
        
        for(int i=0; i<100; i++){
            int min = -100000;
            int start = i * 100;
            int end = (i + 1) * 100;
            
            for(int j=start; j<end; j++){
                if(array[j] >= min){
                    min = array[j];
                }
            }
            
            rangeMax[i] = min;
        }
        
        for(int i = 0; i < K; i++){
            int left = sc.nextInt() - 1;
            int right = sc.nextInt() - 1;
            int now = left;
            int ans = array[left];
            
            while(now <= right){
                if((now % 100 == 0) & (now + 100 - 1 <= right)){
                    if(ans <= rangeMax[now / 100]){
                        ans = rangeMax[now / 100];
                    }
                }
                else{
                    if(ans <= array[now]){
                        ans = array[now];
                        now++;
                    }
                }
            }
            
            System.out.println(ans);
        }
    }
}

Comments

[meg_]

> ランタイムエラーになる。
> 実行時間を縮めることができずに困っています。
エラーなのですか？タイムアウトなんですか？？

[jimbe]

平方分割ならせめてルートは使ったほうが良いのでは。
いくら例が 10000 件だからと言って 100 をベタ書きしては「『平方分割』を学ぶプログラム」としてはそもそもダメな気がしますが。

[takuma0306]

meg_さん。
タイムアウトになってしまいます。

[takuma0306]

jimbeさん。
アドバイスありがとうございます。
修正します！

[meg_]

> タイムアウトになってしまいます。
そうであればタイトルが紛らわしいので修正された方が良いかと思います。

[takuma0306]

タイトル修正しました。

Answer 1

最後のwhile文ですが

            while(now <= right){
                if((now % 100 == 0) & (now + 100 - 1 <= right)){
                    if(ans <= rangeMax[now / 100]){
                        ans = rangeMax[now / 100];
                    }
                    // ※※ここ
                }
                else{
                    if(ans <= array[now]){
                        ans = array[now];
                        now++;
                    }
                    // ※※ここの省略されたelse
                }
            }

コメントを入れた分岐では now も right も書き換えられず、1度でもそこに入ったら無限ループするのではないでしょうか？

Comments

[takuma0306]

pecmmさん！
ありがとうございます。
解決できました！

Answer 2

36～48行目の while は now の加算が if の奥深くに 1 つあるだけですけど、どのような場合でもちゃんとループが終わるでしょうか?

---

1 つのループ内でイロイロ判断するよりも 3 つに分けてやったほうが分かり易い気がします。

import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);

    int n = 10000;

    int k = sc.nextInt();

    int[] a = new int[n];
    int x = (int)Math.sqrt(n);
    int[] r = new int[x+1]; //+1 は最期の x 個に満たない分用. 不使用

    for (int i=0, ii=0; i<n; ii++) {
      r[ii] = Integer.MIN_VALUE;
      for (int j=0; j<x && i<n; i++, j++) {
        a[i] = sc.nextInt();
        r[ii] = Math.max(r[ii], a[i]);
      }
    }

    for (int i=0; i<k; i++) {
      int s = sc.nextInt() - 1; //含む
      int e = sc.nextInt(); //含まない

      int rs = (s+x-1) / x; //含む
      int re = e / x; //含まない

      int v = Integer.MIN_VALUE;
      if(rs >= re) {
        v = max(a, s, e, v);
      } else {
        v = max(a, s, rs*x, v);
        v = max(r, rs, re, v);
        v = max(a, re*x, e, v);
      }
      System.out.println(v);
    }
  }
  //配列 a のインデックス s (含む)から e (含まない)の範囲の値と v のうちの、最大値を返す
  private static int max(int[] a, int s, int e, int v) {
    for(int i=s; i<e; i++) v = Math.max(v, a[i]);
    return v;
  }
}

Comments

[takuma0306]

jimbeさん！
ありがとうございます。
自分で書いたコードよりはるかに見やすく、わかりやすいです！

[jimbe]

すみません、バグがありました。
1 つは、 s～e の範囲に e が含まれていませんでした。
もう 1 つは、常に3つのループをするようでは例えば x=100 の時の s=10, e=20 のように x の 1 つの範囲に収まる場合に rs=1, re=0 となり、 1 つ目のループで 10～100、3 つ目のループで 0～20 を対象にしてしまいます。rs と re の関係によっては単純に s～e をループするようにしました。