はじめに
今回はコンテスト中に書いた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は解けないといけないですね…。