LoginSignup
0
0
@viral_8

ABC351A～Fの解答[Java]

Posted at

はじめに

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

なお、僕のライブラリに関しては提出結果をご覧ください。
では見ていきましょう。

A - The bottom of the ninth

問題文はこちら

$A$の総和から$B$の総和を引いて$1$加えた値が答えになるのでそれを求めました。

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

		//A、Bの総和を求める
		long A = MathFunction.sum(sc.nextInt(9));
		long B = MathFunction.sum(sc.nextInt(8));

  		//差+1の出力
		out.println(A-B+1);

		out.close();
	}
}

B - Spot the Difference

問題文はこちら

ちょうど$1$箇所のみ異なるので、異なる箇所を見つけたら出力するように実装しました。

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、A、Bの受け取り
		int N = sc.nextInt();
		char[][] A = sc.nextCharArray(N);
		char[][] B = sc.nextCharArray(N);

  		//全探索
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(A[i][j]!=B[i][j]){
					out.println((i+1)+" "+(j+1));
				}
			}
		}

		out.close();
	}
}

C - Merge the balls

問題文はこちら

$N$回の操作で出現するボールは$N$個であり、単純に隣り合うボールの数字が一緒なら足し合わせて片方消す、という処理になるので削除は最大でも$N-1$回しか起きず、比較も最大でも$2N-3$回しか起きないことがわかるので、愚直にシミュレーションを行なうことで十分高速に答えを求められます。

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

  		//シミュレーション
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		while(N-->0){

  			//Aの受け取り
			int A = sc.nextInt();
			deq.add(A);

   			//操作を行なう
			while(deq.size()>1){
				int a1 = deq.pollLast();
				int a2 = deq.pollLast();
				if(a1==a2){
					deq.add(a1+1);
				}
				else{
					deq.add(a2);
					deq.add(a1);
					break;
				}
			}
		}

  		//個数の出力
		out.println(deq.size());

		out.close();
	}
}

D - Grid and Magnet

問題文はこちら

自由に行き来できるマスは事前に連結しておき、そのマスから移動できる、磁石によって束縛されてしまうマスを数え上げることで答えを求めることができます。

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

	private static final int[] dx = {1,-1,0,0};
	private static final int[] dy = {0,0,1,-1};

	public static void main(String[] args){

		//H、W、Sの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		final char[][] S = sc.nextCharArray(H);

  		//自由に行き来できるマスの連結と、
		//そのマスから行ける磁石で束縛されるマスの記録
		final UnionFind uf = new UnionFind(H*W);
		HashMap<Integer,ArrayList<Integer>> memo = new HashMap<>();
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				memo.put(i*W+j,new ArrayList<>());
				if(S[i][j]!='#'&&check(i,j,S)){
					for(int k=0;k<4;k++){
						int nx = i+dx[k];
						int ny = j+dy[k];
						if(MathFunction.rangeCheck(nx,0,H) &&
						   MathFunction.rangeCheck(ny,0,W)
						){
							if(check(nx,ny,S))
								uf.unite(i*W+j,nx*W+ny);
							memo.get(i*W+j).add(nx*W+ny);
						}
					}
				}
				memo.get(i*W+j).add(i*W+j);
			}
		}

  		//各連結成分ごとに集計
		HashMap<Integer,TreeSet<Integer>> map = new HashMap<>();
		for(int i=0;i<H*W;i++){
			if(!map.containsKey(uf.root(i)))
				map.put(uf.root(i),new TreeSet<>());
			map.get(uf.root(i)).addAll(memo.get(i));
		}
		int ans = 0;
		for(TreeSet<Integer> set:map.values())
			ans = Math.max(ans,set.size());

   		//最大値の出力
		out.println(ans);

		out.close();
	}

 	//磁石によって束縛されるマスか判定するメソッド
	private static boolean check(int x,int y,char[][] S){
		for(int i=0;i<4;i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(MathFunction.rangeCheck(nx,0,S.length) &&
			   MathFunction.rangeCheck(ny,0,S[0].length) &&
			   S[nx][ny]=='#'
			){
				return false;
			}
		}
		return true;
	}
}

実装下手くそ過ぎてペナ出しまくって地獄と化しました…。

E - Jump Distance Sum

