自分の解説記事内で使用するテンプレートの紹介[～ABC257用]

はじめに

コンテストに参加しているとわざわざ何回も書いたり長いコードを書いたりするのが面倒だなと感じるので、可能な限り簡略化すべく作ったテンプレートを紹介していきたいと思います。

非常に見辛かったりなんでそんなものを･･･？って感じるコードがあったりするかもしれませんが、自分的にこれはこう書きたいなってのを反映した結果だったりするので温かい目で見守っていただけると幸いです(ただ、計算量が大幅に変化するようでしたら指摘していただけると嬉しいです)。
では、見ていきましょう。

インポート

正直テンプレートで書くならimportしなくても良いとは思いますが、まぁテンプレにないものを実装する必要があるときにimportしておいた方が楽なので必要最低限をimportしてあります。

Sample.java

import java.io.*;   //入出力用
import java.util.*; //リスト用
import java.math.*; //BigInteger用

フィールド

取得用としてBufferedReader、出力用としてPrintWriterを使いたいのでフィールドに記述してあります。

Sample.java

//入力用
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//出力用
static PrintWriter pw = new PrintWriter(System.out);

取得系

readInt()

int型の入力値が一行に一個しかない時(Nだけの時など)に使えるメソッドです。

Sample.java

public static int readInt()throws IOException{
    //一列分を受け取ってparseIntで型を変える
    return Integer.parseInt(br.readLine());
}

readLong()

readInt()のlongバージョンです。

Sample.java

public static long readLong()throws IOException{
    //一列分を受け取ってparseLongで型を変える
    return Long.parseLong(br.readLine());
}

read()

readInt()のStringバージョンです。

Sample.java

public static String read()throws IOException{
    //一列分受け取って返す
    return br.readLine();
}

readInt(int n)

整数を空白区切りで取得したときに使うメソッドです(桁数がわかっているとき)。

Sample.java

public static int[] readInt(int n)throws IOException{
    //戻り値用配列
    int[] ans = new int[n];
    //空白区切りで配列に変換
    String[] str = br.readLine().split(" ");
    //一つずつparseIntして格納
    for(int i=0;i<n;i++){
        ans[i] = Integer.parseInt(str[i]);
    }
    return ans;
}

readLong(int n)

readInt(int n)のlongバージョンです。

Sample.java

public static long[] readLong(int n)throws IOException{
    //戻り値用配列
    long[] ans = new long[n];
    //空白区切りで配列に変換
    String[] str = br.readLine().split(" ");
    //一つずつparseLongして格納
    for(int i=0;i<n;i++){
        ans[i] = Long.parseLong(str[i]);
    }
    return ans;
}

reads(String str)

一行をstr区切りで配列にして返します。

Sample.java

public static String[] reads(String str)throws IOException{
    //strで区切って配列にして出力
    return br.readLine().split(str);
}

出力系

print(Object T)

System.out.print()のPrintWriter版です。

Sample.java

public static void print(Object T){
    //PrintWriterを利用
    pw.print(T);
}

println(Object T)

System.out.println()のPrintWriter版です。

Sample.java

public static void println(Object T){
    //PrintWriterを利用
    pw.println(T);
}
public static void println(){
    //PrintWriterを利用
    pw.println();
}

printlnAll(配列か複数の引数かList)

要素ごとに改行して出力します。

Sample.java

public static void printlnAll(int... T){
    //一つずつ出力
    for(int i=0;i<T.length;i++){
        println(T[i]);
    }
}
public static void printlnAll(long... T){
    //一つずつ出力
    for(int i=0;i<T.length;i++){
        println(T[i]);
    }
}
public static void printlnAll(char... T){
    //一つずつ出力
    for(int i=0;i<T.length;i++){
        println(T[i]);
    }
}
public static void printlnAll(byte... T){
    //一つずつ出力
    for(int i=0;i<T.length;i++){
        println(T[i]);
    }
}
public static void printlnAll(Object[] T){
    //一つずつ出力
    for(int i=0;i<T.length;i++){
        println(T[i]);
    }
}
public static void printlnAll(List<?> T){
    //一つずつ出力
    for(int i=0;i<T.size();i++){
        println(T.get(i));
    }
}

printAll(配列かList,String str)

改行無しで、strを間に挟んで全要素を出力します。

Sample.java

