LoginSignup
0
0
@viral_8

ABC332A～Fの解答[Java]

Posted at

はじめに

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

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

A - Online Shopping

問題文はこちら

総額を求めて$S$円未満かを判定して処理しました。

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){

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

  		//総額を求める
		long sum = 0;
		for(int i=0;i<N;i++)
			sum += sc.nextInt()*sc.nextInt();

   		//送料がかかるなら加算
		if(sum<P)
			sum += K;

   		//出力
		out.println(sum);

		out.close();
	}
}

B - Glass and Mug

問題文はこちら

問題文をそのままコードに落とし込んでシミュレーションしました。

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){

		//K、G、Mの受け取り
		int K = sc.nextInt();
		int G = sc.nextInt();
		int M = sc.nextInt();

  		//シミュレーション
		int gla = 0;
		int mug = 0;
		while(K-->0){
			if(gla==G)
				gla = 0;
			else if(mug==0)
				mug = M;
			else{
				int sub = Math.min(G-gla,mug);
				mug -= sub;
				gla += sub;
			}
		}

  		//答えの出力
		out.println(gla+" "+mug);

		out.close();
	}
}

C - T-shirts

問題文はこちら

Bと同様にシミュレーションで解きました。
なるべく無地のTシャツをきた方が有利なのでそのように処理してます。

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、Mの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

  		//ロゴ入りTシャツ(着れる物)
		int L = 0;

  		//洗濯待ち
		int subM = 0;
		int subL = 0;

  		//順に処理
		String S = sc.next();
		for(char c:S.toCharArray()){

  			//洗濯する
			if(c=='0'){
				M += subM;
				L += subL;
				subM = 0;
				subL = 0;
			}

   			//なるべく無地を使う
			else if(c=='1'){
				if(M>0){
					M--;
					subM++;
				}
				else{
					L = Math.max(L-1,0); //無ければ1着購入
					subL++;
				}
			}

   			//ロゴ入りを着る
			else{
				L = Math.max(L-1,0); //無ければ1着購入
				subL++;
			}
		}

  		//最終的に所有している(=購入した)ロゴ入りTシャツの枚数を答える
		out.println(L+subL);
		out.close();
	}
}

D - Swapping Puzzle

問題文はこちら

$H$、$W$が小さいので順列全探索で解きました。
操作回数はバブルソートで求めています。

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){

		//H、W、A、Bの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] A = sc.nextInt(H,W);
		int[][] B = sc.nextInt(H,W);

  		//順列全探索
		int[] r = new int[H];
		int[] c = new int[W];
		Arrays.setAll(r,i->i);
		int ans = Integer.MAX_VALUE;
		do{
			Arrays.setAll(c,i->i);
			Loop:do{

   				//一致してないなら次の候補へ
				for(int i=0;i<H;i++)
					for(int j=0;j<W;j++)
						if(A[r[i]][c[j]]!=B[i][j])
							continue Loop;

       			//全一致したなら最小値更新
				ans = Math.min(ans,count(r,c));
    
			}while(ArrayFunction.nextPermutation(c));
		}while(ArrayFunction.nextPermutation(r));

  		//ちゃんと一致させることができたかで場合分け
		out.println(ans==Integer.MAX_VALUE?-1:ans);

		out.close();
	}

 	//操作回数を数えるメソッド
	private static int count(int[] r,int[] c){

 		//配列をコピーして、その配列をバブルソートする工程で操作回数を数える
		int count = 0;
		int[] subR = Arrays.copyOf(r,r.length);
		for(int i=0;i<r.length;i++){
			for(int j=1;j<r.length-i;j++){
				if(subR[j-1]>subR[j]){
					ArrayFunction.swap(subR,j-1,j);
					count++;
				}
			}
		}
		int[] subC = Arrays.copyOf(c,c.length);
		for(int i=0;i<c.length;i++){
			for(int j=1;j<c.length-i;j++){
				if(subC[j-1]>subC[j]){
					ArrayFunction.swap(subC,j-1,j);
					count++;
				}
			}
		}
		return count;
	}
}