問題文はこちら

斜めへの移動しかできないので、$xy$平面を$45$度回転させた座標系で考えれば答えは行き来できる座標間のマンハッタン距離の総和に帰着できます。
$x$座標、$y$座標の差の総和は累積和の要領で求めることができ、行き来できるかどうかは元の座標$(X,Y)$に対して$X+Y$が偶数か奇数かで分けることができます。

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

  		//座標の総和の偶奇で分けて管理
		ArrayList<Point> odd = new ArrayList<>();
		ArrayList<Point> even = new ArrayList<>();
		for(int i=0;i<N;i++){
			int X = sc.nextInt();
			int Y = sc.nextInt();
			if((X+Y)%2==0)
				even.add(new Point(X,Y));
			else
				odd.add(new Point(X,Y));
		}

  		//座標変換
		for(Point p:even){
			int x = (p.y+p.x)/2;
			int y = (p.y-p.x)/2;
			p.x = x;
			p.y = y;
		}
		for(Point p:odd){
			int x = (p.y+p.x-1)/2;
			int y = (p.y-p.x-1)/2;
			p.x = x;
			p.y = y;
		}

  		//マンハッタン距離の総和を求める
		long ans = 0;
		long bef;
		long sum;
		Collections.sort(even,(a,b)->Integer.compare(a.x,b.x));
		bef = 0;
		sum = 0;
		for(int i=0;i<even.size();i++){
			sum += (even.get(i).x-bef)*i;
			ans += sum;
			bef = even.get(i).x;
		}
		Collections.sort(even,(a,b)->Integer.compare(a.y,b.y));
		bef = 0;
		sum = 0;
		for(int i=0;i<even.size();i++){
			sum += (even.get(i).y-bef)*i;
			ans += sum;
			bef = even.get(i).y;
		}
		Collections.sort(odd,(a,b)->Integer.compare(a.x,b.x));
		bef = 0;
		sum = 0;
		for(int i=0;i<odd.size();i++){
			sum += (odd.get(i).x-bef)*i;
			ans += sum;
			bef = odd.get(i).x;
		}
		Collections.sort(odd,(a,b)->Integer.compare(a.y,b.y));
		bef = 0;
		sum = 0;
		for(int i=0;i<odd.size();i++){
			sum += (odd.get(i).y-bef)*i;
			ans += sum;
			bef = odd.get(i).y;
		}

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

		out.close();
	}
}

これも解法自体はすぐ気付いたんですが、実装下手過ぎて…うぅ…。

F - Double Sum

問題文はこちら

ソート済みの$A$を$B$とすると、
$$\sum_{i=1}^N \sum_{j=i+1}^N \max(A_j-A_i,0)
= \frac{1}{2} \left( \sum_{i=1}^N \sum_{j=i+1}^N(B_j-B_i) +
\sum_{i=1}^N \sum_{j=i+1}^N(A_j-A_i) \right)$$
に変形できるので、これを求めました。
これは、$(B_j-B_i)+(A_j-A_i)$が以下のような性質を持つことに由来します。
$$(B_j-B_i)+(A_j-A_i)=
\begin{cases}
2(A_j-A_i) & \max(A_j-A_i,0) \gt 0 \\
0 & \max(A_j-A_i,0) = 0
\end{cases}
$$

F.java
import java.util.Scanner;
import java.util.Arrays;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

  		//N、Aの受け取り
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i=0;i<N;i++)
			A[i] = sc.nextInt();

   		//ソート済み配列の構築
		int[] sortedA = A.clone();
		Arrays.sort(sortedA);

  		//上記の式の値を求める
		long ans = 0;
		long sum = 0;
		for(int i=0;i<N;i++){
			ans += sum-(long)sortedA[N-i-1]*i;
			sum += sortedA[N-i-1];
		}
		sum = 0;
		for(int i=0;i<N;i++){
			ans += sum-(long)A[N-i-1]*i;
			sum += A[N-i-1];
		}

  		//答えの出力
		System.out.println(ans>>1);
	}
}

これは気付けないな…。

感想

A,B,C:易しい
D:かなり手こずった…
E:実装下手くそ過ぎた…
F:難しい…><
って感じでした。

レート駄々下がり…悲しすぎる…。

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