ABC354A～Fの解答[Java]

はじめに

今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれを載せようと思います。

なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。

A - Exponential Plant

問題文はこちら

問題文の通りに愚直に求めました。

A.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//Hの受け取り
		int H = sc.nextInt();

  		//愚直に求める
		int ans = 0;
		int sum = 0;
		while(sum<=H)
			sum |= 1<<ans++;

   		//答えの出力
		out.println(ans);

		out.close();
	}
}

今思えばsum = sum<<1|1とかでも良かったですね。

B - AtCoder Janken 2

問題文はこちら

$C_i$それぞれの値よりも$\mathrm{sum}(C)$の方が重要なので、$S$と$\mathrm{sum}(C)$を求めて解を出力しました。

B.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//Nの受け取り
		int N = sc.nextInt();

  		//SとTの受け取り
		String[] S = new String[N];
		int T = 0;
		for(int i=0;i<N;i++){
			S[i] = sc.next();
			T += sc.nextInt();
		}

  		//問題文の通りの答えを求めて出力
		Arrays.sort(S);
		out.println(S[T%N]);

		out.close();
	}
}

C - AtCoder Magics

問題文はこちら

正当性の考え方は公式解説に任せますが、$A$で($A$が一緒なら$C$の降順で)ソートすることで、これまでの$C$の最小値のみを保持することで捨てることのできるカードを判定することができます。

C.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//Nの受け取り
		int N = sc.nextInt();

  		//カードの受け取り
		int[][] cards = new int[N][];
		for(int i=0;i<N;i++){
			int A = sc.nextInt();
			int C = sc.nextInt();
			cards[i] = new int[]{A,C,i+1};
		}

  		//Aの昇順(Cの降順)でソート
		Arrays.sort(cards,(a,b)->a[0]==b[0]?Integer.compare(b[1],a[1]):Integer.compare(a[0],b[0]));

  		//愚直にカードを捨てる
		int minC = Integer.MAX_VALUE;
		boolean[] removed = new boolean[N];
		for(int i=N-1;i>=0;i--){
			if(cards[N-1][0]>cards[i][0]&&minC<cards[i][1])
				removed[i] = true;
			minC = Math.min(minC,cards[i][1]);
		}

  		//残ったカードを記録
		ArrayList<Integer> ans = new ArrayList<>();
		for(int i=0;i<N;i++)
			if(!removed[i])
				ans.add(cards[i][2]);

    	//昇順に直して出力
		Collections.sort(ans);
		out.println(ans.size());
		out.println(ans);

		out.close();
	}
}

あんまり正当性とか考えないで実装してぶん投げたので内心ドキドキでした()。

D - AtCoder Wallpaper

問題文はこちら

$(0,0)$を左下、$(4,2)$を右上とする長方形の範囲の図形に着目すると、この長方形の繰り返しであることに気付きます。あとは、簡単に考えるために下の図のように各模様を分割し、各模様がいくつ含まれているかで考えました。

D.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//A、B、C、Dの受け取り
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		long D = sc.nextLong();

  		//各部分ごとの個数を求める
		long D1 = (C-A+MathFunction.remainder(A+4,4))/4 * ((D-B+MathFunction.remainder(B+1,2))/2);
		long D2 = (C-A+MathFunction.remainder(A+1,4))/4 * ((D-B+MathFunction.remainder(B+0,2))/2);
		long D3 = (C-A+MathFunction.remainder(A+3,4))/4 * ((D-B+MathFunction.remainder(B+1,2))/2);
		long D4 = (C-A+MathFunction.remainder(A+2,4))/4 * ((D-B+MathFunction.remainder(B+0,2))/2);
		long D5 = (C-A+MathFunction.remainder(A+3,4))/4 * ((D-B+MathFunction.remainder(B+0,2))/2);
		long D6 = (C-A+MathFunction.remainder(A+2,4))/4 * ((D-B+MathFunction.remainder(B+1,2))/2);

  		//2倍にして出力
		out.println(D1+D2+D3*2+D4*2+D5+D6);

		out.close();
	}
}