public static void printAll(int[] T,String str){
    //一つずつ出力+strを出力
    for(int i=0;i<T.length-1;i++){
        pw.print(T[i]);
        pw.print(str);
    }
    //最後はstrを出力しないように、別途出力
    print(T[T.length-1]);
}
public static void printAll(long[] T,String str){
    //一つずつ出力+strを出力
    for(int i=0;i<T.length-1;i++){
        pw.print(T[i]);
        pw.print(str);
    }
    //最後はstrを出力しないように、別途出力
    print(T[T.length-1]);
}
public static void printAll(char[] T,String str){
    //一つずつ出力+strを出力
    for(int i=0;i<T.length-1;i++){
        pw.print(T[i]);
        pw.print(str);
    }
    //最後はstrを出力しないように、別途出力
    print(T[T.length-1]);
}
public static void printAll(byte[] T,String str){
    //一つずつ出力+strを出力
    for(int i=0;i<T.length-1;i++){
         pw.print(T[i]);
         pw.print(str);
    }
    //最後はstrを出力しないように、別途出力
    print(T[T.length-1]);
}
public static void printAll(Object[] T,String str){
    //一つずつ出力+strを出力
    for(int i=0;i<T.length-1;i++){
        pw.print(T[i]);
        pw.print(str);
    }
    //最後はstrを出力しないように、別途出力
    print(T[T.length-1]);
}
public static void printAll(List<?> T,String str){
    //一つずつ出力+strを出力
    for(int i=0;i<T.size()-1;i++){
        pw.print(T.get(i));
        pw.print(str);
    }
    //最後はstrを出力しないように、別途出力
    print(T.get(T.size()-1));
}

printAllln(配列かList,String str)

printAllの最後に改行します。

Sample.java

public static void printAllln(int[] T,String str){
    //一つずつ出力+strを出力
    printAll(T,str);
    //最後改行
    println();
}
public static void printAllln(long[] T,String str){
    //一つずつ出力+strを出力
    printAll(T,str);
    //最後改行
    println();
}
public static void printAllln(char[] T,String str){
    //一つずつ出力+strを出力
    printAll(T,str);
    //最後改行
    println();
}
public static void printAllln(byte[] T,String str){
    //一つずつ出力+strを出力
    printAll(T,str);
    //最後改行
    println();
}
public static void printAllln(Object[] T,String str){
    //一つずつ出力+strを出力
    printAll(T,str);
    //最後改行
    println();
}
public static void printAllln(List<?> T,String str){
    //一つずつ出力+strを出力
    printAll(T,str);
    //最後改行
    println();
}

flush()

コードの最後に入れてあげると出力ができます。

Sample.java

public static void flush(){
    //PrintWriterのflushを利用
    pw.flush();
}

計算系

gcd(long a,long b)

最大公約数を求めます(ユークリッドの互除法)。

Sample.java

public static long gcd(long a,long b){
    //あまりを格納する変数
    long temp;
    //あまりが0になるまで繰り返す
    while((temp = a % b) != 0){
        a = b;
        b = temp;
    }
    return b;
}

lcm(long a,long b)

最小公倍数を求めます(gcd使用)。

Sample.java

public static long lcm(long a,long b){
    //gcdを利用してlcmを計算
    return a * b / gcd(a, b);
}

isPrime(long num)

(多分)素数であるかを返します(ミラー・ラビン素数判定法)。

Sample.java

public static boolean isPrime(long num){
    //BigIntegerに変換
    BigInteger bi = BigInteger.valueOf(num);
    //ミラーラビン素数判定法を利用(誤判定する確率は1-1/2^20以下)
    return bi.isProbablePrime(20);
}

prime(int num)

numまでの素数をint型配列として返します(エラトステネスの篩)。

Sample.java

public static int[] prime(int num){
    //素数かどうかの情報を格納するset
    BitSet nums = new BitSet(num+1);
    //調べたい分だけtrueにしておく
    nums.set(2,num+1);
    //√nまで模索
    for(int i=2;i<=Math.sqrt(num);i++){
        if(nums.get(i)){ //素数ならその倍数を削除する
            for(int j=i*i;j<=num;j+=i){
                nums.clear(j); //素数ではないのでfalseにする
            }
        }
    }
    //戻り値用配列
    int[] answer = new int[nums.cardinality()];
    //インデックス用変数
    int i=2,index=0;
    //配列全部が埋まるまで繰り返す
    while(true){
        //次の素数を探す(trueになっている箇所を探す)
        i = nums.nextSetBit(i);
        //素数を格納
        answer[index++] = i++;
        //いっぱいになったら終了
        if(index==answer.length) break;
    }
    return answer;
}

