はじめに

今回はC、Eはコンテスト後のもの、他はコンテスト中のものを載せようと思います。

では、見ていきましょう。

A - ^{-1}

問題文はこちら

$P_i$に重複はないので普通に先頭から見ていけば良いです。

A.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、Xの受け取り
		int N = System.in.nextInt();
		int X = System.in.nextInt();

		//indexを入れる変数
		int ans = 0;

		//先頭から見ていって、Xである箇所のindexをansに格納
		for(int i=1;i<=N;i++)
			if(System.in.nextInt()==X)
				ans = i;

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

問題は無いですね。

B - Playing Cards Validation

問題文はこちら

switch文を使いました。
一文字ずつ受け取って判定してHashSetに追加していって、sizeが$N$かどうかで重複してないかを判定しました。

B.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//Nの受け取り
		int N = System.in.nextInt();

		//全ての文字列が条件を満たしているか管理するisTrueと重複を調べるset
		boolean isTrue = true;
		HashSet<String> set = new HashSet<String>();

		//一つずつ受け取り
		for(int i=0;i<N;i++){
	
			//受け取った文字を連結する用のStringBuilder
			StringBuilder sb = new StringBuilder();
			char c = System.in.nextChar();

			//一文字目が条件を満たしているか？
			switch(c){
			case 'H':
			case 'D':
			case 'C':
			case 'S':
				break;
			default:
				isTrue = false;
			}
			sb.append(c);
			c = System.in.nextChar();

			//二文字目も条件を満たしているか？
			switch(c){
			case 'A':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
			case 'T':
			case 'J':
			case 'Q':
			case 'K':
				break;
			default:
				isTrue = false;
			}
			sb.append(c);

			//setに加える
			set.add(sb.toString());
		}

		//全部条件を満たしていてかつ重複が無かったらYes、違うならNo
		System.out.println(isTrue&&set.size()==N?"Yes":"No");
 
		System.out.close();
	}
}

配列作ってfor文で条件を満たしているか見た方が良かったかもしれません。

C - Ladder Takahashi

問題文はこちら

keyを何階か、valueをその階から移動できる階を記録したHashSetにしたHashMapで情報を保持し、BFSで解きました。

C.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//Nの受け取り
		int N = System.in.nextInt();

		//各階から行ける箇所を格納するmap
		HashMap<Integer,HashSet<Integer>> list = new HashMap<>();

		//A、Bの受け取り
		while(N-->0){
			int A = System.in.nextInt();
			int B = System.in.nextInt();
			HashSet<Integer> temp = list.remove(A);
			if(temp==null)
				temp = new HashSet<Integer>();
			temp.add(B);
			list.put(A,temp);
			temp = list.remove(B);
			if(temp==null)
				temp = new HashSet<Integer>();
			temp.add(A);
			list.put(B,temp);
		}

		//行ける階を記録するsetと、行けるかbfsで調べる用のdeque
		TreeSet<Integer> floors = new TreeSet<Integer>();
		ArrayDeque<Integer> bfs = new ArrayDeque<Integer>();
		bfs.add(1);
		floors.add(1);
		HashSet<Integer> emptySet = new HashSet<>();

		//bfs
		while(!bfs.isEmpty()){
			Integer now = bfs.pollFirst();
			for(Integer num:list.getOrDefault(now,emptySet)){
				if(!floors.add(num))
					continue;
				bfs.add(num);
			}
		}

		//floorsの最大値を返す
		System.out.println(floors.last());
 
		System.out.close();
	}
}

最初の提出ではDFSで解いたんですが、1994msという疑惑のACをとってしまいました(提出結果)。

D - Takahashi's Solitaire

問題文はこちら

$A$はソートしても答えは変わらないのでソート済みであるとします。
条件を満たすようにカードを出すには$A_{i+1}=A_i \mathrm{or} A_i+1$を満たす連続部分列を左から順に出していけば良いです。ということで$A_i$の前後で差の絶対値が$\mathrm{mod}\ M$で$1$のものを全部足して全要素の和から引けば$A_i$を含むように選んだ時の最小値を求めることができ、それを$A$全体で調べれば良いです(重複して調べないように)。

