LoginSignup
2
0
@viral_8

ABC339の解答[Java]

Posted at

はじめに

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

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

A - TLD

問題文はこちら

splitメソッドは正規表現として処理されてしまうので、エスケープさせる必要があります。

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

		//入力を.で分割
		String[] S = sc.next().split("\\.");

  		//末尾の文字列の出力
		out.println(S[S.length-1]);

		out.close();
	}
}

最初気付かなくてめちゃくちゃ時間かけちゃいました…。

B - Langton's Takahashi

問題文はこちら

移動回数がそんなに大きくないので愚直にシミュレーションしました。

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

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

  		//初期状態構築
		char[][] map = new char[H][W];
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				map[i][j] = '.';
			}
		}

  		//遷移
		int x = 0;
		int y = 0;
		int d = 0;
		while(N-->0){
			if(map[x][y]=='.'){
				map[x][y] = '#';
				d = (d+1)&3;
			}
			else{
				map[x][y] = '.';
				d = (d+3)&3;
			}
			switch(d){
				case 0 -> x = (x+H-1)%H;
				case 1 -> y = (y+1)%W;
				case 2 -> x = (x+1)%H;
				case 3 -> y = (y+W-1)%W;
			}
		}

  		//今の状態の出力
		out.println(map);

		out.close();
	}
}

C - Perfect Bus

問題文はこちら

最初を$0$人と仮定して先頭から順に見ていって、一番人数が少なかった状態の時が負ならその人数分最初に乗車していたと見ることができるので、最後の状態にその人数分足してあげることで答えが求まります。

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

  		//最初を0にして一つ一つ追いながら最小値を記録
		long sum = 0;
		long min = 0;
		for(int num:A){
			sum += num;
			min = Math.min(min,sum);
		}

  		//足りなかった人数分足して出力
		out.println(sum-min);

		out.close();
	}
}

D - Synchronized Players

問題文はこちら

Pは2箇所だけで、それぞれの位置の組み合わせは$O(N^4)$なので、BFSで全通り列挙しながら操作回数の最小値を求めました。

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

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

  		//Pの位置の取得
		ArrayDeque<Point> deq = new ArrayDeque<>();
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(S[i][j]=='P'){
					deq.add(new Point(i,j));
				}
			}
		}

  		//探索済みか確認する用
		boolean[] checked = new boolean[1<<24];
		checked[hash(deq.peekFirst(),deq.peekLast())] = true;

  		//操作回数
		int ans = 0;

  		//全探索
		while(deq.size()>0){
			ans++;
			ArrayDeque<Point> next = new ArrayDeque<>();

   			//今の状態から移動できる状態へ遷移
			while(deq.size()>0){
				Point p1 = deq.pollFirst();
				Point p2 = deq.pollFirst();
				for(int i=0;i<4;i++){
					Point np1 = new Point(p1.x+dx[i],p1.y+dy[i]);
					Point np2 = new Point(p2.x+dx[i],p2.y+dy[i]);
					if(np1.x<0)
						np1.x++;
					if(N<=np1.x)
						np1.x--;
					if(np1.y<0)
						np1.y++;
					if(N<=np1.y)
						np1.y--;
					if(np2.x<0)
						np2.x++;
					if(N<=np2.x)
						np2.x--;
					if(np2.y<0)
						np2.y++;
					if(N<=np2.y)
						np2.y--;
					if(S[np1.x][np1.y]=='#'){
						np1.x -= dx[i];
						np1.y -= dy[i];
					}
					if(S[np2.x][np2.y]=='#'){
						np2.x -= dx[i];
						np2.y -= dy[i];
					}

     				//同じ位置にいるなら出力して終了
					if(np1.equals(np2)){
						System.out.println(ans);
						return;
					}

     				//未探索なら探索候補に追加
					int hash = hash(np1,np2);
					if(!checked[hash]){
						checked[hash] = true;
						next.add(np1);
						next.add(np2);
					}
				}
			}
			deq = next;
		}

  		//ループを抜けた=同じ位置にいることがないので-1
		out.println(-1);

		out.close();
	}

 	//ハッシュ値計算用
	private static int hash(Point p1,Point p2){
		int hash1 = (p1.x<<6)|p1.y;
		int hash2 = (p2.x<<6)|p2.y;
		return (Math.min(hash1,hash2)<<12)|Math.max(hash1,hash2);
	}
}

