はじめに
コンテスト中に提出したコードは煩雑なので、基本方針はそのままで訂正・改良したものを解説します。
では、解説していきます。
A - Lacked Number
問題文はこちら
特に難しくは考えず、無い数字を全探索しましょう。
import java.io.*;
class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//数字を分割して格納
char[] num = br.readLine().toCharArray();
//0から順に探す
for(int i=0;i<10;i++){
//見つかったかどうか管理する変数
boolean find = false;
for(int j=0;j<num.length;j++){
//一致した？
if(i==num[j]-'0')
find = true;
}
//見つからなかったら終了
if(!(find)){
System.out.println(i);
System.exit(0);
}
}
}
}
易しい問題で助かりました。
B - Slimes
問題文はこちら
問題文を言い換えれば「B/AをKで何回割れば1以下になるか」を聞いているので、そのままfor文で処理しましょう。
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//値の取得
int A = sc.nextInt();
int B = sc.nextInt();
int K = sc.nextInt();
//初期状態を格納
double div = (double)B/A;
//そもそも叫ばなくて良い？
if(A>=B){
System.out.println(0);
System.exit(0);
}
//一回ずつ叫んだときを考える
for(int i=1;;i++){
//一回ずつ割っていく
div = div / K;
//1以下になったら終了
if(div<=1.0){
System.out.println(i);
System.exit(0);
}
}
}
}
計算式さえ思いつけば特に悩まないですね。
C - Dice Sum
問題文はこちら
単純にDFSをやろうとすると多分TLEを食らうので、メモを残すようにしておきましょう。メモをする意味は以下のような時に役立ちます。
例：2番目を決めた後をDFSで調べている時(引数は「K-今の数列の合計」と「残りの要素数」の二つ)
(1,5,?,?,?) → DFS(K-6,3)=10だった！
(2,4,?,?,?) → DFS(K-6,3)=10だった！
上記の場合、一回目も二回目もDFSの引数は同一です。ですから戻り値も一緒です。このとき、わざわざ毎回再帰なんてやらせるよりは一回目でmemo[K-6][3]=10のように二次元配列に突っ込んでしまった方がそれ以降はメモを参照するだけなのでかなり速くなります。
こんな感じで実装してやりましょう！
import java.util.*;
class Main{
//processと共有したい値はフィールドに
static long mod = 998244353;
int max;
long[][] memo;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//値の取得
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
//数列の一つが取れる最大値を格納
max = Math.min(M,K-N+1);
//processのnokoriとlimitに応じた答えはいつも同じなのでそれをメモする配列を準備
memo = new long[N+1][K+1];
//DFSに初期状態を投げ込む
long ans = process(N,K);
System.out.println(ans);
}
//DFSメソッド
public long process(int nokori,int limit){
//もう数列作れなくない…？(以降の要素が0しか入れられなくなっているか？)(多分この条件を満たすことは無い)
if(nokori>limit)
return 0; //そんな状態の数列は条件を満たさないので0を返す
//もう調べたことある？
if(memo[nokori][limit]!=0)
return memo[nokori][limit]; //記録があるならそれを返す
//return用変数
long count = 0;
//最後の一個？
if(nokori==1)
count = Math.min(max,limit); //「取り得る最高」と「今ある余裕(K-sum)」の小さい方を返す
//全部満たさなかったら今見ている要素を1から順に当てはめて再帰させる
else{
//1から順に当てはめていく
for(int i=1;i<=Math.min(max,limit-nokori+1);i++){
//後ろの組合せを合算
count += process(nokori-1,limit-i);
//こまめにあまりを取っておく
count %= mod;
}
}
//今やった結果をメモ
memo[nokori][limit] = count;
//結果を返す
return count;
}
}
メモしながらやる再帰は上手く実装できると楽しいんですよね。私は好きです。思いつけば、ですが…。
D - Range Count Query
問題文はこちら
正直自分でもあまりわかってなかったりする実装なんですが、各数字をListのindexにしてそのListの中のListにどこにあるかを格納するというやり方で情報を格納して、あとはList.get(X)にあるL以上でR以下の要素の数を探せばいいです。ただ、このやり方だとかなりギリギリの実行時間です。言語的な限界なんですかねぇ…(提出したときは1865ms)
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Nの取得
int N = sc.nextInt();
//数列の情報を格納する可変長配列の準備
ArrayList<ArrayList<Integer>> A = new ArrayList<ArrayList<Integer>>();
//ArrayListの中は一つずつ初期化する必要がある。
for(int i=0;i<N+1;i++){
ArrayList<Integer> Asub = new ArrayList<Integer>();
A.add(Asub);
}
//数列情報の格納
for(int i=0;i<N;i++){
int temp = sc.nextInt();
A.get(temp).add(i+1);
}
//Qを取得
int Q = sc.nextInt();
//クエリの試行
for(int i=0;i<Q;i++){
//情報の取得
int L = sc.nextInt();
int R = sc.nextInt();
int X = sc.nextInt();
//一番最初を探す
int fir = Collections.binarySearch(A.get(X),L,(a,b) -> a>=b ? 1 : -1);
//一番最後を探す
int fin = Collections.binarySearch(A.get(X),R+1,(a,b) -> a>=b ? 1 : -1);
//差を出力
System.out.println(fir-fin);
}
}
}
って思ってたんですが、以下のように書き換えたらかなり時短になりました。
具体的にはScannerクラスをBufferedReaderクラスに、出力をPrintWriterクラスに置き換えることで高速化しました。実行時間は772msです。
import java.io.*;
import java.util.*;
class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
//Nの取得
int N = Integer.parseInt(br.readLine());
//数列の情報を格納する可変長配列の準備
ArrayList<ArrayList<Integer>> A = new ArrayList<ArrayList<Integer>>();
//ArrayListの中は一つずつ初期化する必要がある。
for(int i=0;i<N+1;i++){
ArrayList<Integer> Asub = new ArrayList<Integer>();
A.add(Asub);
}
//数列情報の格納
String[] nums = br.readLine().split(" ");
for(int i=0;i<N;i++){
int temp = Integer.parseInt(nums[i]);
A.get(temp).add(i+1);
}
//Qを取得
int Q = Integer.parseInt(br.readLine());
//クエリの試行
for(int i=0;i<Q;i++){
//情報の取得
String[] str = br.readLine().split(" ");
int L = Integer.parseInt(str[0]);
int R = Integer.parseInt(str[1]);
int X = Integer.parseInt(str[2]);
//一番最初を探す
int fir = Collections.binarySearch(A.get(X),L,(a,b) -> a>=b ? 1 : -1);
//一番最後を探す
int fin = Collections.binarySearch(A.get(X),R+1,(a,b) -> a>=b ? 1 : -1);
//差を出力
pw.println(fir-fin);
}
pw.flush();
}
}
多分入力か出力(または両方)がとんでもなく多いんでしょうね…。気をつけないと…。
総評
A：簡単。助かる。
B：数式だけちょっと悩んだが、比較的優しい。
C：メモ化再帰は楽しい！
D：実行速度を詰める箇所がまだまだありそう。楽しい！
って感じでした。
やはり企業コン。なかなか複雑で考えさせられる問題でした。