細かいミスが目立って時間かかっちゃった…。

E - Remove Pairs

問題文はこちら

場の状態を考えると、最大でも$2^{18}$通りと、そこまで大きい値ではないので、メモ化再帰で答えを求めました。

E.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	//再帰に渡す用のクラス変数
	private static int[][] graph;
	private static int set = 0;

	public static void main(String[] args){

		//N、カードの受け取り
		int N = sc.nextInt();
		int[][] cards = sc.nextInt(N,2);

  		//一緒に除けるカードを記録
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for(int i=0;i<N;i++)
			list.add(new ArrayList<>());
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				if(i!=j&&(cards[i][0]==cards[j][0]||cards[i][1]==cards[j][1]))
					list.get(i).add(j);

     	//高速化のために配列に変換
		graph = new int[N][];
		for(int i=0;i<N;i++)
			graph[i] = Converter.toIntArray(list.get(i));

   		//再帰で答えを求める
		out.println(dfs()?"Takahashi":"Aoki");

		out.close();
	}

 	//メモ化
	private static final HashMap<Integer,Boolean> map = new HashMap<>();

 	//再帰用メソッド
	private static boolean dfs(){
		if(map.containsKey(set))
			return map.get(set);

   		//1通りでも自分が勝てるパターンがあればそのパターンを選んだ方が良いのでその時点で復帰
		for(int i=0;i<graph.length;i++){
			if((set&(1<<i))>0)
				continue;
			for(int next:graph[i]){
				if((set&(1<<next))>0)
					continue;
				set |= 1<<i;
				set |= 1<<next;
				boolean ans = !dfs();
				set ^= 1<<i;
				set ^= 1<<next;
				if(ans){
					map.put(set,true);
					return true;
				}
			}
		}

  		//勝ちパターンが無ければ負け確定なのでfalse
		map.put(set,false);
		return false;
	}
}

最初メモ化しなくても通るでしょ、とかいう安易な考えで投げて数ペナ頂きました()。

F - Useless for LIS

問題文はこちら

公式解説の通りです。

F.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//Tの受け取り
		int T = sc.nextInt();

  		//ケースごとに処理
		while(T-->0){

  			//N、Aの受け取り
			int N = sc.nextInt();
			int[] A = sc.nextInt(N);

   			//Aのlisを求める
			int ans = ArrayFunction.lis(A)+1;

   			//自分が最後のlisを求める
			int[] r = lis(A);

   			//符号反転&左右反転
			A = ArrayFunction.reBuild(A,i->-i);
			ArrayFunction.reverseRange(A,0,N);

   			//自分が最初のlisを求める
			int[] l = lis(A);

   			//逆順のままなので反転して戻す
			ArrayFunction.reverseRange(l,0,N);

   			//自身を選んだ時のlisがA全体としてのlisと一致するなら追加
			ArrayList<Integer> answer = new ArrayList<>();
			for(int i=0;i<N;i++)
				if(l[i]+r[i]==ans)
					answer.add(i+1);

     		//答えの出力
			out.println(answer.size());
			out.println(answer);
		}

		out.close();
	}

 	//lisの途中経過を返すメソッド
	private static int[] lis(int[] array){
		int[] answer = new int[array.length];
		int[] list = new int[array.length];
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int i=0;i<array.length;i++){
			int index = Searcher.upSearch(list,array[i]);
			list[index] = Math.min(list[index],array[i]);
			answer[i] = index+1;
		}
		return answer;
	}
}

う～ん…気づけないねぇ…。

感想

A,B:易しい
C:ちょっと不安があった
D:Dにしては難しい…
E:しょうもないミスをしてしまった…
F:解きたかった…
って感じでした。

いやぁ…F解けないとレート維持できないのに…。悔しい…。