はじめに
今回はA～Dがコンテスト中のものを、Eはコンテスト後に解いたものを載せます。
では、見ていきましょう。
A - Integer Sum
問題文はこちら
ただ足すだけですね。
A.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = System.in.nextInt();
//数列を受け取って加算する
int answer = 0;
while(N-->0)
answer += System.in.nextInt();
//総和の出力
System.out.println(answer);
System.out.close();
}
}
まぁ問題無いですね。
B - Everyone is Friends
問題文はこちら
これも全探索すれば良いですね。
B.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//joined[i][j]:i番目の人がj番目に参加したか
boolean[][] joined = new boolean[N+1][M+1];
//受け取って処理
for(int i=1;i<=M;i++){
int k = System.in.nextInt();
while(k-->0){
int person = System.in.nextInt();
joined[person][i] = true;
}
}
//全探索
for(int i=1;i<=N;i++){
for(int j=i+1;j<=N;j++){
//どっかで同じ舞踏会に参加したか管理する変数
boolean ok = false;
//探索
for(int k=1;k<=M;k++){
if(joined[i][k]&&joined[j][k]){
ok = true;
break;
}
}
//同一の舞踏会に参加してないなら終了
if(!ok){
System.out.println("No");
System.exit(0);
}
}
}
//forを抜けた=全員条件を満たしているのでYesを出力
System.out.println("Yes");
System.out.close();
}
}
変数がごちゃごちゃしてていろいろとミスってしまいました。もうちょっとスマートに書きたいですね。
C - Max Even
問題文はこちら
二つの整数を足して偶数ができるのは偶数と偶数、奇数と奇数の二通りです。
ということで、偶数だけ、奇数だけでArrayListに格納し、それぞれの最大値二つの大きい方が答えとなります。
偶数、奇数が$1$個以下の時もあるので注意しましょう。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = System.in.nextInt();
//偶奇を格納するリスト
ArrayList<Integer> odd = new ArrayList<Integer>();
ArrayList<Integer> even = new ArrayList<Integer>();
//各要素を分類
while(N-->0){
int A = System.in.nextInt();
if(A%2==0)
even.add(A);
else
odd.add(A);
}
//ソート
Collections.sort(even);
Collections.sort(odd);
//2個以上あるなら最大値二つの和を、1個以下なら-1
int ev = even.size()>1?even.get(even.size()-1)+even.get(even.size()-2):-1;
int od = odd.size()>1?odd.get(odd.size()-1)+odd.get(odd.size()-2):-1;
//大きい方を出力
System.out.println(Math.max(ev,od));
System.out.close();
}
}
思いのほかサクッと解けました。
D - Root M Leaper
問題文はこちら
BFSで解きました。
先に移動できるマスを調べてからでも良かったんですが、コンテスト中は思いつかなかったので毎度移動できる$i$を全探索する方法をとりました。
D.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//各マスの答えを格納する配列
int[][] ans = new int[N][N];
//初期値は-1で
for(int i=0;i<N;i++)Arrays.fill(ans[i],-1);
//bfs用
LinkedList<Integer> bfs = new LinkedList<Integer>();
//最初の位置を記録
bfs.add(0);
bfs.add(0);
ans[0][0] = 0;
//bfs
while(bfs.size()>0){
int x = bfs.pollFirst();
int y = bfs.pollFirst();
//次の座標のiを全探索
for(int i=0;i<N;i++){
int temp = M-(x-i)*(x-i);
//iが適切な値でないならスキップ
if(temp<0)
continue;
//平方数か調べる
int j = (int)Math.sqrt(temp);
if(j*j==temp){
//平方数なら次の座標をbfsに加える
if(y+j<N&&ans[i][y+j]==-1){
ans[i][y+j] = ans[x][y]+1;
bfs.add(i);
bfs.add(y+j);
}
if(y-j>=0&&ans[i][y-j]==-1){
ans[i][y-j] = ans[x][y]+1;
bfs.add(i);
bfs.add(y-j);
}
}
}
}
//最終結果を出力
System.out.println(ans," ");
System.out.close();
}
}
やってること自体はシンプルなんですが、いろいろと変数を間違えたりしてペナルティを頂いてしまいました･･･。ちゃんと変数名は考えよう！
E - Add and Mex
問題文はこちら
各操作後での最小の非負整数を考えると、要素の数が$N$個なので答えは$0～N$の中にあるはずです。なので、各要素が$0～N$であるとき以外は考えなくても良さそうだと考えられます。
各操作後での値の存在判定はHashSetで行ないました。
E.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//各操作後の整数の存在判定をする用のList
ArrayList<HashSet<Integer>> list = new ArrayList<HashSet<Integer>>();
for(int i=0;i<M;i++)list.add(new HashSet<Integer>());
//各要素の操作後の値を記録
for(int i=1;i<=N;i++){
int A = System.in.nextInt();
//負数なら0以上になるまで操作をすっ飛ばす
int s = Math.max(1,-(A-i+1)/i);
A += s*i;
//N以下になるかM回操作が終わるまで記録
for(int j=s-1;j<M&&A<=N;j++,A+=i)
list.get(j).add(A);
}
//各操作後の最小の非負整数を探して出力
for(HashSet<Integer> nums:list){
int ans = 0;
while(nums.contains(ans))ans++;
System.out.println(ans);
}
System.out.close();
}
}
コンテスト中はめんどくさそう･･･って思って飛ばしてしまいました。ちょっと後悔･･･。
感想
A:簡単
B:ちょっとめんどくさいけど比較的簡単
C:すぐ気づける内容だった
D:内容自体は簡単(実装力が足りなかった･･･)
E:言われてみれば確かに･･･
って感じでした。
ペナルティを頂いての4完だとレート下がりますね･･･。悲しい･･･。