プログラミング

【競プロ】Javaでやるときの備忘

競技プログラミングをJavaではじめました。間違った問題の備忘とかを書いておく。週末更新する。

データの読み込み

Scannerを使うとコマンドラインからデータを与えられる。

// 一行で読み込んで分割する
Scanner scan = new Scanner(System.in); int i = scan.nextInt(); long l = scan.nextLong(); String[] s = scan.nextLine().split(" ");

// 1つ1つとる(型ごとに用意されている)
scan.next();//String型
scan.nextInt();
scan.nextDouble();
scan.nextBigDecimal();
scan.nextFloat();

// 以下のようにfor文でとった入りする。
int[] ai = new int[M];
for(int i=0; i<M;++i)ai[i]=scan.nextInt();

データ型の最大サイズに気を付ける

アルゴリズムは合っていても、データ型を使い間違えると当然だが間違いとなる。結果がTLEやWAとなったりで原因に気付けなかった。intかlongかは注意。ABC193のCでこの手のミスをしてしまった。以下のnをintとしてしていてTLE・WAとなった。

Scanner scan = new Scanner(System.in);
    long n = scan.nextLong();
    Set<Integer> set = new HashSet<>();
    for(int i=2; i<=n; ++i) {
      if(set.contains(i))continue;
      int result = i;
      while(result<=n) {
        result = result*i;
        if(result<=n) {
          set.add(result);
        }
      }
    }
    System.out.println(n-set.size());

20210417までに知ったこと

DP(動的計画法)を学ぶ

ABC129Cにて出会う。

ai[i]=ai[i+1]+ai[i+2]といった漸化式に落とし込める場合に有効。また頭を切り替える必要があり、階段の最上段を「1」とした場合、階段の0段目はどうかという、ゴールから求めるという発想が必要となる。(自分にはなかった)

少数部分を求める

double型の少数部分だけほしいと思った場合のやりかた。

// 整数部分を引く
double data = 1.0583;
double syousuu = data - (int)data;
System.out.println(syousuu);

二つの数値のうち、大きい方を返す、小さい方を返す。(便利)

double max = Math.max(5, 4);
System.out.println(max);//5
double min = Math.min(5,4);
System.out.println(min);//4

レートの変化(2021/01-04)

ABCのABが解けるようにはなってきた。Cは問題によるという状態。アルゴリズムの武器がないため全探索してTLEになって終了という結果になってしまう。