はじめに
今回はコンテスト中にEまで解けたのでそれを載せようと思います。
では、見ていきましょう。
A - Candy Button
問題文はこちら
前回飴をもらったタイミングを保持してC以上時間が経過しているかシミュレーションしながら判定して数え上げました。
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){
int N = sc.nextInt();
int C = sc.nextInt();
int bef = -C;
int ans = 0;
while(N-->0){
int T = sc.nextInt();
if(T-bef>=C){
bef = T;
ans++;
}
}
out.println(ans);
out.close();
}
}
B - Hands on Ring (Easy)
問題文はこちら
右回りと左回りの2通りを考えれば良く、手がぶつからない方向に移動していくシミュレーションで解きました。
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){
int N = sc.nextInt();
int Q = sc.nextInt();
int L = 1;
int R = 2;
int ans = 0;
while(Q-->0){
char H = sc.nextChar();
int T = sc.nextInt();
if(H=='R'){
if(MathFunction.rangeCheck(L,Math.min(R,T),Math.max(R,T)))
ans += N-Math.abs(R-T);
else
ans += Math.abs(R-T);
R = T;
}
else{
if(MathFunction.rangeCheck(R,Math.min(L,T),Math.max(L,T)))
ans += N-Math.abs(L-T);
else
ans += Math.abs(L-T);
L = T;
}
}
out.println(ans);
out.close();
}
}
C - Prepare Another Box
問題文はこちら
$A_i$が大きい方から貪欲にしまうのが最適で、現時点で未使用な、大きさが$A_i$以上の箱を格納したPriorityQueue(min-heap)で管理することで本問題を解くことができます。
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){
int N = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(N-1);
Arrays.sort(A);
Arrays.sort(B);
PriorityQueue<Integer> boxes = new PriorityQueue<>();
int x = 0;
int index = N-2;
for(int i=N-1;i>=0;i--){
while(0<=index&&A[i]<=B[index])
boxes.add(B[index--]);
if(boxes.size()==0){
if(x==0)
x = A[i];
else{
System.out.println(-1);
return;
}
}
else
boxes.poll();
}
out.println(x);
out.close();
}
}
D - Cycle
問題文はこちら
愚直に閉路を探そうとしてはとても間に合わないので、頂点$1$から出発して頂点$1$に戻ることを利用します。
頂点$1$から各頂点への最短距離と有向辺を逆にしての頂点$1$から各頂点への最短距離さえ求まっていれば、頂点$1$から頂点$i(1<i)$を経由して頂点$1$へ戻る最短距離が求まります。これが各頂点を経由する閉路の最小の辺数になります。
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){
int N = sc.nextInt();
int M = sc.nextInt();
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
ArrayList<ArrayList<Integer>> rList = new ArrayList<>();
for(int i=0;i<=N;i++){
list.add(new ArrayList<>());
rList.add(new ArrayList<>());
}
while(M-->0){
int a = sc.nextInt();
int b = sc.nextInt();
list.get(a).add(b);
rList.get(b).add(a);
}
int max = Integer.MAX_VALUE>>1;
int[] dist = new int[N+1];
Arrays.fill(dist,max);
dist[1] = 0;
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(1);
while(deq.size()>0){
int now = deq.pollFirst();
for(int next:list.get(now)){
if(dist[next]==max){
dist[next] = dist[now]+1;
deq.add(next);
}
}
}
int[] rDist = new int[N+1];
Arrays.fill(rDist,max);
rDist[1] = 0;
deq.add(1);
while(deq.size()>0){
int now = deq.pollFirst();
for(int next:rList.get(now)){
if(rDist[next]==max){
rDist[next] = rDist[now]+1;
deq.add(next);
}
}
}
int ans = max;
for(int i=2;i<=N;i++)
ans = Math.min(ans,dist[i]+rDist[i]);
out.println(ans==max?-1:ans);
out.close();
}
}
E - Max × Sum
問題文はこちら
式がいかつくて、そのままを考えるのは気が滅入りそうなので$\max_{i \in S} A_i$を固定することを考えます。
もし$\max A_i$が決まっているならば、最適な$\sum_{j}B_j$は$A_j$が$\max A_i$以下である$j$について$B_j$が小さいものに貪欲に選んでいくことで求まります。
したがって、$A$を昇順に並べ、$A$に対応する$B$をPriorityQueue(max-heap)に入れ、$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){
int T = sc.nextInt();
while(T-->0){
int N = sc.nextInt();
int K = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(N);
int[] subA = A.clone();
Arrays.sort(subA);
PriorityQueue<int[]> queue1 = new PriorityQueue<>((a,b)->Integer.compare(a[0],b[0]));
PriorityQueue<Integer> queue2 = new PriorityQueue<>(Comparator.reverseOrder());
for(int i=0;i<N;i++)
queue1.add(new int[]{A[i],B[i]});
long ans = Long.MAX_VALUE;
long sum = 0;
for(int i=0;i<N;i++){
while(queue1.size()>0&&queue1.peek()[0]<=subA[i]){
int[] sub = queue1.poll();
sum += sub[1];
queue2.add(sub[1]);
}
while(queue2.size()>K)
sum -= queue2.poll();
if(queue2.size()==K)
ans = Math.min(ans,sum*subA[i]);
}
out.println(ans);
}
out.close();
}
}
感想
A,B:易しい
C,D,E:典型感が強め？
って感じでした。
いや～、速度が出せなかったが故の敗北…無念…。