D.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、M、Aの受け取り(Aはソートする)
		int N = System.in.nextInt();
		int M = System.in.nextInt();
		int[] A = System.in.nextInt(N);
		System.sort(A);

		//Aの総和を求めておく
		long sum = 0;
		for(int num:A)sum += num;

		//過去に調べた箇所か管理する用の配列
		boolean[] isChecked = new boolean[N];

		//答え用変数
		long answer = sum;

		//先頭から調べていく
		for(int i=0;i<N;i++){
			if(isChecked[i])
				continue;
			isChecked[i] = true;

			//テーブルに置いたカードの総和を計算する用
			long ans = A[i];

			//A[i]より小さい方向に調べていく
			int back = (i-1+N)%N;
			int now = A[i];
			while(!isChecked[back]&&((A[back]+1)%M==now||A[back]==now)){
				isChecked[back] = true;
				now = A[back];
				ans += A[back];
				back = (back-1+N)%N;
			}

			//A[i]より大きい方向にも
			int front = (i+1)%N;
			now = A[i];
			while(!isChecked[front]&&(A[front]==(now+1)%M||A[front]==now)){
				isChecked[front] = true;
				now = A[front];
				ans += A[front];
				front = (front+1)%N;
			}

			//最小値を更新した？
			if(answer>sum-ans)
				answer = sum-ans;
		}

		//答えの出力
		System.out.println(answer);
 
		System.out.close();
	}
}

そんなには悩まなかったです。助かりました。

E - Crystal Switches

問題文はこちら

01BFSというものを実装しました(今回初めて)。
$1～N$は$0$の辺が通行できるとき、$N+1～2N$は$1$の辺が通行できるときの頂点$1～N$として、
$cost[i]:$頂点$i$にたどり着ける最小操作数
として保持するようにしました。

E.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、M、Kの受け取り
		int N = System.in.nextInt();
		int M = System.in.nextInt();
		int K = System.in.nextInt();

		//各頂点から移動できる頂点を格納するlist
		ArrayList<ArrayList<Integer>> route = new ArrayList<ArrayList<Integer>>();
		for(int i=0;i<=N*2;i++){
			route.add(new ArrayList<Integer>());
		}

		//各辺を加える(aが0なら1～N、1ならN+1～2Nになるように調整)(別の頂点として保持したいので)
		while(M-->0){
			int u = System.in.nextInt();
			int v = System.in.nextInt();
			int a = System.in.nextInt()*N;
			route.get(u+a).add(v+a);
			route.get(v+a).add(u+a);
		}

		//スイッチがある=頂点sと頂点s+Nは繋がっているとする
		while(K-->0){
			int s = System.in.nextInt();
			route.get(s).add(s+N);
			route.get(s+N).add(s);
		}

		//bfs用deque
		ArrayDeque<Integer> bfs = new ArrayDeque<Integer>();
		//最初は1の辺を通れるのでN+1が初期値
		bfs.add(N+1);

		//移動にかかる最小コストを記録する配列
		int[] cost = new int[2*N+1];
		int max = (int)1e9;
		Arrays.fill(cost,max);
		cost[N+1] = 0;

		//01bfs
		while(!bfs.isEmpty()){
			int now = bfs.pollFirst();
			for(int next:route.get(now)){
				if(next%N==now%N&&cost[now]<cost[next]){
					bfs.addFirst(next); //スイッチ切り替え時はdequeの先頭に
					cost[next] = cost[now];
				}else if(cost[next]>cost[now]+1){
					bfs.addLast(next); //辺を通っての移動はdequeの末尾に
					cost[next] = cost[now]+1;
				}
			}
		}

		//スイッチの状態にかかわらず最小コストの方が答え
		int ans = Math.min(cost[N],cost[2*N]);

		//到達できない=最小コストが初期値のままなのでそのときは-1を、それ以外はansを出力
		System.out.println(ans==max?-1:ans);
 
		System.out.close();
	}
}

本番中はスイッチを切り替えるときもaddLast(next)してしまっていたのでafter_contestでTLEが出てました。運が味方してくれて良かったです･･･。

感想

A:易しい
B:場合分けがちょっとめんどくさい
C、D:発想自体はそんなに難しくはなかった
E:テストケースに救われた
って感じでした。

今回のはEとFに崖があったのでEまでをもっと早く解ければパフォーマンスが上がったかもしれません。
まぁ、そんな実力は無いんですが･･･。