プログラミングを上達させたい

情報学専攻の大学院→放送局でCMの営業など@大阪→舞台俳優&IT営業@東京

競プロのときにはintの範囲に気を付けなアカンでホンマ

先週のAtCoderGrandContest029での成績が悪く水色から緑色に落ちてしました。
A問題を解くアルゴリズムは分かったものの、途中でとある変数の値がintの範囲外に出ることに気づかず30分以上時間を無駄にしたのが原因です。
しかもそれが悔しいからと過去問を解いていたら、またも同じようなミスでめちゃ手間取りました。
自分に「intの範囲に気を付けろ」という精神を根付かせるため、このエントリを書きます。

Javaにおけるint、longの範囲のおさらい

intは-2147483648~2147483647⇒ざっくり、2 * 10^9まで

longは-9223372036854775808~9223372036854775807
⇒ざっくり、9* 10^18まで

きっかけとなった問題

こちらです。
atcoder.jp

アルゴリズムは割愛します。
入力される文字列の長さは2 * 10^5と、そんなに大きくありません。
ただ、これは2乗すると4 * 10^10となり、十分intの範囲を超える数になります。
アルゴリズムに関して、「実行時間のオーダー」「メモリ使用量のオーダー」などは気にしているつもりですが、「答えの数値のオーダー」も今後は意識すべきだと痛感しました。

ちなみに最終的にACとなったコードはこんな感じ。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
 
    String str = sc.nextStr();
    int n = str.length();
    int[] ns = new int[n];
 
    long count = 0;
    long ans = 0; //これをlongにしなきゃいけなかった!!!!!!!
    for(int i = 0; i < n; i++){
      if(str.charAt(i) == 'B'){
        count++;
      }else{
        ans += count;
      }
    }
 
    System.out.println(ans);
 
  }
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}

さらにもう1問

復習しようと思い解いていてつまづいたのがこの問題でした。いつもならすぐ解けるハズの300点の問題です。
atcoder.jp

こちらもアルゴリズムの解説は割愛します。

これも自信満々のコードがWA、そして解答となる変数をlongにしてもまだWA・・・と途方に暮れていました。
ただ、今回に関しても結局途中で出てくるint型の変数がintの範囲を超えていたのが問題でした。

具体的には、

    long firstlengths = ans;
 
    for(int i = 1; i < n - 1; i++){
      long nowlen = firstlengths - (long)((nums[i] - nums[i - 1]) * (n - i));
      ans += nowlen;
      firstlengths = nowlen;
 
    }

というコードにおいて、そもそも

(nums[i] - nums[i - 1]) * (n - i)

がintの範囲を超えるケースがあったのです。
このように書き直したらACとなりました。

long nowlen = firstlengths - (long)(nums[i] - nums[i - 1]) * (long)(n - i);

最終的なコードはこんな感じ。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++){
      nums[i] = sc.nextInt();
    }
 
    Arrays.sort(nums);
 
    long ans = 0;
    for(int i = 1; i < n; i++){
      ans += (long)(nums[i] - nums[0]);
    }
 
    long firstlengths = ans;
 
    for(int i = 1; i < n - 1; i++){
      long nowlen = firstlengths - (long)(nums[i] - nums[i - 1]) * (long)(n - i);
      ans += nowlen;
      firstlengths = nowlen;
 
    }
 
    System.out.println(ans);
 
 
  }
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}


今後は計算の途中経過で変数がどれくらいの大きさになっているかも意識して解いていけたらと思います。
何より、こんなんで躓くのはとても悔しい・・・!
気を引き締めていきます。
以上です。