はじめに
このコンテストは企業コンということもあり、若干難しく感じました。急いで書いたコードなので少々汚いです。ご了承ください。
では、解説していきます。
A - You should output ARC, though this is ABC.
問題文はこちら
普通に配列として受け取って処理しちゃいましょう。
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{
//RCの受け取り(String型のまま)
String[] RC = reads(" ");
//配列の受け取り(二次元配列)
String[][] a = {reads(" "),reads(" ")};
//出力
println(a[parseInt(RC[0])-1][parseInt(RC[1])-1]);
flush();
}
/*テンプレ一覧
・String[] reads(String) ：一行分をstr区切りで取得(String型配列)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
・int parseInt(String) ：String型の数字をint型に変換して返す
*/
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();}
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;}
}
ちょっと汚いですね…。まぁ数字でわざわざ処理する必要も無いし…。
B - Light It Up
問題文はこちら
とりあえずあかりを持っている人と全員との距離を全部計算して、一人一人の「あかりを持っている人との最短距離」を算出、その中で最大値を出力してやりましょう。誤差が怖いのでルートは最後に取っています。
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、Kの取得
String[] str = reads(" ");
int N = Integer.parseInt(str[0]);
int K = Integer.parseInt(str[1]);
//あかりを持っている人の取得
str = reads(" ");
int[] A = new int[K];
for(int i=0;i<K;i++){
A[i] = Integer.parseInt(str[i]);
}
//座標の取得
int[][] XY = new int[N][2];
for(int i=0;i<N;i++){
str = reads(" ");
XY[i][0] = Integer.parseInt(str[0]);
XY[i][1] = Integer.parseInt(str[1]);
}
//全員の距離の記録
long[][] distances = new long[K][N];
for(int i=0;i<K;i++){
long x = XY[A[i]-1][0];
long y = XY[A[i]-1][1];
for(int k=0;k<N;k++){
distances[i][k] = (x-XY[k][0])*(x-XY[k][0])+(y-XY[k][1])*(y-XY[k][1]);
}
}
//一人ずつ最短距離を求め、最短の中で最大距離を探す
long ans = 0;
for(int i=0;i<N;i++){
long dis = Long.MAX_VALUE;
for(int j=0;j<K;j++){
dis = Math.min(dis,distances[j][i]);
}
if(ans<dis)
ans = dis;
}
//ルートとって出力
println(Math.sqrt(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();}
}
最初計算ミスっててめちゃくちゃ焦りました。
C - ±1 Operation 1
問題文はこちら
普通に計算してやれば良いです。ただ、条件分岐は必要なのでそこに注意しましょう。
C.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{
//各値の取得
String[] str = reads(" ");
long X = Long.parseLong(str[0]);
long A = Long.parseLong(str[1]);
long D = Long.parseLong(str[2]);
long N = Long.parseLong(str[3])-1; //初項を除く為に-1
//計算しなくて良い？
if(X==A)
println(0);
//公差0なら初項との差
else if(D==0)
println(Math.abs(A-X));
//数列の外側？
else if((X>(A+D*N))^(D<0))
println(Math.abs(X-A-D*N));
else if((X<A)^(D<0))
println(Math.abs(A-X));
//それ以外
else{
//近いところの項を求める
long near = ((X-A)/D)*D+A;
//計算が合ってるかわからなかったので周辺200項も調べといた(実際は±1くらいで良い)
long ans = Long.MAX_VALUE;
for(int i=-100;i<101;i++){
ans = Math.min(Math.abs(near-D*i-X),ans);
}
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();}
}
ミスりまくって±100個の項も調べるというよくわからないことをやってしまいました…。まぁそれでも十分高速なので±1にしても実行速度はさほど変わらなそう。
D - ±1 Operation 2
問題文はこちら
コンテスト中は全然解法が思いつかなかったです…。以下の説明はほぼ公式解説の下位互換なので公式解説見てもらった方がいい気もしますが、私自身の考えを整理するためにも書きます。
まず、XよりもAiが小さい箇所を考えると(Aiはソート済みとする)、以下のような式で操作回数を表せます。(Ak≦X、A(k+1)>X)
\sum^{k}_{i=1}{(X-A_i)}=kX-\sum^{k}_{i=1}A_i (1)
同様にXよりもAiが大きい箇所を考えると、
\sum^{N}_{i=k+1}{(A_i-X)}=\sum^{N}_{i=k+1}A_i-(N-k)X (2)
したがって、全部の要素をXにする最短操作は以下の式で求められます。
(1)+(2)=\sum^{N}_{i=k+1}A_i-\sum^{k}_{i=1}A_i+kX-(N-k)X
=\sum^{N}_{i=1}A_i-2\sum^{k}_{i=1}A_i+(2k-N)X
ということで、上記の式をそのまま実装してやりましょう。
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、Qの取得
String[] str = reads(" ");
int N = parseInt(str[0]);
int Q = parseInt(str[1]);
//数列の取得
str = reads(" ");
int[] Asub = new int[N];
for(int i=0;i<N;i++){
Asub[i] = parseInt(str[i]);
}
//昇順並べ替え
sort(Asub);
//初項からindexまでの和を求めておく
long[] A = new long[N];
A[0] = Asub[0];
for(int i=1;i<N;i++){
A[i] = A[i-1] + Asub[i];
}
//順に調べる
for(int i=0;i<Q;i++){
//Xの取得
long X = parseInt(read());
//初項より下？(和から計算するとズレるため条件分岐で除去
if(X<=A[0]){
println(A[A.length-1]-A.length*X);
continue;
}
//二分探索でXと同じかそれより小さい最大の値のindexを探す
int point = downsearch(Asub,(int)X);
println(A[A.length-1]+((point+1)*X-A[point])*2-A.length*X);
}
flush();
}
/*テンプレ一覧
・String read() ：一行取得(String型)
・String[] reads(String) ：一行分をstr区切りで取得(String型配列)
・void println(何か) ：改行あり出力
・void flush() ：出力のflush
・void sort(int[]) ：昇順並べ替え
・Integer[] changeIntDim1(int[])：int型配列をInteger型配列に変換(sort用)
・int parseInt(String) ：String型の数字をint型に変換して返す
・int downsearch(int[],int) ：二分探索でnumを探してindexを返す(見つからない場合はnum以下のインデックスを、num以下が無ければ-1)
*/
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 flush(){pw.flush();}
public static void sort(int[] lis){Integer[] list=changeIntDim1(lis);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);sort(list1);sort(list2);ArrayList<Integer> newList=new ArrayList<Integer>();int i=0,j=0;while(i<list1.length&&j<list2.length){int temp1=list1[i];int temp2=list2[j];if(temp1<temp2)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++)lis[k]=newList.get(k);}
public static Integer[] changeIntDim1(int[] list){Integer[] ans=new Integer[list.length];for(int i=0;i<list.length;i++)ans[i]=list[i];return ans;}
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;}
public static int downsearch(int[] nums,int num){int a=0,b=nums.length-1;if(nums[a]>=num)return a;if(nums[b]<=num)return b;int ans=(a+b)/2;while(a<=b){if(nums[ans]==num)return ans;else if(nums[ans]<num)a=ans+1;else b=ans-1;ans=(a+b)/2;}if(nums[ans]>num)return ans-1;return ans;}
}
実は二分探索使ったの初めてなんですよね。改めて、凄いアルゴリズムだと思いました。
総評
A：やるだけ。易しい。
B：一瞬悩んだが実装さえ思いつけばなんてことはない。
C：初項を除く為にNを-1することを忘れてはいけない…(戒め)
D：アルゴリズムの勉強になりました(累積和って何のことかいまいちまだわかってないけど…)
って感じでした。
難しいけど、凄いやり応えのある問題でした。