はじめに
今回はD以外はコンテスト中に、Dは解説を見てから解いたものを載せようと思います。
では、見ていきましょう。
A - 1-2-4 Test
問題文はこちら
1、2、4を二進数で表すと001、010、100となることから、それぞれの問題が解けたかはビットが立ってるかで判定できます。ということで、$A|B$が答えになりますね。
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{
//A、Bの受け取り
int A = System.in.nextInt();
int B = System.in.nextInt();
//答えの出力
System.out.println(A|B);
System.out.close();
}
}
なんてことはないですね。
B - Hammer
問題文はこちら
位置関係ごとに条件分岐させることで解きました。
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{
//値の受け取り
int X = System.in.nextInt();
int Y = System.in.nextInt();
int Z = System.in.nextInt();
//Xまでまっすぐ進めるか？
if(0<Z&&Z<Y||0<X&&(X<Y||0>Y))
System.out.println(Math.abs(X));
else if(Z<0&&Y<Z||0>X&&(X>Y||0<Y))
System.out.println(Math.abs(X));
else{
//壁とゴールが同じ方向にあるとき
if(X>0&&Y>0){
if(X>Y&&Z<0)
System.out.println(2*Math.abs(Z)+Math.abs(X));
else
System.out.println(-1);
}else if(X<0&&Y<0){
if(X<Y&&Z>0)
System.out.println(2*Math.abs(Z)+Math.abs(X));
else
System.out.println(-1);
}else{
//違う方向ならXに直行
System.out.println(Math.abs(X));
}
}
System.out.close();
}
}
最初条件が抜けててペナルティを頂いてしまいました。
もったいない･･･。
C - Simple path
問題文はこちら
DFSで解きました。
通った頂点をboolean型配列で記録し、$Y$に到着したら順にArrayListに記録して返しました。返ってきた物は逆順になっていることに注意しましょう(ちなみに、ArrayListをLinkedListに変えてaddFirstで記録すれば逆順にならなくて済みます)。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
//各種変数(DFS側で参照できるように)
static boolean[] isUsed;
static int Y;
static ArrayList<ArrayList<Integer>> list;
public static void main(String[] args)throws IOException{
//N、X、Yの受け取り
int N = System.in.nextInt();
int X = System.in.nextInt();
Y = System.in.nextInt();
//通った場所か記録する変数
isUsed = new boolean[N+1];
//繋がってる頂点を記録するArrayList
list = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<=N;i++)list.add(new ArrayList<Integer>());
while(--N>0){
int U = System.in.nextInt();
int V = System.in.nextInt();
list.get(U).add(V);
list.get(V).add(U);
}
//Xは始点なのでtrueに
isUsed[X] = true;
//DFSで探す
ArrayList<Integer> answer = dfs(X);
//逆順に出力
for(int i=answer.size()-1;i>=0;i--){
System.out.print(answer.get(i));
if(i==0)
System.out.println();
else
System.out.print(' ');
}
System.out.close();
}
//DFS
public static ArrayList<Integer> dfs(int now){
//繋がってる頂点を調べる
for(int next:list.get(now)){
//行ったことあるならスルー
if(isUsed[next])
continue;
//ゴール？
if(next==Y){
ArrayList<Integer> ans = new ArrayList<Integer>();
ans.add(Y);
ans.add(now);
return ans;
}
//通過済みにしてDFS
isUsed[next] = true;
ArrayList<Integer> temp = dfs(next);
//見つかった？
if(temp!=null){
temp.add(now);
return temp;
}
}
//見つからなかったらnullを
return null;
}
}
典型っちゃ典型な気がしました。
D - Stones
問題文はこちら
公式解説通りかと思います。
最初は二分探索で一番多く取れる$A_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{
//各変数の受け取り
int N = System.in.nextInt();
int K = System.in.nextInt();
int[] A = System.in.nextInt(K);
//dp[i]：i個あったときの最適解
int[] dp = new int[N+1];
//いるかわからないけど1個の時を念のため
dp[1] = 1;
//遷移
for(int i=2;i<=N;i++){
int temp = A[0]+(i-A[0]-dp[i-A[0]]);
for(int j=1;j<K&&A[j]<=i;j++){
temp = Math.max(temp,A[j]+(i-A[j]-dp[i-A[j]]));
}
dp[i] = temp;
}
//N個の時の最適解を出力
System.out.println(dp[N]);
System.out.close();
}
}
いやぁ･･･dpだろうなとは思ったんですがねぇ･･･遷移がわからず･･･無念･･･。
E - Apple Baskets on Circle
問題文はこちら
シミュレーションなんてやっていては到底終わりません。
そこで、1周するときにどうなるかを考えてみると、0以外の全ての場所が1個減っているということがわかります。ということで、$A$をソートして小さい方から順に見ていけばループ回数を特定できます。あとは$A_1$から順に、まだ0で無い場所を端数分引いてやれば答えが求まります。
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、Kの受け取り
int N = System.in.nextInt();
long K = System.in.nextLong();
//何番目かも記録しておきたいので二次元で
long[][] A = new long[N][2];
for(int i=0;i<N;i++){
A[i][0] = System.in.nextLong();
A[i][1] = i;
}
//個数でソート
System.sort(A);
//食べたリンゴの総数
long count1 = 0;
//ループ回数
long count2 = 0;
//端数
long tmp = 0;
//少ない方から順に
for(int i=0;i<N;i++){
//このかごが空になるまでループしたときに食べる個数
long temp = (N-i)*(A[i][0]-count2);
//Kを超過してない？
if(count1+temp<K){
count1 += temp;
count2 = A[i][0];
}
//Kを超過した場合は端数を調べてbreak
else{
tmp = (K-count1)%(N-i);
count2 += (K-count1)/(N-i);
break;
}
}
//count2回ループしたときの各かごにある個数を記録
long[] answer = new long[N];
for(int i=0;i<N;i++){
int ind = (int)A[i][1];
answer[ind] = Math.max(0,A[i][0]-count2);
}
//端数合わせをしながら出力
for(int i=0;i<N;i++){
if(answer[i]==0)
System.out.print(0);
else if(tmp-->0)
System.out.print(answer[i]-1);
else
System.out.print(answer[i]);
if(i==N-1)
System.out.println();
else
System.out.print(' ');
}
System.out.close();
}
}
個人的にはDよりかは簡単でした。DP慣れてなさ過ぎでは･･･？
感想
A:易しい。
B:めんどくさい。
C:典型っぽい。特に悩みはしなかった。
D:難しい･･･。
E:ループ回数を特定すれば良いことに気付いてからはサクッと(ペナルティは頂いたけど)。
って感じでした。
DPね･･･難しいね･･･。精進するしかないですね。