※D追記しました(7/21)

はじめに

A～Cはコンテスト中に、Dはコンテスト後に解けたので今回もA～Dを解説していきます。

では、見ていきましょう。

A - A Unique Letter

問題文はこちら

普通に互いに異なるかどうか調べれば良いです。
今回はchar[]として受け取り、if～else文で分岐させてみました。
※やっていることはphysics0523さんの解説の最初の実装例と同じです。

A.java

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しています。

B.java

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回繰り返せば良さそうですね。

C.java

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と同じ枚数重なっているか見れば良いです。

まぁ実装自体はそんなに難しくないのでコードを見ていきましょう。

D.java

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)に抑えられますので、高速になります。

D改.java

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も解きたかった…未練です…。