AtCoderのABC180の復習メモ。自分用なので、正確な情報をお探しの方は公式の解説放送をご覧になられることをお勧めします。使用言語はJavaです。
A問題 box
問題文
個のボールが入っていた箱から 個のボールを取り出し、新たに 個のボールを入れました。
今、箱にはボールが何個入っていますか?
制約
- 入力はすべて整数
- 100≤N≤200
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
答えを整数で出力せよ。
メモ
問題文の通りN – A + Bをすれば問題なし。以下のコードでAC。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = null;
sc = new Scanner(System.in);
long n = sc.nextLong();
long a = sc.nextLong();
long b = sc.nextLong();
sc.close();
System.out.println(n-a+b);
}
}
B問題 Various distances
問題文
N次元空間内の点 (x1,…,xN)が与えられます。原点からこの点までの、マンハッタン距離、ユークリッド距離、チェビシェフ距離をそれぞれ求めてください。 ただし、それぞれの距離は次のように計算されます
- マンハッタン距離：
$$|x_1|+\ldots+|x_N|$$
- ユークリッド距離：
$$\sqrt{|x_1|^2+\ldots+|x_N|^2}$$
- チェビシェフ距離：
$$\max(|x_1|,\ldots,|x_N|)$$
制約
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
x1 …xN
出力
原点から与えられた点までの、マンハッタン距離、ユークリッド距離、チェビシェフ距離をそれぞれこの順に改行区切りで出力せよ。 正しい値との絶対誤差または相対誤差が 以下であれば正解とみなされる。
メモ
問題文に記載されている計算式を実装すれば良い。intでは桁あふれする場合があるので、longを使用する。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = null;
sc = new Scanner(System.in);
long n = sc.nextLong();
long m = 0;
double u = 0;
long tmp = 0;
long abs = 0;
ArrayList<Long> numList = new ArrayList<Long>();
for (int i = 0; i < n; i++) {
tmp = sc.nextLong();
abs = Math.abs(tmp);
m += abs;
u += Math.pow(abs, 2);
numList.add(abs);
}
sc.close();
System.out.println(m);
System.out.println(Math.sqrt(u));
System.out.println(Collections.max(numList));
}
}
C問題 Cream puff
問題文
N個のシュークリームがあります。
シュークリームを分割することなく平等に分けることができるような人数としてあり得るものを全て求めてください。
制約
- 1≤N≤10^12
- Nは整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを改行区切りで昇順に出力せよ。
メモ
Nを割り切ることができる数＝約数を全て列挙する。１～Nまでの全てを試すとTLEしてしまう。
Nをaで割り切れる時、\(\frac{N}{a}\)も約数に加えることができる。この性質を利用して、計算量を抑えることができる。
例）12は2で割り切れるが、\(\frac{12}{2}\)=6も約数となる。
以下の記事の解説がとても分かりやすかった。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = null;
sc = new Scanner(System.in);
long n = sc.nextLong();
ArrayList<Long> numList = new ArrayList<Long>();
for (long i = 1; i * i <= n; i++) {
if (n % i == 0) {
numList.add(i);
if (n / i != i) {
numList.add(n / i);
}
}
}
sc.close();
Collections.sort(numList);
for (int j = 0; j < numList.size(); j++) {
System.out.println(numList.get(j));
}
}
}
D問題 Takahashi Unevolved
問題文
いろはちゃんはペットを育てるゲームにはまっています。
いろはちゃんはペットとして高橋君を飼っており、はじめ高橋君の 強さ は X、経験値 は 0です。 これらの値は次の 2種類の特訓によって増加します。
- カコモンジムに通う：強さが A 倍になり、経験値は 1 増える。
- AtCoderジムに通う：強さが B 増え、経験値は 1 増える。
高橋君は強さが Y以上になると進化しますが、進化しない方がかわいいといろはちゃんは思っています。そこで、強さが Y以上にならないように高橋君に特訓を課すとき、経験値の最大値を求めてください。
制約
- \(1 \leq X < Y \leq 10^{18}\)
- \(2 \leq A \leq 10^9\)
- \(1 \leq B \leq 10^9\)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X Y A B
出力
与えられた条件の下での経験値の最大値を出力せよ。
メモ
どこかでA倍にした時の増加幅が＋Bするよりも大きくなるタイミングが来る為、A倍出来る回数を調べ、出来なくなったら残りの数をBで割り、何回+B出来るのか調べれば良い。
A倍出来る条件を満たすのが\(X \times A＜X+B\)となる。これを移項していくと
\((X \times A)-X＜B\)
\(X A-X＜B\)
\((A-1) \times X＜B\)
\(X＜\frac{(A-1)}{B}\)
となる。上記を満たす間はA倍していき、満たせなくなったらBで割り、足せる回数を算出すれば良い。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = null;
sc = new Scanner(System.in);
long x = sc.nextLong();
long y = sc.nextLong();
long a = sc.nextLong();
long b = sc.nextLong();
sc.close();
long ans = 0;
while (x < y) {
// オーバーフロー対策
if (y / a < x) {
break;
}
// 一発で進化してしまうケース
if (x*a >= y) {
break;
}
if (x >= b / (a - 1)) {
break;
}
x *= a;
ans += 1;
}
ans += (y-x-1)/b;
System.out.println(ans);
}
}