ABC340A～Fの解答[Java]

はじめに

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

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

A - Arithmetic Progression

問題文はこちら

$A$が$B$になるまでループを回しながら$D$だけ加算していけば目的の数列を構築できます。

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

  		//Bになるまでループ
		for(;A!=B;A+=D)
			out.print(A+" ");

   		//最後は空白じゃなくて改行
		out.println(B);

		out.close();
	}
}

B - Append

問題文はこちら

動的に要素を追加したいのでArrayList<Integer>で処理しました。

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

		//Qの受け取り
		int Q = sc.nextInt();
		ArrayList<Integer> A = new ArrayList<>();

  		//問題文通りに処理
		while(Q-->0){
			int t = sc.nextInt();
			if(t==1)
				A.add(sc.nextInt());
			else
				out.println(A.get(A.size()-sc.nextInt()));
		}

		out.close();
	}
}

C - Divide and Divide

問題文はこちら

一番大きい値を貪欲に選んでいくことを考えると、値をkey、個数をvalueとしたTreeMap<Long,Long>で処理できると考え、これで実装しました。

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

  		//Mapで黒板に書いてある値を管理
		TreeMap<Long,Long> map = new TreeMap<>();
		long ans = 0;
		map.put(N,1L);

  		//操作できなくなるまで回す
		while(map.size()>0){
			Map.Entry<Long,Long> entry = map.pollLastEntry();
			long key = entry.getKey();
			long val = entry.getValue();
   
			if(key>1){ //操作できるなら次の値を書き込む
				ans += key*val;
				map.merge(key/2,val,Long::sum);
				map.merge((key+1)/2,val,Long::sum);
			}
		}

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

		out.close();
	}
}

D - Super Takahashi Bros.

問題文はこちら

ダイクストラ法で解ける見た目なので(単一頂点からの最短経路問題なので)、それで解きました。

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

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

  		//隣接行列の構築
		ArrayList<ArrayList<int[]>> list = new ArrayList<>();
		for(int i=0;i<=N;i++)
			list.add(new ArrayList<>());
		for(int i=1;i<N;i++){
			int A = sc.nextInt();
			int B = sc.nextInt();
			int X = sc.nextInt();
			list.get(i).add(new int[]{i+1,A});
			list.get(i).add(new int[]{X,B});
		}

  		//Queueに乗せるようのクラス
		class Node{
			int now;
			long val;
			public Node(int n,long v){
				now = n;
				val = v;
			}
		}

  		//初期値設定
		PriorityQueue<Node> queue = new PriorityQueue<>((a,b)->Long.compare(a.val,b.val));
		queue.add(new Node(1,0));
		long[] cost = new long[N+1];
		Arrays.fill(cost,Long.MAX_VALUE);
		cost[1] = 0;

  		//ダイクストラ
		while(queue.size()>0){
			Node node = queue.poll();
			if(node.val==cost[node.now]){
				for(int[] path:list.get(node.now)){
					if(cost[node.now]+path[1]<cost[path[0]]){
						cost[path[0]] = cost[node.now]+path[1];
						queue.add(new Node(path[0],cost[path[0]]));
					}
				}
			}
		}

  		//答えの出力
		out.println(cost[N]);

		out.close();
	}
}

E - Mancala 2

問題文はこちら

区間への加算が必要なので遅延セグメントツリーで処理しました。

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

  		//セグ木に乗せたかったのでラッパークラスで
		Long[] A = new Long[N];
		for(int i=0;i<N;i++)
			A[i] = sc.nextLong();

   		//Bの受け取り
		int[] B = sc.nextInt(M);

  		//遅延セグ木
		LazySegmentTree<Long,Long> lSegT = new LazySegmentTree<>(A,0L,0L,false){
			public Long mapping(Long a,Long b){
				return Long.sum(a,b);
			}
			public Long composition(Long a,Long b){
				return Long.sum(a,b);
			}
			public Long function(Long a,Long b){
				return Long.sum(a,b);
			}
		};

  		//Bに沿って処理
		for(int num:B){
			long sum = lSegT.get(num);
			lSegT.update(num,0L);
			lSegT.apply(0,N,sum/N);
			sum %= N;
			if(N<sum+num+1)
				lSegT.apply(0,(int)sum+num+1-N,1L);
			if(num<N)
				lSegT.apply(num+1,Math.min(N,num+(int)sum+1),1L);
		}

  		//石の数を求めて配列に
		Long[] ans = new Long[N];
		for(int i=0;i<N;i++)
			ans[i] = lSegT.get(i);
		out.println(ans);

		out.close();
	}
}

定数倍が重いのもあってちょっと実行時間がキツめ…。

F - S = 1

問題文はこちら

証明は公式解説に任せますが、拡張ユークリッドの互除法を用いて解きました。

F.java

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

  		//X、Yの受け取り
		long X = sc.nextLong();
		long Y = sc.nextLong();

  		//何となく絶対値で拡張ユークリッド
		long[] d = extendedGcd(Math.abs(X),Math.abs(Y));

  		//最大公約数が2より大きいなら無理
		if(d[0]>2){
			System.out.println(-1);
			return;
		}

  		//値調整
		if(d[0]==1){
			d[1] *= 2;
			d[2] *= 2;
		}
		if(Long.signum(X)==Long.signum(Y)){
			d[1] *= -1;
		}

  		//答えの出力
		System.out.println(d[2]+" "+d[1]);
	}

 	//拡張ユークリッドの互除法
  	//aX+bY=gcd(a,b)を満たすとき、new long[]{gcd(a,b), X, Y}が返ってくる
	private static long[] extendedGcd(long a,long b){
		if(b==0){
			return new long[]{a,1,0};
		}
		long[] d = extendedGcd(b,a%b);
		d[1] -= a/b*d[2];
		return new long[]{d[0],d[2],d[1]};
	}
}

符号こねくり回してしまって本番中解けなかった…。

感想

A,B,C,D:易しい
E:遅延セグ木はFなイメージが少しあったけど、まぁ別解もあるからEが妥当なのかな
F:うぉぉぉぉぉぉぉぉぉん😭😭😭😭😭😭😭😭😭😭
って感じでした。

ギリギリ青に留まれましたが、次回が…怖い…。