LoginSignup
0
0

More than 1 year has passed since last update.

@viral_8

ABC297A～Gの解答[Java]

Last updated at Posted at 2023-04-10

はじめに

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

では見ていきましょう。

なお、ライブラリの内容は提出結果より確認出来ます。

A - Double Click

問題文はこちら

先頭から見ていって、差が$D$以下の箇所を見つけたら時間を変数に入れてループを抜けることで一番最初の時刻を出力させました。

A.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、D、T1の受け取り
		int N = sc.nextInt();
		int D = sc.nextInt();
		int T = sc.nextInt();

		//答えを格納する変数(初期値は-1)
		int ans = -1;

		//T2～TNを順に見ていく
		while(--N>0){

			//次のクリックの時間の受け取り
			int t = sc.nextInt();

			//ダブルクリック判定？
			if(t-T<=D){

				//ansを更新してループを抜ける
				ans = t;
				break;
			}

			//クリックの時間を更新
			T = t;
		}

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

最初に$T_1$を受け取っているのでループ回数が$N-1$回になるようwhileの条件は--N>0になっています。

B - chess960

問題文はこちら

S.indexOf("B")とS.lastIndexOf("B")の偶奇が異なるか、S.indexOf("K")がS.indexOf("R")とS.lastIndexOf("R")の間かを判定することで解きました。

B.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//Sの受け取り
		String S = sc.next();

		//各条件を満たしているか求める
		boolean isTrue = true;
		isTrue &= (S.lastIndexOf("B")-S.indexOf("B"))%2==1;
		isTrue &= S.indexOf("R")<S.indexOf("K");
		isTrue &= S.indexOf("K")<S.lastIndexOf("R");

		//全部満たしていた？
		out.println(isTrue?"Yes":"No");
 
		out.close();
	}
}

ユーザー解説にもありますが、正規表現を用いて解くこともできます。

C - PC on the Table

問題文はこちら

各$S$の中のTTを先頭から貪欲にPCに置き換えれば良いので、replaceメソッドを用いて解きました。

C.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//H、W、Sの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		String[] S = sc.next(H);

		//各Sに対してreplaceメソッドを適用
		for(int i=0;i<H;i++)
			S[i] = S[i].replace("TT","PC");

		//各Sを改行区切りで出力
		out.println(S,"\n");
 
		out.close();
	}
}

比較的易しめですかね。

D - Count Subtractions

問題文はこちら

公式解説にありますが、引き算を行える回数を求めることで高速に処理することができると考えて、$A=B$になるまでそれを繰り返すことで答えを求めました。

D.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//A、Bの受け取り
		long A = sc.nextLong();
		long B = sc.nextLong();

		//回数を記録する変数
		long ans = 0;

		//条件を満たすまで繰り返す
		while(A!=B){

			//大きい方から小さい方を引けるだけ引く(大きい方が小さい方の倍数だったときの為に-1してから割り算している)
			if(A<B){
				ans += (B-1)/A;
				B -= (B-1)/A*A;
			}
			else{
				ans += (A-1)/B;
				A -= (A-1)/B*B;
			}
		}

		//回数の出力
		out.println(ans);
 
		out.close();
	}
}

$A$、$B$が$0$になる時を考えるのがめんどくさいなと思って上記のように回数を求めました。

E - Kth Takoyaki Set

問題文はこちら

TreeSetを二つ準備し、片方のSet(以下Set1)に$A$を入れます。Set1の最小値を$v$とすると、Set1に各$i$に対する$v+A[i]$を、もう片方のSet(以下Set2)に$v$を入れることで、1から$K$番目までの金額をset2に構築することで、$K$番目の金額を求めました。Setを使っているので重複するものを考慮しなくてすみます。

E.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、K、Aの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] A = sc.nextInt(N);

		//小さい方から金額が確定しているもののset
		TreeSet<Long> set = new TreeSet<>();
		//保留中の金額のset
		TreeSet<Long> thinking = new TreeSet<>();

		//Aをthinkingに入れる
		for(int i=0;i<N;i++)
			thinking.add((long)A[i]);

		//setにK個入るまで繰り返す
		while(set.size()<K){

			//現状一番小さい金額を取り出す
			long now = thinking.pollFirst();

			//now+A[i]をthinkingに入れる
			for(int i=0;i<N;i++)
				thinking.add(now+A[i]);

			//now未満の金額はsetの中以外に存在しないのでsetに入れる
			set.add(now);
		}

		//K番目=setで一番大きい数字を出力
		out.println(set.pollLast());
 
		out.close();
	}
}

