ABC358A～D、Gの解答[Java]

はじめに

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

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

A - Welcome to AtCoder Land

問題文はこちら

愚直に調べれば良いです。

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

		//受け取ってAtCoder Landか判定して出力
		out.println(
			sc.next().equals("AtCoder") &&
			sc.next().equals("Land")
			?"Yes":"No");


		out.close();
	}
}

B - Ticket Counter

問題文はこちら

$i$番目の人が購入を終えた時刻を$C_i$とすると、$i+1$番目の人が購入を終える時刻は$\max(C_i,T_{i+1})+A$です。
これを先頭から順に行なうことで答えが求まります。

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

  		//直前の人が購入し終えた時刻
		int bef = 0;

  		//順に処理
		while(N-->0){
			int T = sc.nextInt();
			bef = Math.max(bef+A,T+A);
			out.println(bef);
		}

		out.close();
	}
}

C - Popcorn

問題文はこちら

bit全探索で解きました。
味$i$のポップコーンがあるとき、$i$番目のビットを立てた整数として保持することでいくつかの売り場を訪れたときの購入可能なポップコーンの味の集合をビット論理和で扱うことができ、全種類の味のポップコーンを購入できる=bitCountがMとなる組み合わせを数え上げることで本問題を解くことができます。

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、Sの受け取り(Sは整数に変換)
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] S = new int[N];
		for(int i=0;i<N;i++){
			char[] subS = sc.nextCharArray();
			for(int j=0;j<M;j++)
				if(subS[j]=='o')
					S[i] |= 1<<j;
		}

  		//bit全探索
		int min = Integer.MAX_VALUE;
		for(int i=0;i<1<<N;i++){
			int sum = 0;
			for(int j=0;j<N;j++)
				if((i&(1<<j))>0)
					sum |= S[j];
			if(Integer.bitCount(sum)==M)
				min = Math.min(min,Integer.bitCount(i));
		}

  		//最小値の出力
		out.println(min);

		out.close();
	}
}

D - Souvenirs

問題文はこちら

$B$を降順に見ていけば、まだ渡していない箱の中で$B_i$より大きい$A$の集合の最小値を貪欲に選ぶことで本問題を解くことができます。

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

  		//A、Bはソートしても構わないのでソート
		Arrays.sort(A);
		Arrays.sort(B);
		ArrayUtil.reverseRange(B,0,M); //(降順で扱いたいので降順に)

  		//数え上げ用変数
		long sum = 0;

  		//今までに見たAの位置を記録する用
		int index = N-1;

  		//Bの降順に貪欲法を適用
		for(int b:B){
			while(0<=index&&b<=A[index])
				queue.add(A[index--]);

    		//もし該当する箱が無ければ構築不可なので-1
			if(queue.size()==0){
				System.out.println(-1);
				return;
			}
			sum += queue.poll();
		}

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

		out.close();
	}
}

G - AtCoder Tour

問題文はこちら

マス目がそんなに多くないので、$\min(K,HW)$回移動したあと$K$回経過するまでそのマスに留まったときの楽しさを全探索することで最大値を得ることができます。これは、最大の$A$に最終的に留まった方が最適であることに由来します(もし移動した方が有利である場合、そのマスが最大であることに矛盾します)。

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

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

	public static void main(String[] args){

		//H、W、K、Si、Sj、Aの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();
		int Si = sc.nextInt()-1;
		int Sj = sc.nextInt()-1;
		long[][] A = sc.nextLong(H,W);

  		//各位置における、そのマスにくるまでに得た楽しさの総和の最大値を記録する用の配列
		long[][] dp1 = new long[H][W];
		for(long[] temp:dp1)
			Arrays.fill(temp,-Long.MAX_VALUE);
		dp1[Si][Sj] = 0;

  		//無駄な処理はしたくないので到達可能なマスを記録する用のSet
		HashSet<Point> set = new HashSet<>();
		set.add(new Point(Si,Sj));

  		//最大値記録用の変数
		long ans = 0;

  		//遷移用の配列
		long[][] dp2 = new long[H][W];

  		//min(K,HW)回繰り返す
		for(int now=1;now<=Math.min(K,H*W);now++){

  			//移動してみる
			HashSet<Point> next = new HashSet<>();
			for(int i=0;i<H;i++)
				System.arraycopy(dp1[i],0,dp2[i],0,W);
			for(Point p:set){
				for(int i=0;i<5;i++){
					int nx = p.x+dx[i];
					int ny = p.y+dy[i];
					if(MathFunction.rangeCheck(nx,0,H)&&
					   MathFunction.rangeCheck(ny,0,W)){
						dp2[nx][ny] = Math.max(dp2[nx][ny],dp1[p.x][p.y]+A[nx][ny]);
						next.add(new Point(nx,ny));
					}
				}
			}
			set.addAll(next);

   			//今いる場所に留まった場合の最大値を求める
			for(Point p:set){
				ans = Math.max(ans,(K-now)*A[p.x][p.y]+dp2[p.x][p.y]);
			}

   			//配列交換(メモリ削減用)
			var temp = dp1;
			dp1 = dp2;
			dp2 = temp;
		}

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

		out.close();
	}
}

ペナは出したけど、気づけて良かった…。

感想

A,B,C,D:易しい
G:Gにしては易しい
って感じでした。

比較的速解きっぽかったのでペナ出したのが良くなかった…。