はじめに
今回のコンテストも前回同様企業コンということもあり、少々難易度が高く感じました。
A、Bはコンテスト中に書いたものをそのまま、C、Dはコンテスト後に解いたのでそのコードを載せます。
それでは解説してきます。
A - 2^N
問題文はこちら
単純に2をN乗してやりましょう。
A.java
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの取得
int N = readInt();
//2^Nを出力(flushも)
println(pow(2,N));
flush();
}
/*テンプレ一覧
・int readInt() ：int型取得(行まるごと)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
・long pow(long1,long2) ：long1^long2を返す(最小二乗法)
*/
public static int readInt()throws IOException{return Integer.parseInt(br.readLine());}
public static void println(Object T){pw.println(T);}
public static void flush(){pw.flush();}
public static long pow(long a,long b){long ans=1;while(b>0){if((b&1)==1)ans*=a;a*=a;b>>=1;}return ans;}
}
特に悩まないですね。普通にwhileやforでN回かけてもいいですし、以下のように書き換えても良いんじゃないでしょうか。
A改.java
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの取得
int N = readInt();
//2^Nを出力(flushも)
println(1<<N);
flush();
}
/*テンプレ一覧
・int readInt() ：int型取得(行まるごと)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
・long pow(long1,long2) ：long1^long2を返す(最小二乗法)
*/
public static int readInt()throws IOException{return Integer.parseInt(br.readLine());}
public static void println(Object T){pw.println(T);}
public static void flush(){pw.flush();}
public static long pow(long a,long b){long ans=1;while(b>0){if((b&1)==1)ans*=a;a*=a;b>>=1;}return ans;}
}
2^Nなのでシフト演算子を使えばN回2をかけたことになります。
B - Batters
問題文はこちら
4マス分準備して実際に試行してやれば十分終わります。マスの参照は後ろから見ていくことに注意しましょう。
B.java
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、Aiの取得
int N = readInt();
int[] A = readInt(N);
//マスの準備
int[] masu = new int[4];
//解答用変数
int P = 0;
//A1から順に試行
for(int i=0;i<N;i++){
//0番目にコマをおく
masu[0]++;
//後ろから順にコマを動かしていく
for(int j=masu.length-1;j>=0;j--){
//4より大きくなった？
if(j+A[i]>=masu.length){
//解答用変数に加算
P+=masu[j];
//マスの中身は0に
masu[j] = 0;
}
else{
//コマを目的の位置に持っていく
masu[j+A[i]] = masu[j];
//元のマスは空に
masu[j] = 0;
}
}
}
//答えの出力(flushも)
println(P);
flush();
}
/*テンプレ一覧
・int readInt() ：int型取得(行まるごと)
・int[] readInt(整数) ：int型配列取得(一行分)(空白あり)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
*/
public static int readInt()throws IOException{return Integer.parseInt(br.readLine());}
public static int[] readInt(int n)throws IOException{int[] ans=new int[n];String[] str=br.readLine().split(" ");for(int i=0;i<n;i++)ans[i]=Integer.parseInt(str[i]);return ans;}
public static void println(Object T){pw.println(T);}
public static void flush(){pw.flush();}
}
マスには高々1個しか存在しないそうなので、boolean型で管理しても良さそうでしたね。
C - Filling 3x3 array
問題文はこちら
マスすべてを全探索(1≦マスの番号≦30)すると、$O(30^9)$で当然TLEです。
ということで、マス目のうち、左上の2×2マスに注目しましょう。このマスが決まればh1〜3、w1〜3が与えられていますから、残りの5マスは必然的に一つの値に定まります。これを利用して$O(30^4)$で解いてやりましょう。
C.java
import java.io.*;
import java.util.*;
import java.math.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//それぞれの値の取得
String[] str = reads(" ");
int[] h = new int[3];
h[0] = Integer.parseInt(str[0]);
h[1] = Integer.parseInt(str[1]);
h[2] = Integer.parseInt(str[2]);
int[] w = new int[3];
w[0] = Integer.parseInt(str[3]);
w[1] = Integer.parseInt(str[4]);
w[2] = Integer.parseInt(str[5]);
//解答用変数
int ans = 0;
//左上
for(int i=1;i<31;i++){
//中央上
for(int j=1;j<31;j++){
//中央左
for(int i1=1;i1<31;i1++){
//中央
for(int j1=1;j1<31;j1++){
//左下
int h1 = h[0]-(i+j);
//中央下
int h2 = h[1]-(i1+j1);
//右上
int w1 = w[0]-(i+i1);
//中央右
int w2 = w[1]-(j+j1);
//下一列から求めた右下
int h3 = w[2]-(h1+h2);
//右一列から求めた右下
int w3 = h[2]-(w1+w2);
if(
//下一列からでも右一列からでも右下は等しい値が求まったか？
h3==w3&&
//それぞれの値は適正か？
Math.min(h1,h2)>0&&
Math.min(w1,w2)>0&&
h3>0
) ans++; //解答に加算
}
}
}
}
//答えの出力(flushも)
println(ans);
flush();
}
/*テンプレ一覧
・String[] reads(String) ：一行分をstr区切りで取得(String型配列)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
*/
public static String[] reads(String str)throws IOException{return br.readLine().split(str);}
public static void println(Object T){pw.println(T);}
public static void flush(){pw.flush();}
}
hとwがややこしくて本番はACできませんでした。悔しい…。
D - Union of Interval
問題文はこちら
私の解答はmiscalculation53さんの解説に近い(というか同じ？)ものになっています。
まず、二次元配列に区間の情報を入れ、ソート。すると前後の情報が結合できるかはLと一つ前のRを比較するだけで良くなります。ちなみにソートはLだけでも良いですし、Lが同じところをさらにRを条件にソートしても良いと思います。ただし、バブルソートでは終わらないのでマージソート、ヒープソートなどを実装する必要があることに注意しましょう。
D.java
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの取得
int N = parseInt(read());
//区間の取得
Integer[][] LR = new Integer[N][2];
for(int i=0;i<N;i++){
String[] temp = reads(" ");
LR[i][0] = parseInt(temp[0]);
LR[i][1] = parseInt(temp[1]);
}
//マージソート(念の為Lが同じ時はRでもソート)
deepSort(LR);
//最初の情報の格納
int L = LR[0][0];
int R = LR[0][1];
//一つ前まで見る
for(int i=1;i<N-1;i++){
//Rが更新できる？
if(R>=LR[i][0]){
//念の為LとRどちらも参照(Lはしなくていい)
L = Math.min(LR[i][0],L);
R = Math.max(LR[i][1],R);
}
else{
//被った区間がなかったら出力して情報を更新
println(L+" "+R);
L = LR[i][0];
R = LR[i][1];
}
}
//最後の一つは更新可能かどうかで出力内容を変える
if(R>=LR[LR.length-1][0])
println(Math.min(LR[LR.length-1][0],L)+" "+Math.max(LR[LR.length-1][1],R));
else{
println(L+" "+R);
println(LR[LR.length-1][0]+" "+LR[LR.length-1][1]);
}
//最後に
flush();
}
/*テンプレ一覧
・String read() ：一行取得(String型)
・String[] reads(String) ：一行分をstr区切りで取得(String型配列)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
・void deepSort(Integer[][]) ：[i][0]を比較して昇順並べ替え([i][0]が同じなら[i][1]で比較)
・int parseInt(String) ：String型の数字をint型に変換して返す
*/
public static String read()throws IOException{return br.readLine();}
public static String[] reads(String str)throws IOException{return br.readLine().split(str);}
public static void println(Object T){pw.println(T);}
public static void println(){pw.println();}
public static void flush(){pw.flush();}
//二次元配列用マージソート(テンプレ記事に記載なし)
public static void deepSort(Integer[][] list){
//もし配列の中身が1個以下ならソートのしようがないので返す
if(list.length<2) return;
//半分に分ける
Integer[][] list1 = new Integer[list.length/2][];
Integer[][] list2 = new Integer[list.length-list1.length][];
System.arraycopy(list,0,list1,0,list1.length);
System.arraycopy(list,list1.length,list2,0,list2.length);
//それぞれをマージソート
deepSort(list1);
deepSort(list2);
//一時的に保存するリスト(速度を上げたいなら配列で実装してみてもいいかも？)
ArrayList<Integer[]> newList = new ArrayList<Integer[]>();
//index用変数
int i=0,j=0;
//どっちかがなくなるまで繰り返す
while(i<list1.length&&j<list2.length){
//一時的に格納
Integer[] temp1 = list1[i];
Integer[] temp2 = list2[j];
//１つ目はtemp1の方が小さい？
if(temp1[0]<temp2[0])
newList.add(list1[i++]);
//1つ目はtemp2の方が小さい？
else if(temp1[0]>temp2[0])
newList.add(list2[j++]);
//２つ目も同様に比較
else if(temp1[1]<temp2[1])
newList.add(list1[i++]);
else
newList.add(list2[j++]);
}
//最後に余った要素を全部格納
while(i<list1.length)
newList.add(list1[i++]);
while(j<list2.length)
newList.add(list2[j++]);
//元の配列に返却
for(int k=0;k<list.length;k++)
list[k]=newList.get(k);
}
public static int parseInt(String str){char[] temp=str.toCharArray();int ans=0;for(int i=0;i<temp.length;i++)ans=ans*10+(int)temp[i]-48;return ans;}
}
書きはしませんが、forは最後までやって最後に結果に関わらず出力するだけで良いですね…。コメントアウトしていて気づきました。
総評
A:やるだけ。
B:さまざまなやり方がありそう。とりあえず、試行してしまえば良い。
C:hとwがごっちゃにならないよう注意しよう(戒め)
D:本番でマージソートバグらせました。事前準備は念入りに！(自分用)
って感じでした。
コードには細心の注意を払うべきだと実感したコンテストでした。