※D追記しました(7/21)
はじめに
A～Cはコンテスト中に、Dはコンテスト後に解けたので今回もA～Dを解説していきます。
では、見ていきましょう。
A - A Unique Letter
問題文はこちら
普通に互いに異なるかどうか調べれば良いです。
今回はchar[]として受け取り、if～else文で分岐させてみました。
※やっていることはphysics0523さんの解説の最初の実装例と同じです。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//Sをchar[]として受け取る
char[] S = ss.next().toCharArray();
//全部の条件を書く
if(S[0]!=S[1]&&S[0]!=S[2])
Sys.out.println(S[0]);
else if(S[1]!=S[0]&&S[1]!=S[2])
Sys.out.println(S[1]);
else if(S[2]!=S[0]&&S[2]!=S[1])
Sys.out.println(S[2]);
else
Sys.out.println(-1);
Sys.out.close();
}
}
ちょっと分岐が多くて面倒ではありますが、まぁこんな感じでいいんじゃないでしょうか。
B - Better Students Are Needed!
問題文はこちら
数学、英語、合計の順に見ていけば良いので、全部別の配列に記録して全部ソートして先頭から見ていけば十分な速度で終わります。
普通にソートをすると同点の人同士は出席番号で昇順ソートしてくれるから良いのですが、点数も昇順になってしまい比較するのが少々面倒です(後ろから見てしまうと出席番号が降順になってしまう)。ということで、受け取った点数は±を入れ替えて格納してソートすると高得点が先頭に、かつ同点の場合は出席番号が小さい順に並んでくれます。
なお、既出の生徒か判断するためにArrayListに選んだ生徒をaddしています。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//情報の受け取り
int N = ss.nextInt();
int X = ss.nextInt();
int Y = ss.nextInt();
int Z = ss.nextInt();
//英語(E)、数学(M)、合計点(D)を格納する配列(出席番号も記録する)
int[][] listE = new int[N][2];
int[][] listM = new int[N][2];
int[][] listD = new int[N][2];
for(int i=0;i<N;i++){
int temp = ss.nextInt();
//ソートで役立つから負にして受け取る
listM[i][0] = listD[i][0] = -temp;
listM[i][1] = listD[i][1] = i;
}
for(int i=0;i<N;i++){
int temp = ss.nextInt();
//ソートで役立つから負にして受け取る
listD[i][0] += (listE[i][0] = -temp);
listE[i][1] = i;
}
//全部ソートする
Sys.sort(listM);
Sys.sort(listE);
Sys.sort(listD);
//選んだ人を記録する用
ArrayList<Integer> better = new ArrayList<Integer>();
//X人は普通に格納
for(int i=0;i<X;i++)better.add(listM[i][1]+1);
//Y人、Z人の分は重複しないようチェックしながら格納
for(int i=0,j=0;j<Y;i++){
if(!better.contains(listE[i][1]+1)){
j++;
better.add(listE[i][1]+1);
}
}
for(int i=0,j=0;j<Z;i++){
if(!better.contains(listD[i][1]+1)){
j++;
better.add(listD[i][1]+1);
}
}
//昇順ソートして順に出力
Collections.sort(better);
for(int i=0;i<better.size();i++)Sys.out.println(better.get(i));
Sys.out.close();
}
}
今思えば選択済みの生徒はboolean[]で管理しても良かったのかな。まぁそれでも大差は無いと思います。多分。
C - Changing Jewels
問題文はこちら
実際に試行してみましょう。今現在レベルがnの赤い宝石がα個、青い宝石がβ個あったとしましょう。すると、レベルn-1のそれぞれの宝石の個数は以下の過程で求められます。
・まずレベルnの赤い宝石を変換する(①レベルn-1の赤い宝石がα個、②レベルnの青い宝石がαX個増える)
・次にレベルnの青い宝石を変換する(③レベルn-1の赤い宝石がαX+β個、④レベルn-1の青い宝石が(αX+β)Y個増える)
ということで、Lv1の青い宝石の個数を求めるにはこの工程をN-1回繰り返せば良さそうですね。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//情報の格納
int N = ss.nextInt();
int X = ss.nextInt();
int Y = ss.nextInt();
//正直いらなかったけど一応分岐
if(N==1){
Sys.out.println(0);
}
else{
//初期値を格納
long red = 1;
long blue = 0;
//レベルが1になるまでやり続ける
while(N-->1){
blue += red*X;
red += blue;
blue *= Y;
}
//最後は青い宝石の個数を出力
Sys.out.println(blue);
}
Sys.out.close();
}
}
ちょっと理解するのに時間がかかってしまいました。Nが十分に小さいのでこれでできましたが、Nが大きかったらどうなんでしょう(普通にMAX_VALUE超えそうだから別の方法をとる必要があるだろうなぁ…)。
D - Draw Your Cards
問題文はこちら
※このコードでACは取れましたが、計算量的に嘘解法となります。ご注意下さい。
普通に試行してみましょう。
ArrayList<LinkedList<Integer>>で場に出ているカードを、int[]で何手目に食べられたか格納し、順にPを受け取っていきます。二分探索で置ける場所を探し、見つかればLinkedListの先頭にadd、無ければ新しくLinkedListを作ってそこにaddし、Kと同じ枚数重なっているか見れば良いです。
まぁ実装自体はそんなに難しくないのでコードを見ていきましょう。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//N、Kの取得
int N = ss.nextInt();
int K = ss.nextInt();
//答え用配列(最初ArrayListにしたらTLEした)
int[] answer = new int[N];
//初期値は-1にしておく
Arrays.fill(answer,-1);
//場の情報を記録する用
ArrayList<LinkedList<Integer>> ba = new ArrayList<LinkedList<Integer>>();
//N個分Pを受け取る
for(int i=0;i<N;i++){
//Pを受け取り、二分探索でPを探す
int P = ss.nextInt();
int temp = upsearch(ba,P);
//見つからなかった？
if(temp==ba.size()){
//新しくリストに加える(見つからなかった=最大なので末尾に加えれば昇順のまま)
LinkedList<Integer> forAdd = new LinkedList<Integer>();
forAdd.add(P);
ba.add(forAdd);
}
//リストの先頭を比較したかったので先頭に加える
else{
ba.get(temp).addFirst(P);
}
//もしKに達していたらanswerに記録して食べる
if(ba.get(temp).size()==K){
for(ListIterator<Integer> number = ba.get(temp).listIterator(0);number.hasNext();){
answer[number.next()-1] = i+1;
}
ba.remove(temp);
}
}
//答えを順に出力
for(int ans:answer){
Sys.out.println(ans);
}
Sys.out.close();
}
//二分探索用メソッド
public static int upsearchs(ArrayList<LinkedList<Integer>> nums,int num){
int a=0,b=nums.size()-1,ans=nums.size(),c=-1;
while(a-b<1){
c=(a+b)/2;
if(nums.get(c).getFirst()>=num)b=(ans=c)-1;
else a=c+1;
}
return ans;
}
}
実は初めてLinkedList使ったんですよね。ArrayListの時と変わらなかったので正直LinkedListじゃなくても良い気もしますが…。
追記
上記のコードではremoveにO(N)かかってしまうので、ケースによっては740msくらいかかります(今回のテストケースにはなかったから高速なだけ)。
ということで、TreeMapを使った方法を用いましょう。
removeがO(logN)に抑えられますので、高速になります。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//N、K、Pの取得
int N = ss.nextInt();
int K = ss.nextInt();
int[] answer = new int[N];
int[] P = new int[N];
for(int i=0;i<N;i++)P[i]=ss.nextInt()-1; //後々楽だからPは-1した値で
//初期値は-1で
Arrays.fill(answer,-1);
//場の情報を記録するMap
TreeMap<Integer,LinkedList<Integer>> ba = new TreeMap<Integer,LinkedList<Integer>>();
for(int i=0,j=1;i<N;i++,j++){
//intじゃnullの時受け取れないからIntegerで
Integer temp = ba.ceilingKey(P[i]);
//結果に応じたListを格納
LinkedList<Integer> tmp = temp!=null?ba.remove(temp):new LinkedList<Integer>();
//カードを重ねる(新しく山を作る)
tmp.add(P[i]);
//K枚になったか？
if(tmp.size()==K){
final int ii = j;
tmp.forEach(t -> answer[t]=ii); //answerに食べられたタイミングを記録
}else{
ba.put(P[i],tmp); //まだKに達していないならMapに戻す
}
}
//最後番号順に出力
for(int ans:answer)Sys.out.println(ans);
Sys.out.flush();
}
}
ただ、テストケースだと前述のコードの方が速いんですよね…。全ケースがKが大きくてなかなか食べないとかNがさほど大きくないとかなんでしょうか…。
感想
A:これまでのAより実装がめんどくさい感覚だった。
B:公式解説が天才過ぎる。常人にはこれしか思いつかなかったよ…。
C:気付けばサクッと解ける。個人的にはCにしては優しいと感じた。
D:出力する順番を読み間違えて時間を潰してしまった…悔しい…。
って感じでした。
Dが緑diffだったのでCまでを如何に早く解けるか、って感じの勝負だったのではないでしょうか。ただ、個人的にはDも解きたかった…未練です…。