AtCoderのABC181の復習メモ。自分用なので、正確な情報をお探しの方は公式の解説放送をご覧になられることをお勧めします。使用言語はJavaです。
A問題 Heavy Rotation
問題文
高橋くんは今、白い服を着ています。
高橋くんは、白い服を着た次の日には黒い服を、黒い服を着た次の日には白い服を着ます。
N日後には何色の服を着るでしょうか？
制約
- Nは整数である
- \(1 \leq N \leq 30\)
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数で出力せよ。
メモ
N日後が奇数の場合に黒、偶数の場合に白を着ることになるので、2で割った余りを見れば良い。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = null;
sc = new Scanner(System.in);
long n = sc.nextLong();
sc.close();
if (n%2 == 0) {
System.out.println("White");
} else {
System.out.println("Black");
}
}
}
B問題 Various distances
問題文
何も書かれていない黒板があります。 高橋くんは N回の操作を行い、黒板に整数を書きます。
i回目の操作では、 Ai以上 Bi以下の整数すべてを 1個ずつ、合計 Bi−Ai+1個の整数を書きます。
N回の操作を終えたときの、黒板に書かれた整数の合計を求めてください。
制約
- 入力は全て整数
- \(1 \leq N \leq 10^5\)
- \(1 \leq A_i \leq B_i \leq 10^6\)
入力
入力は以下の形式で標準入力から与えられる。
A1 B1
⋮
AN BN
出力
N回の操作を終えたときの、黒板に書かれた整数の合計を出力せよ。
メモ
A以上~B以下までの整数の和を算出していけば良いが、整数が最大で\(10^{11}\)個となるのでループでの計算はTLEしてしまう。
1以上\(x\)以下の総和は\(\frac{x(x+1)}2\)で求められる為、これを利用して
(\(A\)以上\(B\)以下の整数の和 ) = ( 1以上 \(B\)以下の整数の和 ) − ( 1以上 \(A\)−1以下の整数の和 )
で求めることが出来る。
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 = 0;
long b= 0;
long ans = 0;
long work= 0;
long a2= 0;
for (int i = 0; i < n; i++) {
a = sc.nextLong();
b = sc.nextLong();
a2 = a - 1;
work = ((b * (b + 1)) / 2) - ((a2 * (a2 + 1)) / 2);
ans += work;
}
sc.close();
System.out.println(ans);
}
}
C問題 Collinearity
問題文
無限に広い次元平面の上に\(N\)個の点があります。
\(i\)番目の点は\((x_i,y_i)\)にあります。
\(N\)個の点の中の相異なる点であって、同一直線上にあるものは存在するでしょうか？
制約
- 入力はすべて整数
- \(3 \leq N \leq 10^2\)
- \(|x_i|, |y_i| \leq 10^3\)
- \(i \neq j\)ならば\((x_i, y_i) \neq (x_j, y_j)\)
入力
入力は以下の形式で標準入力から与えられる。
\(N\)
\(x_1\) \(y_1\)
⋮
\(x_N\) \(y_N\)
出力
同一直線上にある相異なる 点が存在するなら Yesを、存在しないなら No を出力せよ。
メモ
\(N\)が\(10^2\) = 100なので3重ループで総当たりで検証しても間に合う。
異なる3点 \(A\) \(B\) \(C\)が同一直線状にいる場合、直線ABと直線BCの傾きは同一となる。
直線ABの傾きを\(\frac{y_1}{x_1}\)、直線BCの傾きを\(\frac{y_2}{x_2}\)とした時、
\(\frac{y_1}{x_1} = \frac{y_2}{x_2}\) が成立するか判定すればよい。
但し、分母が0となる可能性がある為、両辺に\(x_1x_2\)を掛け
\(x_2y_1 = x_1y_2\) で判定を行う。
import java.util.*;
public class C {
public static void main(String[] args) {
Scanner sc = null;
sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Integer> x = new ArrayList<Integer>();
ArrayList<Integer> y = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
x.add(sc.nextInt());
y.add(sc.nextInt());
}
sc.close();
int ax = 0;
int bx = 0;
int cx = 0;
int ay = 0;
int by = 0;
int cy = 0;
// 点Aと点Bの座標の差
int x1 = 0;
int y1 = 0;
// 点Bと点C座標の差
int x2 = 0;
int y2 = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
ax = x.get(i);
bx = x.get(j);
cx = x.get(k);
ay = y.get(i);
by = y.get(j);
cy = y.get(k);
// 点Aと点Bの座標の差
x1 = ax - bx;
y1 = ay - by;
// 点Bと点Cの座標の差
x2 = bx - cx;
y2 = by - cy;
// 0除算考慮のため、両辺にx1x2を掛け、移項して判定
// y1/x1 = y2/x2 → x2y1 = x1y2
if (x2 * y1 == x1 * y2) {
System.out.println("Yes");
return;
}
}
}
}
System.out.println("No");
}
}