はじめに
今回はFまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - ab
問題文はこちら
普通にabかbaが存在するか判定しました。
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、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//abかbaがあるか判定
out.println(S.contains("ab")||S.contains("ba")?"Yes":"No");
out.close();
}
}
B - A^A
問題文はこちら
誤差がどれくらい出るか検証してないですけど、制約下においてはMath.pow(A,A)が$B$未満な間$A$を$1$ずつ増やしていくだけで答えが求まります。
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 ) {
//Bの受け取り
long B = sc.nextLong();
//Aを探索
long A = 1;
while(Math.pow(A,A)<B)
A++;
//Bが条件を満たしているか？
out.println(MathFunction.pow(A,A)==B?A:-1);
out.close();
}
}
誤差でWAが出なくて助かりました()。
C - Number Place
問題文はこちら
問題文の通りに実装しました。
数字があるかないかはHashSetを使いました。
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 ) {
//Aの受け取り
int[][] A = sc.nextInt(9,9);
//全部の条件の論理積を取る用
boolean flag = true;
//横方向
for(int i=0;i<9;i++){
HashSet<Integer> set = new HashSet<>();
for(int j=0;j<9;j++)
set.add(A[i][j]);
flag &= set.size()==9;
}
//縦方向
for(int i=0;i<9;i++){
HashSet<Integer> set = new HashSet<>();
for(int j=0;j<9;j++)
set.add(A[j][i]);
flag &= set.size()==9;
}
//各小ブロック
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
HashSet<Integer> set = new HashSet<>();
for(int k=0;k<3;k++){
for(int l=0;l<3;l++){
set.add(A[i*3+k][j*3+l]);
}
}
flag &= set.size()==9;
}
}
//全条件を満たしていたか？
out.println(flag?"Yes":"No");
out.close();
}
}
D - Good Tuple Problem
問題文はこちら
とりあえず1つ頂点を0とし、そこから行ける頂点を自分と異なるように割り当てながらBFSをすることで解きました。
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、A、Bの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(M);
int[] B = sc.nextInt(M);
//隣接リストの構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0){
list.get(A[M]).add(B[M]);
list.get(B[M]).add(A[M]);
}
//各頂点の番号を記録する用
int[] num = new int[N+1];
Arrays.fill(num,-1);
//全連結成分を探索
for(int i=1;i<=N;i++){
if(num[i]>=0)
continue; //探索済みならスルー
//未探索なら、頂点iを含む連結成分について調べる
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(i);
num[i] = 0;
while(deq.size()>0){
int now = deq.pollFirst();
for(int next:list.get(now)){
if(num[next]>=0){
if(num[now]==num[next]){
System.out.println("No"); //もし条件を満たさない割り当て方があればNo
return;
}
}
else{
num[next] = num[now]^1;
deq.add(next);
}
}
}
}
//上記のループを抜けたら全部割り当てられたのでYes
out.println("Yes");
out.close();
}
}
最初楽をしようとUnionFindでテキトーに閉路だけ検出して判定するようにしたら見事にWAが出ました。
ちゃんと、考えてから提出しようね。
E - Maximize Rating
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i]$を$i$回参加したときの$\sum_{k=1}^{i}{(0.9)^{i-k}Q_k}$の最大値として解きました(遷移は実装例を見て下さい)。
E.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、Pの受け取り
int N = sc.nextInt();
int[] P = sc.nextInt(N);
//DP
double[] max = new double[N+1];
for(int i=0;i<N;i++){
for(int j=i+1;j>=1;j--){
double num = max[j-1]*0.9+P[i];
max[j] = Math.max(max[j],num);
}
}
//レート計算をして最大値を求める
double ans = -1200;
for(int i=1;i<=N;i++)
ans = Math.max(ans,max[i]/(10*(1-Math.pow(0.9,i)))-1200/Math.sqrt(i));
//最大値の出力
out.println(ans);
out.close();
}
}
初期値とかいろいろミスってしまって、巡り回って以下のような実装に落ち着きました。
F - Apples
問題文はこちら
遅延セグメント木で解きました。
僕のライブラリには無いのでAtCoderLibraryForJavaのものを拝借して解きました。
この場をお借りして御礼申し上げます。
F.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 );
//遅延セグ木用
static class S{
public int sum;
public S(int s){
sum = s;
}
public static S op(S a,S b){
return new S(Math.max(a.sum,b.sum));
}
}
static class F{
int num;
public F(int n){
num = n;
}
public static S op(F a,S b){
return new S(a.num+b.sum);
}
public static F composite(F a,F b){
return new F(a.num+b.num);
}
}
public static void main ( String[] args ) {
//N、D、Wの受け取り
int N = sc.nextInt();
int D = sc.nextInt();
int W = sc.nextInt();
//落下する時刻が早い順に並べておく
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Integer.compare(a[0],b[0]));
while(N-->0){
int T = sc.nextInt();
int X = sc.nextInt();
queue.add(new int[]{T,X});
}
//遅延セグ木
LazySegTree<S,F> lSegT = new LazySegTree<S,F>(400_001,S::op,new S(0),F::op,F::composite,new F(0));
//最大値記録用
int ans = 0;
//削除対象
PriorityQueue<int[]> dQueue = new PriorityQueue<>((a,b)->Integer.compare(a[0],b[0]));
//順に見ていく
while(queue.size()>0){
//新しく落下してくるりんごを元に増減させる
int[] apple = queue.poll();
dQueue.add(apple);
lSegT.apply(apple[1],apple[1]+W,new F(1));
int limit = apple[0]-D;
while(dQueue.size()>0&&dQueue.peek()[0]<=limit){
int[] dApple = dQueue.poll();
lSegT.apply(dApple[1],dApple[1]+W,new F(-1));
}
//最大値で更新
ans = Math.max(ans,lSegT.allProd().sum);
}
//答えの出力
out.println(ans);
out.close();
}
}
イマイチ使い方を理解してないのでなんかおかしいところがあったらすみません…。
感想
A,B:易しい
C:ちょっと重めだけどこれくらいは気合いで
D:詰めが甘い実装をしてしまって反省…
E:DPってすぐ気づけた。易しめ？
F:遅延セグ木だとはすぐ気づいたが読解に時間がかかってしまった…
って感じでした。
終了5分前くらいに通ったので良かったですが、もし通らなかったらレートかなり下がってたかも…。怖…。