2
0

More than 1 year has passed since last update.

ABC260A~Dの解答[Java]

Last updated at Posted at 2022-07-18

※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個増える)

プレゼンテーション1.jpg

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

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0