はじめに

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

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

A - A Healthy Breakfast

問題文はこちら

StringのindexOfメソッドを用いるとインデックスを得ることができるので、これを使って位置の判定を行ないました。

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

		//Sの受け取り
		String S = sc.next();

  		//インデックスの取得
		int indexR = S.indexOf("R");
		int indexM = S.indexOf("M");

  		//条件判定
		out.println(indexR<indexM?"Yes":"No");

		out.close();
	}
}

B - Vertical Reading

問題文はこちら

問題文の通りに実際に構築して判定しました。

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

		//S、Tの受け取り
		String S = sc.next();
		String T = sc.next();

  		//シミュレーション
		for(int i=1;i<S.length();i++){
			ArrayList<String> list = new ArrayList<>();
			for(int j=0;j<S.length();j+=i)
				list.add(S.substring(j,Math.min(j+i,S.length())));
			for(int j=0;j<i;j++){
				String subS = "";
				for(String s:list)
					if(j<s.length())
						subS += s.charAt(j);

      			//構築できたらさっさと終わらせてしまう
				if(T.equals(subS)){
					System.out.println("Yes");
					return;
				}
			}
		}

  		//ループを抜けた=条件を満たさなかったのでNo
		out.println("No");

		out.close();
	}
}

C - Move It

問題文はこちら

ある箱に荷物が複数入っている場合、一番重いものを残して他のものを動かした方が得なので、残り一個になるまで軽いものから順に取り出して、その総和を求めて上げれば答えが求まります。

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

  		//箱毎に記録
		HashMap<Integer,PriorityQueue<Integer>> map = new HashMap<>();
		for(int i=0;i<N;i++){
			if(!map.containsKey(A[i]))
				map.put(A[i],new PriorityQueue<>());
			map.get(A[i]).add(W[i]);
		}

  		//貪欲法により最適解を求める
		int ans = 0;
		for(PriorityQueue<Integer> q:map.values())
			while(q.size()>1)
				ans += q.poll();

		//出力
		out.println(ans);

		out.close();
	}
}

D - Ghost Ants

問題文はこちら

同じ向きを向いている蟻同士は永遠にすれ違うことはないので、同じ向き同士で二グループに分けておきます。すると、片方のある蟻がすれ違う蟻は他方のグループの蟻のうち、自分との距離が$1$以上$2T$以下である蟻だとわかります。条件を満たす蟻が何匹いるかは事前に位置でソートしておけば二分探索で求まるのでこれで解きました。

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、S、Xの受け取り
		int N = sc.nextInt();
		long T = sc.nextInt();
		char[] S = sc.nextCharArray();
		long[] X = sc.nextLong(N);

  		//右向き左向きごとに記録
		ArrayList<Long> L = new ArrayList<>();
		ArrayList<Long> R = new ArrayList<>();
		for(int i=0;i<N;i++){
			if(S[i]=='0')
				L.add(X[i]);
			else
				R.add(X[i]);
		}

  		//位置でソート
		Collections.sort(L);
		Collections.sort(R);

  		//左向きの蟻を基準に数え上げ
		long ans = 0;
		for(long x:L){
			int index1 = Searcher.upSearch(R,x);
			int index2 = Searcher.upSearch(R,x-T*2);
			ans += index1-index2;
		}

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

		out.close();
	}
}

E - Random Swaps of Balls

問題文はこちら

最初に黒いボールは先頭にあるという条件から、二番目以降に黒いボールがある確率がどのマスも全て等しいです。これを利用すると、先頭に黒いボールがあるときの確率、二番目以降にボールがある確率の$2$つを保持しておけば適切に計算ができます。あとはDPの要領で各操作による確率の変化を計算すれば良いです。

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

	private static final int MOD = 998244353;

	public static void main(String[] args){

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

  		//先頭とそれ以外に黒いボールがある確率
		long main = 1;
		long sub = 0;

  		//高速化のために1/N^2 mod MODを前計算
		long div = MathFunction.modPow((long)N*N%MOD,MOD-2,MOD);

  		//K回操作
		while(K-->0){

  			//遷移
			long nm = (main*(N-1)%MOD*(N-1)+main)%MOD*div%MOD;
			nm += sub*2%MOD*(N-1)%MOD*div%MOD;
			long ns = sub*MathFunction.remainder((long)N*N%MOD-2,MOD)%MOD*div%MOD;
			ns += main*2%MOD*div%MOD;
			main = nm;
			sub = ns;
			if(MOD<=main)
				main -= MOD;
			if(MOD<=sub)
				sub -= MOD;
		}

  		//それぞれの確率を足す
		long ans = main+((long)N*(N+1)/2-1)%MOD*sub%MOD;

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

		out.close();
	}
}

かなり遷移書くのに手間取りました…

G - Suitable Edit for LIS

問題文はこちら

初期状態でのLISを求めてあげると(以降$L$)、LIS構築にどの要素を使う必要があるのかが求まります。あとは、$L_i$として採用可能な一番先頭の要素と$L_{i+1}$として採用可能な一番後ろの要素の間の要素に対して操作をすることでLISが大きくなりそうか判定すれば答えが求まります。

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();
		int[] A = sc.nextInt(N);

  		//普通にLISを求める(構築に使用可能な一番先頭の要素を求めるため)
		int[] list = new int[N];
		int[] indexList = new int[N];
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int i=0;i<N;i++){
			int index = Searcher.upSearch(list,A[i]);
			list[index] = Math.min(list[index],A[i]);
			indexList[i] = index;
		}
		int len = Searcher.upSearch(list,Integer.MAX_VALUE);
		ArrayList<Integer> lastIndex = new ArrayList<>();
		int index = N-1;
		for(int i=len-1;i>=0;i--){
			while(i!=indexList[index])
				index--;
			lastIndex.add(index);
		}

  		//正負を入れ替えて逆順にして再度LIS(構築に使用可能な一番末尾の要素を求めるため)
		ArrayUtil.mapping(A,i->-i);
		ArrayUtil.reverseRange(A,0,N);
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int i=0;i<N;i++){
			index = Searcher.upSearch(list,A[i]);
			list[index] = Math.min(list[index],A[i]);
			indexList[i] = index;
		}
		ArrayList<Integer> firstIndex = new ArrayList<>();
		index = N-1;
		for(int i=len-1;i>=0;i--){
			while(i!=indexList[index])
				index--;
			firstIndex.add(N-index-1);
		}

  		//Aを元に戻す
		ArrayUtil.mapping(A,i->-i);
		ArrayUtil.reverseRange(A,0,N);

  		//高速化のためにint[]に変換
		int[] fi = Converter.toIntArray(firstIndex);
		int[] li = Converter.toIntArray(lastIndex);

  		//末尾の要素が逆順になったまんまなので元に戻す
		ArrayUtil.reverseRange(li,0,len);

  		//現時点でのLISの答え
		int ans = len;

  		//LISを+1できるかどうか調べる
		for(int i=1;i<len;i++){
			if(fi[i-1]+1<li[i]&&A[li[i]]-A[fi[i-1]]>1)
				ans = len+1;
		}

  		//先頭、末尾に適当な値を追加できるか判定
		if(0<li[0])
			ans = len+1;
		if(fi[len-1]+1<N)
			ans = len+1;

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

		out.close();
	}
}

なんとか解けて良かった…。

感想

A,B,C:易しい
D:Dにしては易しい？
E:かなり手こずった…
G:勘が当たって良かった！
って感じでした。

かなり調子が良かったです。いつもこうなら文句無いんですがねぇ…。