はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解いたのでそれを載せようと思います。
では、見ていきましょう。
なお、ライブラリの内容は提出結果よりご確認ください。
A - First Player
問題文はこちら
最年少をforで探してそこから$N$行出力しました。
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 ) {
//N、S、Aの受け取り
int N = sc.nextInt();
String[] S = new String[N];
int[] A = new int[N];
for(int i=0;i<N;i++){
S[i] = sc.next();
A[i] = sc.nextInt();
}
//最年少のindexを探す
int index = -1;
int min = Integer.MAX_VALUE;
for(int i=0;i<N;i++){
if(min>A[i]){
min = A[i];
index = i;
}
}
//最年少から時計回りに
for(int i=0;i<N;i++)
out.println(S[(i+index)%N]);
out.close();
}
}
特に難しくはないですね。
B - Subscribers
問題文はこちら
$N$の桁数を$K$とすると、$\lfloor \frac{N}{\mathrm{max}(1,10^{K-3})} \rfloor \times \mathrm{max}(1,10^{K-3})$が答えです。
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の受け取り
int N = sc.nextInt();
//上記の式の計算
out.println(N/MathFunction.pow(10,String.valueOf(N).length()-3)*MathFunction.pow(10,String.valueOf(N).length()-3));
out.close();
}
}
$K$を入れる変数作ればもうちょっと見やすかったかな…。
C - Virus
問題文はこちら
BFSで解きました。
$N$が小さいので、感染している人と距離が$D$以下の人を$O(N)$で求めても十分高速です。
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、D、座標の受け取り
int N = sc.nextInt();
int D = sc.nextInt();
Point[] p = sc.nextPoint(N);
//BFS
ArrayDeque<Integer> deq = new ArrayDeque<>();
boolean[] isBad = new boolean[N];
deq.add(0);
isBad[0] = true;
while(deq.size()>0){
int now = deq.pollFirst();
for(int i=0;i<N;i++){
if(i==now||(p[i].x-p[now].x)*(p[i].x-p[now].x)+(p[i].y-p[now].y)*(p[i].y-p[now].y)>D*D)
continue;
if(!isBad[i]){
isBad[i] = true;
deq.add(i);
}
}
}
//感染してるか否かを出力
for(boolean bool:isBad)
out.println(bool?"Yes":"No");
out.close();
}
}
UnionFindを使った解法もあるそうですね。計算量の話がユーザー解説にあるのでそれと合わせて読むと良いかも？
D - A Piece of Cake
問題文はこちら
上から何番目で左から何番目かをキーとしたHashMapで個数を数えて最大最小を探しました。
Mapのsizeが$(A+1)(B+1)$未満の時は最小値が0になることに注意しましょう。
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 ) {
//W、H、N、座標の受け取り
int W = sc.nextInt();
int H = sc.nextInt();
int N = sc.nextInt();
Point[] p = sc.nextPoint(N);
//A、aの受け取り
int A = sc.nextInt();
int[] a = sc.nextInt(A);
//B、bの受け取り
int B = sc.nextInt();
int[] b = sc.nextInt(B);
//各イチゴがどこの区画に属するか記録
HashMap<Point,Integer> map = new HashMap<>();
for(Point point:p){
int indexA = Searcher.downSearch(a,point.x);
int indexB = Searcher.downSearch(b,point.y);
map.merge(new Point(indexA,indexB),1,Integer::sum);
}
//各区画の最大最小値を探す
int min = Integer.MAX_VALUE;
int max = 0;
for(int sum:map.values()){
min = Math.min(min,sum);
max = Math.max(max,sum);
}
//もし何も無い区画があれば最小値は0
if(map.size()<(long)(A+1)*(B+1))
min = 0;
//答えの出力
out.println(min+" "+max);
out.close();
}
}
最初(A+1)*(B+1)をA*Bと書いてしまって1ペナです…悔しい…。
E - Good Graph
問題文はこちら
UnionFindを使って解きました。
先にグラフ$G$を構築し、$(\mathrm{root}(x_i),\mathrm{root}(y_i))$をHashSetに記録して、$(\mathrm{root}(p_i),\mathrm{root}(q_i))$がSetに含まれているかで判定しました。
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の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//Gの構築
UnionFind uf = new UnionFind(N+1);
while(M-->0){
int u = sc.nextInt();
int v = sc.nextInt();
uf.unite(u,v);
}
//各組み合わせをsetに記録
int K = sc.nextInt();
HashSet<Point> set = new HashSet<>();
while(K-->0){
int x = uf.root(sc.nextInt());
int y = uf.root(sc.nextInt());
//入れ替えた組み合わせも記録しておく
set.add(new Point(x,y));
set.add(new Point(y,x));
}
//各クエリに対して答える
int Q = sc.nextInt();
while(Q-->0){
int p = uf.root(sc.nextInt());
int q = uf.root(sc.nextInt());
//setに含まれていたらダメな組み合わせ
out.println(set.contains(new Point(p,q))?"No":"Yes");
}
out.close();
}
}
これは比較的早く気づけました。
F - Shift Table
問題文はこちら
公式解説の通りです。
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 ) {
//N、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
final int mod = 998244353;
//約数の記録
TreeSet<Integer> set = new TreeSet<>();
set.add(1);
for(int i=2;i*i<=N;i++){
if(N%i==0){
set.add(i);
set.add(N/i);
}
}
//数え上げ用
long ans = 0;
//重複削除用map
HashMap<Integer,Long> map = new HashMap<>();
//約数を小さい方から
for(int num:set){
//必ず働く必要のある日を記録
boolean[] mustWork = new boolean[num];
for(int i=0;i<N;i++)
mustWork[i%num] |= S.charAt(i)=='.';
//働かなくて良い日を数え上げ
int count = 0;
for(boolean flag:mustWork)
if(!flag)
count++;
//重複を引いた総数
long sum = MathFunction.modPow(2,count,mod)-map.getOrDefault(num,0L);
//重複して数えてしまう候補をmapに記録
for(int i=num;i<N;i+=num)
map.merge(i,sum,(a,b)->(a+b)%mod);
//答えを記録
ans += sum;
ans %= mod;
}
//重複を引く時に負数になる可能性があるので調製して出力
out.println((mod+ans)%mod);
out.close();
}
}
最後あたりに気づきはしましたが、実装が間に合わなかった上にバグらせたので完敗です…。
感想
A:易しい
B:ちょっとウッってなった
C:BFSがCで出るようになったんだな～とか思った(過去にもあったような気がするけど)
D:最初解法が見えなくて焦った
E:UnionFindで解く問題はもう慣れてきたかも？
F:難しい…
って感じでした。
unratedになってしまったのは悲しいですが、次回以降への勉強になったのでヨシ！