BFSする、という手法もありましたね(Twitterで見かけて確かに、になりました)。

E - Lucky bag

問題文はこちら

公式解説の通りです。
$$\sum_{i}{(x_i-\bar{x})^2}$$
$$=\sum_{i}{x_i^2}-\frac{(\sum_{j}{w_j})^2}{D}$$
より、$\sum_{i}{x_i^2}$の最小値を求めています(これのおかげでDPテーブルはlongで扱えます)。

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);

	public static void main(String[] args){

		//N、D、Wの受け取り
		int N = sc.nextInt();
		int D = sc.nextInt();
		long[] W = sc.nextLong(N);

  		//DPテーブルの構築
		long[][] dp = new long[D+1][1<<N];
		for(int i=1;i<1<<N;i++){
			for(int j=0;j<N;j++)
				if((i&1<<j)>0)
					dp[1][i] += W[j];
			dp[1][i] *= dp[1][i];
		}

  		//遷移
		for(int i=2;i<=D;i++){
			for(int j=1;j<1<<N;j++){
				int S = (j-1)&j;
				dp[i][j] = dp[i-1][j];
				while(S>0){
					long num = dp[i-1][j^S]+dp[1][S];
					if(num<dp[i][j])
						dp[i][j] = num;
					S = (S-1)&j;
				}
			}
		}

  		//答えの出力
		long sum = MathFunction.sum(W);
		out.println((dp[D][(1<<N)-1]*D-sum*sum)/(double)D/D);

		out.close();
	}
}

思いつけたら良かったけど…う～ん…。

F - Random Update Query

問題文はこちら

遅延セグ木で解きました。
処理は一次関数$f(x)=ax+b$の形で表せるので、compositionなどもそのような処理になっています。

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);

	//mod
	private static final int MOD = 998244353;

	//一次関数を表すクラス
	private static class F{
		final long a,b;
		F(long a,long b){
			this.a = a;
			this.b = b;
		}
	}

	public static void main(String[] args){

		//N、M、Aの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		Long[] A = new Long[N]; //セグ木に載せるためにLongで
		for(int i=0;i<N;i++){
			long num = sc.nextLong();
			if(MOD<=num)
				num -= MOD;
			A[i] = num;
		}

  		//遅延セグ木の宣言
		LazySegmentTree<Long,F> lSegT = new LazySegmentTree<>(A,0L,new F(1,0),false){
			public Long function(Long a,Long b){
				return a; //何だって良いのでテキトーに
			}

   			//一次関数を適用するメソッド
			public Long mapping(Long a,F f){
				long ans = a*f.a%MOD+f.b;
				if(MOD<=ans)
					ans -= MOD;
				return ans;
			}

   			//一次関数を合成するメソッド
			public F composition(F a,F b){
				long c = a.a*b.a%MOD;
				long d = b.a*a.b%MOD+b.b;
				if(MOD<=d)
					d -= MOD;
				return new F(c,d);
			}
		};

  		//前計算用
		Factorial fact = new Factorial(200_000,MOD);

  		//クエリの処理
		while(M-->0){

  			//L、R、Xの受け取り
			int L = sc.nextInt();
			int R = sc.nextInt();
			int X = sc.nextInt();
			if(MOD<=X)
				X -= MOD;

    		//一次関数の形に直してapply
			long a = (R-L)*fact.getInverse(R-L+1)%MOD;
			long b = X*fact.getInverse(R-L+1)%MOD;
			lSegT.apply(L-1,R,new F(a,b));
		}

  		//答えの取得と出力
		long[] ans = new long[N];
		for(int i=0;i<N;i++)
			ans[i] = lSegT.get(i);
		out.println(ans);

		out.close();
	}
}

ずっと答え合わなくてどこミスったんだろう…とコンテスト後も考えていたんですが、まさかのライブラリがバグっておりました…。
こ、殺してくれ…。

感想

A,B,C,D:易しめ
E:何も見えてこなかった…
F:遅延セグ木とわかったのに…わかったのに…
って感じでした。

前日のARCでもレート下がったので、非常に悲しい…。まぁ、ライブラリのバグが見つかったと思えば…。

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