E - Smooth Subsequence

問題文はこちら

動的計画法で解きました。
$A_i \pm D$の最大値$+1$で$\mathrm{dp}[A_i]$を更新して遷移しました。
区間最大値と更新はセグメント木を用いています。

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

  		//DPテーブル構築
		SegmentTree<Integer> segT = new SegmentTree<>(500_000,0,true){
			public Integer function(Integer a,Integer b){
				return Integer.max(a,b);
			}
		};

  		//遷移
		for(int num:A){
			int max = segT.query(Math.max(1,num-D),Math.min(500_000,num+D));
			segT.update(num,max+1);
		}

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

		out.close();
	}
}

F - Product Equality

問題文はこちら

適当に$2^{31}-1$とその手前の素数($2^{31}-19$)の二つであまりを取り、この値を元に$A_i$と$A_j$を全探索しました。

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

	//法とする素数二つ
	private static final int mod1 = 2147483647;
	private static final int mod2 = 2147483629;

	//素数二つで割ったあまりを管理するクラス
	static class Node{
		long A,B;
		Node(long a,long b){
			A = a;
			B = b;
		}
		public Node multiply(Node n){
			return new Node(A*n.A%mod1,B*n.B%mod2);
		}
		public boolean equals(Object o){
			if(o instanceof Node n){
				return A==n.A&&B==n.B;
			}
			return false;
		}
		public int hashCode(){
			return (int)((A>>1)^B);
		}
	}

	public static void main(String[] args){

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

  		//mapに記録しながらAの受け取り
		Node[] A = new Node[N];
		HashMap<Node,Integer> map = new HashMap<>(N<<2);
		for(int i=0;i<N;i++){
			char[] s = sc.nextCharArray();
			long num1 = 0;
			long num2 = 0;
			for(char c:s){
				num1 = (num1*10+c-'0')%mod1;
				num2 = (num2*10+c-'0')%mod2;
			}
			A[i] = new Node(num1,num2);
			map.merge(A[i],1,Integer::sum);
		}

  		//全組み合わせを調べる
		long ans = 0;
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				ans += map.getOrDefault(A[i].multiply(A[j]),0);

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

		out.close();
	}
}

なお、$A_i < 10^{1000}$なので、予め$A$をソートしておいて$A_i \times A_j \ge 10^{1000}$となるような組み合わせを枝切りするようにするとjava.math.BigIntegerを用いても実行時間内に処理できます。

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

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

  		//Aの受け取り
		HashMap<BigInteger,Integer> map = new HashMap<>(N<<2);
		BigInteger[] A = new BigInteger[N];
		for(int i=0;i<N;i++){
			A[i] = sc.nextBigInteger();
			map.merge(A[i],1,Integer::sum);
		}

  		//枝切りしながら全探索
		long ans = 0;
		Arrays.sort(A);
		BigInteger LIMIT = BigInteger.TEN.pow(1000);
		Loop:for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				BigInteger mult = A[i].multiply(A[j]);
				if(mult.compareTo(LIMIT)>0)
					continue Loop;
				ans += map.getOrDefault(mult,0);
			}
		}

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

		out.close();
	}
}

本番中はこれで通しました()。

G - Smaller Sum

問題文はこちら

公式解説の通りです。
merge-sort treeに相当するクラスを作って処理しました。

