はじめに
今回はコンテスト中にCまで、コンテスト後にDを解いたのでそれを載せようと思います。
では、見ていきましょう。
A - Many A+B Problems
問題文はこちら
普通にA+Bを出力するだけですね。
A.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Nの受け取り
int N = System.in.nextInt();
//N回A+Bを出力する
while(N-->0){
System.out.println(System.in.nextInt()+System.in.nextInt());
}
System.out.close();
}
}
普段のAもこれくらいで良い気がしてます…。
B - Qualification Contest
問題文はこちら
上位$K$人の情報しか必要でないので$K$個文字列を受け取ってソートし、それを順に出力しました。
重複するハンドルネームは制約上無いのでソートするのにTreeSetを使いました。
B.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Kの受け取り
int N = System.in.nextInt();
int K = System.in.nextInt();
//昇順で並べ替える用
TreeSet<String> set = new TreeSet<>();
//上位K人のハンドルネームを入れる
while(K-->0)
set.add(System.in.next());
//先頭から順に出力する
for(String str:set)
System.out.println(str);
System.out.close();
}
}
これもそこまで難しくなかったですね。
$K$人のハンドルネームを固定長配列で受け取ってArrraysのsortメソッドを使っても良いかと思います。
C - Don’t be cycle
問題文はこちら
公式解説の通り、全域木を作ることを考えれば良いかなと思って、UnionFindを用いて解きました。
C.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//UnionFind
UnionFind uf = new UnionFind(N+1);
//消す辺の数
int ans = 0;
while(M-->0){
int A = System.in.nextInt();
int B = System.in.nextInt();
//既に同一の木に存在するならその辺を消す
if(!uf.unite(A,B))
ans++;
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
気付くのが早かったので助かりました。
D - Range Add Query
問題文はこちら
解法は公式解説の通りなので詳しい説明はそちらに任せます(手抜き)。
D.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Kの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//先頭、末尾に0を挿入したAを受け取る
int[] A = new int[N+2];
for(int i=1;i<=N;i++)
A[i] = sc.nextInt();
//階差数列の構築
int[] subA = new int[N+1];
for(int i=0;i<=N;i++)
subA[i] = A[i+1]-A[i];
//階差数列の累積和(添え字modKで分ける)
//sum[i][j]:添え字modK=iのみでのj個までの総和
long[][] sum = new long[K][N+2];
for(int i=0;i<=N;i++){
for(int j=0;j<K;j++){
if(i%K==j)
sum[j][i+1] = subA[i];
sum[j][i+1] += sum[j][i];
}
}
//Qの受け取り
int Q = sc.nextInt();
//出力高速化用
StringBuilder ans = new StringBuilder();
while(Q-->0){
int l = sc.nextInt();
int r = sc.nextInt();
//各あまりの累積和から良い数列に出来るか検証
boolean isGood = true;
for(int i=0;i<K;i++){
//累積和の添え字が解説のものと+1ズレてるので注意
long temp1 = sum[i][r+1];
if(r%K==i)
temp1 -= A[r+1];//端っこの調整
long temp2 = sum[i][l-1];
if((l-1)%K==i)
temp2 -= A[l-1];//端っこの調整
//総和が0になり得るか論理積を取る
isGood &= temp1==temp2;
}
//良い数列に出来そうかをansに
ans.append(isGood?"Yes":"No");
ans.append("\n");
}
//答えの出力
System.out.print(ans.toString());
}
}
添え字が永遠に合わなくてすんごい理解に時間がかかりました…。
感想
A:すごく易しい
B:これも易しい
C:発想が比較的早かったのに救われた
D:手も足も出なかった…
って感じでした。
3完でもこの回ではレートが上がりました。良かった…。