はじめに
入力のみ、提出時から変更してあります。他はなるべく提出時のままの方針です。
コンテスト中にはA,B,Dが解けました。Cはコンテスト後です。
では、見ていきましょう。
A - Good morning
問題文はこちら
if文で書いてみましょう。
まず、A>Cならば青木君が、A<Cならば高橋君が早く起きるのでそれを分岐します。
すると、それ以降のelseはA==C前提でコードが組めますので、条件はB>D(すなわち青木君の方が早く起きるとき)のみで分岐すれば良いです(同時刻なら高橋君の方が早く起きるので>に=は付けません)。
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 C = sc.nextInt();
int D = sc.nextInt();
//分岐させて正しい答えを出力する
if(A>C)
System.out.println("Aoki");
else if(A<C)
System.out.println("Takahashi");
else if(B>D)
System.out.println("Aoki");
else
System.out.println("Takahashi");
}
}
なお、これは以下のように書くことも出来ます。
B、Dは高々59<2^6なので、A、Dを右シフトしてそれぞれB、Cを加算することで、ifとelseのみで済みます。
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 C = sc.nextInt();
int D = sc.nextInt();
//高橋君が起きた時刻は青木君が起きた時刻より遅いか？(同時刻は含まない)
if((A<<6)+B>(C<<6)+D)
System.out.println("Aoki");
else
System.out.println("Takahashi");
}
}
もちろん時間の定義にしたがってA*60+Bのようにしても同様に解けます。
B - Mex
問題文はこちら
普通に全探索をしました。
0から順に、Aに含まれていないかを確認して、含まれていれば1加算してまた探して…という感じです。
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//値の取得
int N = sc.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++)A[i] = sc.nextInt();
//0から順に探す
for(int i=0;true;i++){
boolean Yes = true;
//Aの中にあるか探す
for(int j=0;j<N;j++){
if(A[j]==i){
Yes = false;
break;
}
}
//無ければ出力して終了
if(Yes){
System.out.println(i);
System.exit(0);
}
}
}
}
なお、事前にAをソートしてしまえば、Arrays.binarySearchの戻り値が0未満になるまで探すという手法もあります(要素中に同一の値があれば0以上、無ければ0未満が保証されているので)。
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//値の取得
int N = sc.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++)A[i] = sc.nextInt();
//Aのソート
Arrays.sort(A);
//初期値設定(++numberにするために、初期値は-1から)
int number = -1;
//0から順にA内にないものを探し、出力
while(Arrays.binarySearch(A,++number)>=0){}
System.out.println(number);
}
}
直感的ではないのでちょっとわかりにくいかもしれませんが、記述自体はすっきりします。
C - Choose Elements
問題文はこちら
解説のままのコードです。
一番最初から見ている箇所までがtrueで、かつ次の数字を選ぶことは可能かをA、Bそれぞれで記録していくことで解けました。(いわゆるDPというやつです)。まぁ実際にコードを見た方が良いかなと思います(DPの説明が難しい…)。
class Main{
public static void main(String[] args){
java.util.Scanner sc = new java.util.Scanner(System.in);
//N、Kの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//選択可能か見ていく為の配列
boolean[] dpA = new boolean[N];
boolean[] dpB = new boolean[N];
dpA[0] = dpB[0] = true; //一番最初はtrue
//A、Bの受け取り
int[] A = new int[N];
int[] B = new int[N];
for(int i=0;i<N;i++){
A[i] = sc.nextInt();
}
for(int i=0;i<N;i++){
B[i] = sc.nextInt();
}
//二番目から順に、条件を満たすか記録していく
for(int i=1;i<N;i++){
//なんか好きだから三項演算子で
if(dpA[i-1]){
dpA[i] = Math.abs(A[i-1]-A[i])<=K?true:dpA[i];
dpB[i] = Math.abs(A[i-1]-B[i])<=K?true:dpB[i];
}
if(dpB[i-1]){
dpA[i] = Math.abs(B[i-1]-A[i])<=K?true:dpA[i];
dpB[i] = Math.abs(B[i-1]-B[i])<=K?true:dpB[i];
}
}
//最後まで選択可能だったらYes、そうでないならNoを出力
if(dpA[N-1]||dpB[N-1])
System.out.println("Yes");
else
System.out.println("No");
}
}
詳しい説明は公式解説にまかせます(丸投げ)。
D - Polynomial division
問題文はこちら
高校数学で習った記憶がありますが、多項式の割り算で解けますね。
実装が少々面倒ですがCの最高次から順に見ていき、Aの最高次で割った値をAにかけてCから引く、というのを繰り返していけば答えが出ます。
筆算をイメージしてもらえればと思います。
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//添え字が0から始まることに注意！
int[] A = new int[N+1];
for(int i=0;i<=N;i++)A[i] = sc.nextInt();
//同様に注意！
int[] C = new int[N+M+1];
for(int i=0;i<=N+M;i++)C[i] = sc.nextInt();
//答えとなるBの長さ
int lengthOfB = C.length-A.length + 1;
//答えを記録する配列
int[] answer = new int[lengthOfB];
//順番にBを埋めていく
for(int i=0;i<lengthOfB;i++){
//今見ているCの係数が0ならスキップ
if(C[C.length-1-i]==0){
answer[i] = 0;
continue;
}
//割り算をし、順にCから引いていく(筆算のイメージ)
int temp = C[C.length-1-i] / A[A.length-1];
for(int j=0;j<A.length;j++){
C[C.length-1-i-j] -= A[A.length-1-j] * temp;
}
//答えを記録
answer[i] = temp;
}
//記録した答えが逆順になっているので、後ろから出力
for(int i=answer.length-1;i>0;i--){
System.out.print(answer[i]+" ");
}
System.out.println(answer[0]);
}
}
まだ高校の記憶が若干残ってて良かったです。
感想
A:易しい。
B:制約から全探索で良いかと思えたので良かった。
C:難しい…解説見ないと全然思いつかなかった…。
D:高校数学を懐かしく感じる問題だった。
って感じでした。
DP苦手ですね…精進が足りてないです…。