pow(long a,long b)

繰り返し二乗法による累乗計算です。

Sample.java

public static long pow(long a,long b){
    long ans = 1;
    while(b>0){
        if((b&1)==1){
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ans;
}

modPow(long a,long b,long mod)

累乗計算した結果をmodで割った値を返します。

Sample.java

public static long modPow(long a,long b,long mod){
    long ans = 1;
    a %= mod;
    while(b>0){
        if((b&1)==1){
            ans *= a;
        }
        ans %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}

その他

parseInt(String str)

大きい値ならInteger.parseInt()よりほんのちょっとだけ速い変換です。

Sample.java

//正負の対策ができていなかったので改良(2022/06/11)
//実行時間に変化はほぼ無いです
public static int parseInt(String str){
    char[] nums = str.toCharArray();
    int ans = 0;
	boolean plus = true;
    if(nums[0]=='-'){
        plus = false;
        nums[0]='0';
    }
    for(int i=0;i<nums.length;i++){
        ans = ans*10 + (int)(nums[i]-'0');
    }
    return plus ? ans:-ans;
}

実行速度検証

実行はAtCoderのコードテストを使いました。実行したコードは以下のコードです。

Test.java

import java.io.*;
class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //試行する数字をString型で受け取る
        String str = br.readLine();
        //10^8回変換してみる
        for(int i=0;i<100000000;i++){
            /*
                Integer.parseInt(str);
                    or
                parseInt(str);
            */
        }
    }
    //自作parseInt
    public static int parseInt(String str){
        char[] nums = str.toCharArray();
        int ans = 0;
        for(int i=0;i<nums.length;i++){
            ans = ans*10 + (int)(nums[i]-'0');
        }
        return ans;
    }
}

10回平均は以下のようになりました。

入力値	Integer.parseInt	自作parseInt
0	234ms	628ms
1000	716ms	624ms
2147483647	1551ms	706ms

0〜1000くらいならparseIntの方が良いか、大差ないって感じですね。1000以下って制約があるならInteger.parseIntを使った方が良いです。
なお、変数に代入を行わないでの実行時間ですので、実際に使うときは+αの時間がかかるということに注意してください。

追記

parseIntの中のansをint型からlong型に変えるだけでparseLongにも変換できます。
こちらもLong.parseLongと比較してみました(10^8回変換にかかる時間の10回平均)。

入力値	Long.parseLong	自作parseLong
0	317ms	623ms
9223372036854775807	3530ms	771ms

AtCoderではここまで大きい数字をこんなに多く受け取ることはないと思いますが(私が知らないだけの可能性も…)、これだけ大きく差がつくので実装しておく価値はあるかと思います。ぜひ、ご参考に。

sort(int[] list)

ヒープソートで実装してあります。int[][]、long[]、long[][]にも対応できるようオーバーロードしてあります(ここにはint[]用のみ記載)。

Sample.java

public static void sort(int[] list){
	for(int i=0;i<list.length;i++){
		int j = i;
		while(j>0&&list[(j-1)/2]<list[j]){
			int temp = list[(j-1)/2];
			list[(j-1)/2] = list[j];
			list[j] = temp;
			j = (j-1)/2;
		}
	}
	for(int i=list.length;i>0;i--){
		int temp = list[i-1];
		list[i-1] = list[0];
		list[0] = temp;
		int j = 0;
		while(
			(2*j+1 < i-1  &&  list[j] < list[2*j+1])||
			(2*j+2 < i-1  &&  list[j] < list[2*j+2])
		){
			if(2*j+2==i-1 || list[2*j+1]>list[2*j+2]){
				temp = list[2*j+1];
				list[2*j+1] = list[j];
				list[j] = temp;
				j <<= 1;
				j++;
			}
			else{
				temp = list[2*j+2];
				list[2*j+2] = list[j];
				list[j] = temp;
				j <<= 1;
				j += 2;
			}
		}
	}
}

終わりに

テンプレは私のを参考にしても良い(というか参考にしてくれたらめちゃくちゃ嬉しい)ですが、実際は自分が馴染むものを作って使うのが一番ですから、自分でも一度作ってみることをオススメします。