競プロにJavaで挑んで四苦八苦しましたよというお話
Java × 競技プログラミング
競技プログラミングにJavaで参加するするときにネックとなるのが、実行時間の制約だと思います。私が参加しているプラットでは、場合によってC++14よりも20倍～、Python3よりも4倍の処理時間がかかります(Java8 OpenJDK1.8.0)。
課題を解けるロジックを思いついたのにも関わらず、実行時間の制約によって正答とならず、やりきれない思いをすることも多いのです。
そこで、最近出会ったtoughな課題の内容と、そのような問題への方策・方針を共有しようと思います。
（謙遜ではなく）初心者コーダーの書き留めですので、コメント等あれば遠慮なくいただけれると、これ幸いです。
中央値を求めよ
2以上の偶数Aと、1以上のA個の自然数の入力を所与とし、A個の整数をそれぞれ入力順に１つずつ除いた奇数個の数の集合に対して、その集合の中央値を順に出力せよ。
ただし
・Aが必ず10^5以下であることは、保証されている。
・入力が必ず全て整数であることは、保証されている。処理例：
input
6 (==A)
7 1 4 2 6 9 (与えられた（テストケースとして与えられる）1以上のA個の自然数の入力)output
4 ∵(1,4,2,6,9)の集合
6 ∵(7,4,2,6,9)の集合
6 ∵(7,1,2,6,9)の集合
6 ∵(7,1,4,6,9)の集合
4 ∵(7,1,4,2,9)の集合
4 ∵(7,1,4,2,6)の集合
中央値の説明はこちら
https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
どう解くか
問題の内容から
・入力された値を数値配列に格納する（Array、もしくはArrayListに）。
・その配列から順に要素を削除する。
・その配列をソートする。
・(A/2)-1番目の値を出力する。
という処理の流れが見えてきます。
ということは
・その配列から順に要素を削除する。
・その配列をソートする。
・(A/2)-1番目の値を出力する。
という繰り返し処理を書けばよいことになります。
そのうえで最初に書いたコードがこちら。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(s.nextInt());
}
ArrayList<Integer> arrCopy = (ArrayList<Integer>) arr.clone();
for(int j=0;j<n;j++){
/*★*/ arr.remove(j);
/*★*/ Collections.sort(arr);
System.out.println(arr.get((n / 2) - 1));
/*★*/ arr = (ArrayList<Integer>) arrCopy.clone();
}
}
}
しかしこのコード、本番環境では実行時間オーバーになります。
★の位置でA回分、Listの削除・ソート・複製を行っているのでアウト。
ArrayListクラスは、要素数は可変ですが、Arrayクラスに比べ実行速度が遅くなりがちである、という性質を持っています。
どう時間制約を守るか
さて、課題の内容は、それぞれの中央値を出力せよとのことでした。
そして、要素を１つずつ削除し中央値は特定しなければいけませんが、ArrayListは使うべきではない、と。
…
実はこの問題の中央値、どんなに要素数があっても候補は2つです。
例えば
1，2，3，4，5，6
という数が与えられたとして、1から6まで1つずつ数を削除しても、中央値は必ず3か4のどちらかになります。
1,2,3が削除されたときには4が中央値、
4,5,6が削除されたときには3が中央値として決定されます。
これを踏まえた後に書いたコードがこちら。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] sortedArr = new int[n];
for (int i = 0; i < n; i++) {
sortedArr[i] = s.nextInt();
}
int[]originArr=sortedArr.clone();
Arrays.sort(sortedArr);
int firstNum=sortedArr[(n/2)-1];
int secondNum=sortedArr[n/2];
for(int j=0;j<n;j++){
if(originArr[j]<secondNum){
System.out. println(secondNum);
}
else{
System.out.println(firstNum);
}
}
}
}
入力された数字を配列を格納するところまでは（配列のクラスは違いますが）一緒です。
そのあと、（n/2）-1番目の数とn/2番目の数を、それぞれint値として格納します。
そして、削除された数と中央値候補の小さい数を比較して、任意の値を出力します。
こちらのコードでは、出力を行うfor文内で配列の操作を行うことなく済んでいます。そしてJavaであっても、配列の要素が可変の課題でも、時間制約を守ることができます。
時間の制約にどう挑んでいくかということ
まず、最初の見通しとして、削除後の各配列の中で中央値が、動的に変化するということを前提にしていたことが誤り。
このような前提をおいた要因は”早くコードを書いて、submitしなきゃ”という焦りです。
競技プログラミングってコーダーにとって特殊な環境だと思っていて、ほとんどの参加者にとっては厳しい競技時間の中で動くコードを書かなければいけません。つまり、早くコードを書きたくて焦ることが起きがちなのです。
ある程度慣れてきている人(全体の数%しか正答できないもの以外の課題を正答できる人)にとっては、問題の正答数よりも所要時間のほうが参加者順位を決める重要なファクターとなってくるので、なおさらです。
しかし、制約の多い環境で、加えてJavaのような競技プログラミングに”不利な”言語で参加する際には、
・繰り返し文の中に処理を複数書いたり、
・便利なクラスを使う
のではなく、
・解答について法則を検討する
・繰り返し文を使うとしてもその中での処理は最小限にする
ということが重要な方略になってくるのでは、ということが、自分への戒めでもあり、今回共有したかったことです。
以上となります。誤った点、または別解などありましたら、コメントにて教えていただけますと幸いです。