はじめに

今回はコンテスト中に書いたA、B、D、Fとコンテスト後に書いたC、Eを載せようと思います。

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

なお、ライブラリを見たい方はこちら(提出結果)からどうぞ。

A - CAPS LOCK

問題文はこちら

StringにはtoUpperCaseメソッドがあるのでそれを使いましょう。

A.java

final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//Sを受け取ってtoUpperCase
		out.println(sc.next().toUpperCase());
 
		out.close();
	}
}

特に悩まなかったです。

B - Yellow and Red Card

問題文はこちら

人数分の配列を準備しておいて、イエローカードを提示されたら+$1$、レッドカードを提示されたら+$2$して、退場処分を受けたかは値が$2$以上かで判定するようにしました。

B.java

final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、Qの受け取り
		int N = sc.nextInt();
		int Q = sc.nextInt();

		//イエローカード、レッドカードの提示を得点として記録する用の配列
		int[] point = new int[N+1];
		while(Q-->0){

			//t、xの受け取り
			int t = sc.nextInt();
			int x = sc.nextInt();

			//2以上か判定
			if(t==3)
				out.println(point[x]>=2?"Yes":"No");

			//得点の加算
			else
				point[x] += t;
		}
 
		out.close();
	}
}

これも特には悩まずに解くことができました。

C - Four Variables

問題文はこちら

事前に$AB$としてあり得る値を全探索して配列に各値に対する$AB$の種類を数え上げることで、$AB$、$CD$の値から$(A,B,C,D)$の組み合わせの総数を$O(1)$で求められると思い、それを実装しました。

C.java

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

		//count[i]:AB=iとなるABの種類
		int[] count = new int[N+1];

		//探索
		for(int i=1;i<N;i++)
			for(int j=1;j*i<=N;j++)
				count[i*j]++;

		//数え上げ
		int ans = 0;
		for(int i=1;i<N;i++)
			ans += count[i]*count[N-i];

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

コンテスト後に他の人の提出を見ていてこれが一番わかりやすいなと思ってこれを載せました。

D - Unicyclic Components

問題文はこちら

UnionFindをベースに、辺の数を配列で数え上げながら解きました。

D.java

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

		//辺の合計
		int[] sum = new int[N];

		//UnionFind
		UnionFind uf = new UnionFind(N);

		while(M-->0){

			//u、vの受け取り
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;

			//今の根を記録
			int rootU = uf.root(u);
			int rootV = uf.root(v);

			//連結
			uf.unite(u,v);

			//根に辺の合計を記録(すでに連結済みなら+1するだけ、新しく連結したなら元の根同士の合計を)
			sum[uf.root(u)] = rootU!=rootV?sum[rootU]+sum[rootV]+1:sum[uf.root(u)]+1;
		}

		//頂点の合計と辺の合計が合致しているか
		boolean isTrue = true;
		for(int i=0;i<N;i++){
			isTrue &= sum[uf.root(i)]==uf.size(i);
		}

		//結果に応じて出力
		out.println(isTrue?"Yes":"No");
 
		out.close();
	}
}

Twitterで見かけたのですが、逐一数え上げるのではなく、一度UnionFindで連結してから根に加算するという方法の方が理解しやすかったかもしれません。

D改.java

final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、M、辺の受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] path = sc.nextInt(M,2);

		//UnionFind
		UnionFind uf = new UnionFind(N);

		//辺の情報を基に連結
		for(int[] pair:path)
			uf.unite(pair[0]-1,pair[1]-1);

		//根に辺の個数を加算
		int[] sum = new int[N];
		for(int[] pair:path)
			sum[uf.root(pair[0]-1)]++;

		//頂点の合計と辺の合計が合致しているか
		boolean isTrue = true;
		for(int i=0;i<N;i++){
			isTrue &= sum[uf.root(i)]==uf.size(i);
		}

		//結果に応じた出力を
		out.println(isTrue?"Yes":"No");
 
		out.close();
	}
}

