はじめに
今回は参加できなかったのでコンテスト後に解いたものを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください(ちなみにE、Fはライブラリを使用していません)。
では、見ていきましょう。
A - 321-like Checker
問題文はこちら
下一桁を見て条件を満たしていれば$10$で割るのを繰り返すことで全体が条件を満たしているか調べました。
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 ) {
//Nの受け取り
int N = sc.nextInt();
//直前に見た数字(便宜上初期値は-1)
int bef = -1;
//見終わるまで見る
while(N>0){
//条件を満たしていないならNoを出力して即終了
if(N%10<=bef){
System.out.println("No");
return;
}
//befを更新して、Nを10で割る
bef = N%10;
N /= 10;
}
//見終わった=条件を満たしているのでYes
out.println("Yes");
out.close();
}
}
普通に文字列で受け取って処理しても良かったかもしれません。
B - Cutoff
問題文はこちら
$N$ラウンド目が最小値となるとき、$1～N-1$ラウンドの最小値が全体の最小値となるとき、$N$ラウンド目が全体の最大値となるときを考えて答えを求めました。
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 ) {
//N、X、Aの受け取り
int N = sc.nextInt();
int X = sc.nextInt();
int[] A = sc.nextInt(N-1);
//ソートして総和から最大値を引いておく
Arrays.sort(A);
int sum = (int)MathFunction.sum(A)-A[N-2]; //Nラウンド目が最小値のときの成績
//Nラウンド目が全体の最小値のときに単位が貰えるなら答えは0
if(X<=sum)
out.println(0);
//Nラウンド目が最大値になったときに単位が貰えないならどう頑張っても無理なので-1
else if(sum+A[N-2]-A[0]<X)
out.println(-1);
//上記を満たしていないなら頑張れば単位が貰えるのでその最小値を求める
else
out.println(X-sum+A[0]);
out.close();
}
}
思ったよりサクッと解けました。
C - 321-like Searcher
問題文はこちら
最初にTreeSetを使って全列挙しておいて目的の値を取り出す方針で解きました。
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 ) {
//全列挙
TreeSet<Long> set = new TreeSet<>();
for(long i=9;i>=0;i--){
TreeSet<Long> next = new TreeSet<>();
for(Long num:set){
//これまで出現してきた数字の末尾につければ降順に数字が並んでいることが保証される
next.add(Long.parseLong(num+""+i));
next.add(num);
}
next.add(i);
set = next;
}
//Kの受け取り
int K = sc.nextInt();
//0が余計に含まれているので、それも考慮してK個取り出す
while(K-->0)
set.pollFirst();
//K番目に該当する数字を出力する
out.println(set.pollFirst());
out.close();
}
}
これもサクッと解けました。
D - Set Menu
問題文はこちら
$B$をソートしておいて、選ぶ$A_i$を決め打ったときの$s$が$P$を超えない最大の$B_i$を二分探索で求め、累積和を用いて$A_i$を選んだ時の総額を求めました。
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、M、P、A、Bの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int P = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(M);
//Bのソート
Arrays.sort(B);
//累積和の構築
long[] sumB = new long[M+1];
for(int i=0;i<M;i++)
sumB[i+1] = sumB[i]+B[i];
//総和を求める
long sum = 0;
for(int i=0;i<N;i++){
//A_i+B_jがPを超える最小のjを求める
int index = Searcher.overSearch(B,P-A[i]);
//1～j-1まではmin(s,P)=sなのでそれを求め、以降はmin(s,P)=Pなので(M-j)*Pが総和となる
sum += sumB[index]+(long)index*A[i] + (long)(M-index)*P;
}
out.println(sum);
out.close();
}
}
Dにしては割と易しめに感じました。
E - Complete Binary Tree
問題文はこちら
公式解説の通りです。
E.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Tの受け取り
int T = sc.nextInt();
while(T-->0){
//N、X、Kの受け取り
long N = sc.nextLong();
long X = sc.nextLong();
long K = sc.nextLong();
//自分自身の左右に繋がっている頂点で距離がKである頂点の総和を求める
long ans = K>0?findRight(N,X,K)+findLeft(N,X,K):1;
long bef = X; //親に向かって遡るときに左右どっちから来たかわかるように保持しておく
X >>= 1; //見ている頂点を1つだけ頂点1側に移動する
while(X>0&&--K>=0){
//まだ見ていない方の頂点の方にある条件を満たす頂点の数を加算
ans += (bef&1)==0?findRight(N,X,K):findLeft(N,X,K);
//遷移
bef = X;
X >>= 1;
}
//答えの出力
System.out.println(ans);
}
}
//頂点parの左側の頂点と結合していて距離がdistの頂点の総和を求めるメソッド
private static long findLeft(long N,long par,long dist){
if(N/Math.pow(2,dist)<par)
return 0;
long low = par<<dist;
long high = (low|((1L<<dist)-1))+low>>1;
return Math.max(0,Math.min(high,N)-low+1);
}
//頂点parの右側の頂点と結合していて距離がdistの頂点の総和を求めるメソッド
private static long findRight(long N,long par,long dist){
if(N/Math.pow(2,dist)<par)
return 0;
long low = 2*par+1<<dist-1;
long high = low|((1L<<dist)-1);
return Math.max(0,Math.min(high,N)-low+1);
}
}
入出力高速化をしていないので1000msかかってますが、十分高速ですね。
F - #(subset sum = K) with Add and Erase
問題文はこちら
公式解説の方の解き方で解きました。
F.java
import java.util.Scanner;
class Main{
//あまり求める用
private static final int MOD = 998244353;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Q、Kの受け取り
int Q = sc.nextInt();
int K = sc.nextInt();
//DPテーブル
int[] dp = new int[K+1];
dp[0] = 1; //初期値
while(Q-->0){
//+-と数字の受け取り
char c = sc.next().charAt(0);
int x = sc.nextInt();
//遷移
if(c=='+')
for(int i=K;i>=x;i--)
dp[i] = (dp[i]+dp[i-x])%MOD;
else
for(int i=x;i<=K;i++)
dp[i] = (dp[i]-dp[i-x]+MOD)%MOD;
//現状での組み合わせの数をこたえｒ
System.out.println(dp[K]);
}
}
}
最初全然思いつかなくて解説見てしまいましたが、これは解けるようになりたい…。
感想
A,B,C,D:易しい
E:範囲として扱えば上手くいけそうな気はしたけど実装方法が全然思いつかなかった…。
F:どのようにすれば削除ができるようになるかを遷移で考えようとできなかったことが敗因…無念…
って感じでした。
普通に出てたらめちゃくちゃレート下がってそう…。コロナで精進できていないとはいえ、ここまで解けなくなっているとは…。早く治したい…！