上記の実装だと構築途中でset1とset2に保持され得る要素数の合計は$N(K+1)$個以下なので、メモリに関しても心配する必要は無さそうです。

追記

set1の方はTreeSetを使わなくても、一番大きいものさえ保持出来れば良いのでlong型変数で処理できますね。

E改.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] A = sc.nextInt(N);
		long ans = 0;
		TreeSet<Long> thinking = new TreeSet<>();
		for(int i=0;i<N;i++)
			thinking.add((long)A[i]);
		while(K-->0){
			ans = thinking.pollFirst();
			for(int i=0;i<N;i++)
				thinking.add(ans+A[i]);
		}
		out.println(ans);
 
		out.close();
	}
}

F - Minimum Bounding Box 2

問題文はこちら

公式解説の通りです。内容は重複すると思いますが、備忘録も兼ねて説明的なものを書いてみます。

とあるマス$(i,j)$が選ばれた$K$個のマスを囲む長方形に含まれるようなマスの選び方は以下の通りに求められます。

まず以下のような、$x$座標が$i$未満の範囲、$i$より大きい範囲、$y$座標が$j$未満の範囲、$j$より大きい範囲の4つの区域を考えます(青の部分)。

スライド1.PNG

すると、各範囲内のみで$K$個のマスが選ばれた時は黄色のマスが長方形に含まれないと考えられます。ですので、全体から$K$個選ぶ通りから各範囲内で$K$個選ぶ通り数を引けば答えを求められそうですが、ただ範囲内での選び方を求めるだけでは以下の4つの範囲内のみで$K$個選んだ時の組み合わせを重複して求めていることになります(緑の部分)。

スライド2.PNG

ですので、全体から$K$個選ぶ通りから各範囲内で$K$個選ぶ通り数を引いた後、この部分の選び方を再び加算してあげることで、$(i,j)$が選ばれた$K$個のマスを囲む長方形に含まれるようなマスの選び方を正しく求められます。

F.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//H、W、Kの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();

		//mod
		final int mod = 998244353;

		//階乗とその逆元を求めておく
		Factorial fact = new Factorial(H*W,mod);

		//答え用変数
		long ans = 0;

		//全マスからK個選ぶ通り数
		long all = fact.getCombi(H*W,K);

		//全マスに対して、そのマスが長方形に含まれる通り数を求める
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){

				//上記の各領域内でのK個選ぶ通り数を求める
				long m1 = fact.getCombi(H*(j-1),K);
				long m2 = fact.getCombi(H*(W-j),K);
				long m3 = fact.getCombi((i-1)*W,K);
				long m4 = fact.getCombi((H-i)*W,K);
				long p1 = fact.getCombi((i-1)*(j-1),K);
				long p2 = fact.getCombi((i-1)*(W-j),K);
				long p3 = fact.getCombi((H-i)*(j-1),K);
				long p4 = fact.getCombi((H-i)*(W-j),K);

				//全通りから(i,j)が選ばれないマスの選び方を引いたものを加算
				long sub = p1-m1+p2-m2+p3-m3+p4-m4;
				ans += all+sub;
				ans %= mod;
			}
		}

		//負の値になっている可能性があるのでその時はmodを加算
		if(ans<0)
			ans += mod;

		//ansを全通り数で割って出力
		out.println(ans*MathFunction.modPow(all,mod-2,mod)%mod);
 
		out.close();
	}
}

全然思いつかなかった…。

G - Constrained Nim 2

問題文はこちら

公式解説の通りです。

G.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、L、Rの受け取り
		int N = sc.nextInt();
		int L = sc.nextInt();
		int R = sc.nextInt();

		//grundy数の排他的論理和を求める
		int now = 0;
		while(N-->0){
			int A = sc.nextInt();
			now ^= (A%(L+R))/L;
		}

		//0より大きいなら先手が勝ち、0なら後手が勝つ
		out.println(now>0?"First":"Second");
 
		out.close();
	}
}

grundy数を知らなかったので勉強になりました。

感想

A,B,C:易しい
D:そんなにループ回数が多くないことに気付いてからはサクッと解けた
E:特に何も考えずに提出してみたら通った
F,G:わかりません…
って感じでした。

Eまでは早く解けましたが、ちょっと難しくなると一気に手が出なくなってしまいますね…。精進不足な部分が露呈したような感じでした。

0
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
Sign upLogin
0
0