とはいえ、これもそこまで難しくは感じなかったです。

E - Transitivity

問題文はこちら

公式解説と同じ方針です。
BFSを用いて「各頂点から到達可能な頂点-各頂点から直接到達可能な頂点」の総和を求めました。

E.java

final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、M、辺から作った連結リスト(1-indexed)の受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] list = sc.nextGraph(N,M,true);

		//答えを数える用の変数
		long ans = 0;

		//各頂点を始点に
		for(int i=1;i<=N;i++){

			//到達済みかを管理する配列
			boolean[] isVisited = new boolean[N+1];

			//到達出来る頂点の数を管理する変数
			int count = 0;

			//初期状態設定
			isVisited[i] = true;

			//bfs用Deque
			ArrayDeque<Integer> deq = new ArrayDeque<>();

			//始点追加
			deq.add(i);

			//BFS
			while(!deq.isEmpty()){
				int now = deq.pollFirst();
				for(int next:list[now]){
					if(isVisited[next])
						continue;
					isVisited[next] = true;
					deq.add(next);
					count++; //到達可能と判定したら+1しておく
				}
			}

			//「間接的に到達可能-直接到達可能」をansに加算
			ans += count-list[i].length;
		}

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

うーん…コンテスト中に思いつけませんでした…。

F - Regular Triangle Inside a Rectangle

問題文はこちら

三分探索で解きました。
証明は公式解説に任せますが、正三角形の一つの頂点は長方形のどこかの頂点と仮定して良く、正三角形と長方形の辺が成す角の角度を三分探索しました。

F.java

final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//A、Bの受け取り
		int A = sc.nextInt();
		int B = sc.nextInt();

		//上下限値の設定
		double a = 0.0;
		double b = Math.PI/6.0; //radでの30°

		//良い具合の精度になるまで繰り返す
		while(b-a>=1e-14){
			double c1 = (a*2+b)/3;
			double c2 = (a+b*2)/3;
			if(function(A,B,c1)>function(A,B,c2))
				b = c2;
			else
				a = c1;
		}

		//答えの出力
		out.println(function(A,B,(a+b)/2.0));
 
		out.close();
	}

	//指定された角度での辺の長さを求めるメソッド
	private static double function(int A,int B,double s){
		return Math.min(A/Math.cos(s),B/Math.cos(Math.PI/6.0-s));
	}
}

1e-14ですが、1e-9程度で十分そうです。1e-15までは確認しましたが、それより小さくすると結果が返ってこない場合があると思いますので、まぁその辺はうまい具合に調整する必要がありそうです。
ちなみに時間を計って打ち切る解法も通りました(1.5秒で打ち切る)。

F改.java

final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//実行開始時刻の記録
		long time = System.nanoTime();
 
		//A、Bの受け取り
		int A = sc.nextInt();
		int B = sc.nextInt();

		//初期値設定
		double a = 0.0;
		double b = Math.PI/6.0;

		//1.5秒に達するまで三分探索
		while((System.nanoTime()-time)/1e9<1.5){
			double c1 = (a*2+b)/3;
			double c2 = (a+b*2)/3;
			if(function(A,B,c1)>function(A,B,c2))
				b = c2;
			else
				a = c1;
		}

		//答えの出力
		out.println(function(A,B,(a+b)/2.0));
 
		out.close();
	}

	//指定された角度での辺の長さを求めるメソッド
	private static double function(int A,int B,double s){
		return Math.min(A/Math.cos(s),B/Math.cos(Math.PI/6.0-s));
	}
}

コンテスト中に思いついて良かったです。

感想

A,B:易しい
C:めちゃくちゃ悩んでしまった…
D:Cより易しく感じた
E:全然気づけなかった…実験するべきだったかも…
F:一点を長方形の頂点と共有して良いと気づいてからはサクッと解けた
って感じでした。

5完でしたが、レートは微増って感じでした。やはり水を維持するには水diffは解けないといけないですね…。