AtCoderのARC105の復習メモ。自分用なので、正確な情報をお探しの方は公式の解説放送をご覧になられることをお勧めします。使用言語はJavaです。
A問題
問題文
すぬけ君は美味しさが A,B,C,D であるような 4枚のクッキーを持っています。 すぬけ君は 1枚以上のクッキーを選んで食べます。食べるクッキーの美味しさの総和と、残るクッキーの美味しさの総和が等しくなることはありますか？
制約
- 与えられる入力は全て整数
- \(1 \leq A,B,C,D \leq 10^{8}\)
入力
入力は以下の形式で標準入力から与えられる。
A B C D
出力
すぬけ君が食べるクッキーの美味しさの総和と、残るクッキーの美味しさの総和が等しくなることがあるなら YES、そうでなければ Noを出力せよ。
メモ
コンテストの時は総当たりで確認を行った。だが、入力値を\(A<B<C<D\)と並び変えることで、A+D=B+CとD=A+B+Cのみの確認で十分となる。
import java.util.*;
public class A {
public static void main(String[] args){
Scanner sc = null;
sc = new Scanner(System.in);
ArrayList<Long> numList = new ArrayList<Long>();
for (int i = 0; i < 4; i++) {
numList.add(sc.nextLong());
}
sc.close();
// ソート A≦B≦C≦D
Collections.sort(numList);
long a = numList.get(0);
long b = numList.get(1);
long c = numList.get(2);
long d = numList.get(3);
String ansStr = "No";
// 不等号の関係から、試すのはA+D=B+CとD=A+B+Cのみで十分となる
if (a+d == b+c) {
ansStr = "Yes";
}
if (d == a+b+c) {
ansStr = "Yes";
}
System.out.println(ansStr);
}
}
B問題
問題文
すぬけ君は から の番号がついた 枚のカードを持っています。 それぞれのカードには整数が書かれており、カード には が書かれています。
すぬけ君は以下の手続きを行います。
- すぬけ君が持っているカードに書かれた数の最大値を 、最小値を とする。
- なら手続きを終了する。そうでなければ が書かれたカードを全て が書かれたカードに変え、 へ戻る。
この問題の制約下で、いずれ手続きが終了することが証明できます。手続き終了後のすぬけ君が持っているカードに書かれた唯一の数を求めてください。
制約
- 与えられる入力は全て整数
- \(1 \leq N \leq 10^{5}\)
- \(1 \leq a_i \leq 10^9\)
入力
入力は以下の形式で標準入力から与えられる。
N
a1 a2 ⋯ aN
出力
手続き終了後のすぬけ君が持っているカードに書かれた唯一の数を出力せよ。
メモ
2つの数の例で幾つか試しに考えてみると、最大公約数（GCD）求めれば良いことが分かる。
例）6と15の場合
①15から6を引く：6,9
②9から6を引く：6,3
③6から3を引く：3,3 ←答えの3は6,15のGCD
例）18と48の場合
①48から18を引く：18,30
②30から18を引く：18,12
③18から12を引く：12,6
④12から6を引く：6,6 ←答えの6は18,48のGCD
よって、引数全てのGCDを求める。
import java.util.*;
public class B {
public static void main(String[] args) {
Scanner sc = null;
sc = new Scanner(System.in);
int n = sc.nextInt();
long ans = 0;
for (int i = 0; i < n; i++) {
ans = GCD(ans, sc.nextLong());
}
sc.close();
System.out.println(ans);
}
private static long GCD(long a, long b) {
if (b == 0) {
return a;
} else {
return GCD(b, a % b);
}
}
}