G.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の受け取り
		int N = sc.nextInt();
		long[] A = sc.nextLong(N);

  		//merg-sort treeの構築
		MergeSortTree mst = new MergeSortTree(A,Integer.MAX_VALUE,true);

  		//累積和として再構築
		MergeSortTree sumMst = new MergeSortTree(mst,arr->{
			long[] ans = new long[arr.length+1];
			for(int i=0;i<arr.length;i++)
				ans[i+1] = ans[i]+arr[i];
			return ans;
		});

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

  		//直前の答えの記録用
		long bef = 0;

  		//クエリに答える
		while(Q-->0){

  			//α、β、γの受け取り
			long alpha = sc.nextLong();
			long beta = sc.nextLong();
			long gamma = sc.nextLong();

   			//復元
			int L = (int)(alpha^bef);
			int R = (int)(beta^bef);
			int X = (int)(gamma^bef);

   			//答えを求める
			bef = sumMst.query(L,R,0,Long::sum,arr->{
				int a = 1;
				int b = arr.length-1;
				int ans = 0;
				while(a-b<1){
					int c = a+b>>1;
					if(arr[c]-arr[c-1]<=X)
						a = (ans=c)+1;
					else
						b = c-1;
				}
				return arr[ans];
			});

   			//出力
			out.println(bef);
		}

		out.close();
	}
}

//merge-sort tree相当のクラス
final class MergeSortTree{
	private final long[][] node;
	private final int N,size;

	public MergeSortTree(final int n,final long def,final boolean is1indexed){
		int num = 2;
		while(num<n<<1){
			num <<= 1;
		}
		N = num;
		size = (num>>1)-(is1indexed?1:0);
		node = new long[N][];
		updateAll(new long[0],def);
	}

	public MergeSortTree(final long[] arr,final long def,final boolean is1indexed){
		int num = 2;
		while(num<arr.length<<1){
			num <<= 1;
		}
		N = num;
		size = (num>>1)-(is1indexed?1:0);
		node = new long[N][];
		updateAll(arr,def);
	}

	public MergeSortTree(MergeSortTree mst,Function<long[],long[]> mapping){
		N = mst.N;
		size = mst.size;
		node = new long[N][];
		for(int i=1;i<N;i++){
			node[i] = mapping.apply(mst.node[i]);
		}
	}

	public MergeSortTree(final int n,final long def){
		this(n,def,false);
	}

	private void updateAll(final long[] arr,long def){
		for(int i=0;i<arr.length;i++){
			node[i+(N>>1)] = new long[]{arr[i]};
		}
		for(int i=arr.length;i+(N>>1)<node.length;i++){
			node[i+(N>>1)] = new long[]{def};
		}
		for(int i=(N>>1)-1;i>0;i--){
			node[i] = merge(node[i<<1],node[(i<<1)+1]);
		}
	}

	private static long[] merge(long[] a,long[] b){
		long[] ans = new long[a.length+b.length];
		int i = 0;
		int j = 0;
		int k = 0;
		while(i<a.length&&j<b.length){
			if(a[i]<b[j])
				ans[k++] = a[i++];
			else
				ans[k++] = b[j++];
		}
		while(i<a.length)
			ans[k++] = a[i++];
		while(j<b.length)
			ans[k++] = b[j++];
		return ans;
	}

	public long get(final int a){
		return node[a+size][0];
	}

	public long[] sortedArray(){
		return node[1];
	}

	public long query(int l,int r,long def,LongBinaryOperator operator,ToLongFunction<long[]> function){
		l += size;
		r += size;
		long answer = def;
		while(l>0&&r>0&&l<=r){
			if(l%2==1){
				answer = operator.applyAsLong(function.applyAsLong(node[l++]),answer);
			}
			l >>= 1;
			if(r%2==0){
				answer = operator.applyAsLong(answer,function.applyAsLong(node[r--]));
			}
			r >>= 1;
		}
		return answer;
	}
}

感想

A:かなり時間かけちゃった…
B,C:易しい
D:実装に時間かけたが、全探索できるのはすぐ見えて良かった
E:Eにしては易しい
F:枝切り愚直が通って良かった…()
G:全然発想出来なかった…悲しい…
って感じでした。

今回はGまでの理解にそこまで苦労しなかったので全部解けました。
今度は本番中に全部解けるようになりたい…。

2
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
2
0