AtCoder Beginner Contest 094
※今回は不参加で、問題はすべてコンテスト終了後に解きました。
A - Cats and Dogs
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int a=sc.nextInt(), b=sc.nextInt(), x=sc.nextInt(); if (x < a) out.println("NO"); else { out.println(x-a<=b?"YES":"NO"); } } }
猫の最小値はa匹なので、それ未満の数の猫を指定された場合は条件分岐で弾く。
それ以上を指定された場合は、b匹のなかにx-a匹の猫がいることを証明する、つまりx-aがb以下であればよいので、それを条件式で処理して終わり。
B - Toll Gates
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n=sc.nextInt(), m=sc.nextInt(), x=sc.nextInt(); int[] ar = new int[n+1]; for (int i=0; i<m; i++) { int temp = sc.nextInt(); ar[temp]++; } int costL=0, costR=0; for (int i=x; i>=0; i--) costL += ar[i]; for (int i=x; i<=n; i++) costR += ar[i]; out.println(Math.min(costL,costR)); } }
配列を用意して、初期地点から左端(0)に向かうときのコストと、右端(n-1)に向かうときのコストを比較して、少ないほうを出力する。
C - Many Medians
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int[] ar = new int[n]; int[] ar2 = new int[n]; for (int i=0; i<n; i++) { ar[i] = sc.nextInt(); ar2[i] = ar[i]; } Arrays.sort(ar); int medianA = ar[n/2-1]; int medianB = ar[n/2]; for (int i=0; i<n; i++) { if (ar2[i] <= medianA) out.println(medianB); else out.println(medianA); } } }
答えとなる値は2通りしかないな、というのはすぐに分かりました。
与えられる要素数は偶数なので、配列をソートし、左側の中央値(本来なら2値の平均をとりますが、暫定的に)と右側の中央値をまず求める。
次に、ソートする前の配列を回していって、値が左側の中央値以下ならば右側の中央値を、右側の中央値以下ならば左側の中央値を出力する。
D - Binomial Coefficients
import static java.lang.System.*; import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int[] ar = new int[n]; for (int i=0; i<n; i++) { ar[i] = sc.nextInt(); } Arrays.sort(ar); int max = ar[n-1]; double target = max/2.0; double minDif = Integer.MAX_VALUE; int ans = 0; for (int i=0; i<n-1; i++) { double tempDif = Math.abs(ar[i]-target); if (tempDif < minDif) { ans = ar[i]; minDif = tempDif; } } out.println(max+" "+ans); } }
出力例1を見て、「最大値」と「最大値/2にいちばん近い値」を順に出力すればいいのでは、と思い、そのように書いたところACしました。
その後解説を読みましたが、何が何やら分からないので、やっぱり数学の知識をつけないといけないのだなと改めて思いました。
まとめ
とくになし