はじめに
今回はコンテスト中に全完できたのでそのときのコードをそのまま載せようと思います。
なお、僕のライブラリはGitHubよりご確認ください。
では、見ていきましょう。
A - Cut
問題文はこちら
答え用の配列に$K$個分ずらして格納することで解を構築しました。
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 K = sc.nextInt();
int[] A = sc.nextInt(N);
int[] ans = new int[N];
for(int i=0;i<N;i++)
ans[(i+K)%N] = A[i];
out.println(ans);
out.close();
}
}
B - Decrease 2 max elements
問題文はこちら
制約がそんなに大きくないので愚直にシミュレーションして解を求めました。
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[] A = sc.nextInt(N);
Arrays.sort(A);
int ans = 0;
while(A[N-2]>0){
A[N-1]--;
A[N-2]--;
ans++;
Arrays.sort(A);
}
out.println(ans);
out.close();
}
}
C - Triple Attack
問題文はこちら
$1$、$1$、$3$の繰り返しになっているので$3$の倍数に合わせてから$5$で割った商$\times 3$を答えに、あまりの部分は愚直に求めることで解を求めました。
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();
long ans = 0;
while(N-->0){
int H = sc.nextInt();
while(ans%3>0&&H>0){
ans++;
H -= ans%3==0?3:1;
}
int sub = H/5;
ans += sub*3;
H %= 5;
while(H>0){
ans++;
H -= ans%3==0?3:1;
}
}
out.println(ans);
out.close();
}
}
今思えば$3$の倍数に揃える必要は無かったですね。
D - Minimum Steiner Tree
問題文はこちら
$V_1$から再帰的に辿っていき、自身が$V$に含まれているか、自分を経由して$V$に含まれている頂点にたどり着くならその分の辺を保持、それ以外は辺を削除することで解を求めることができます。
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 K = sc.nextInt();
int[][] graph = sc.nextGraph(N,N-1);
int[] V = sc.nextInt(K);
HashSet<Integer> set = new HashSet<>();
for(int v:V)
set.add(v);
out.println(dfs(V[0],0,graph,set));
out.close();
}
private static int dfs(int now,int bef,int[][] graph,HashSet<Integer> V){
int ans = 0;
for(int next:graph[now]){
if(next==bef)
continue;
ans += dfs(next,now,graph,V);
}
if(ans>0)
return ans+1;
return V.contains(now)?1:0;
}
}
E - Train Delay
問題文はこちら
$X$を求めながらダイクストラ法を適用することで最適な$X$を求めることができます。
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 N = sc.nextInt();
int M = sc.nextInt();
long[] X = new long[M];
X[0] = sc.nextInt();
int[][] trains = new int[M][5];
for(int i=0;i<M;i++){
for(int j=0;j<4;j++)
trains[i][j] = sc.nextInt();
trains[i][4] = i;
}
Arrays.sort(trains,(a,b)->Integer.compare(a[2],b[2]));
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Integer.compare(a[3],b[3]));
long[] time = new long[N+1];
for(int[] train:trains){
int A = train[0];
int B = train[1];
int S = train[2];
int T = train[3];
int index = train[4];
queue.add(train);
while(queue.size()>0&&queue.peek()[3]<=S){
int[] subTrain = queue.poll();
time[subTrain[1]] = Math.max(time[subTrain[1]],subTrain[3]+X[subTrain[4]]);
}
if(X[index]==0)
X[index] = Math.max(0,time[A]-S);
}
for(int i=1;i<M-1;i++)
out.print(X[i]+" ");
out.println(X[M-1]);
out.close();
}
}
F - Dividing Game
問題文はこちら
$A_i$の約数$x$を選んで割るという行為は$A_i$の素因数をいくつか選んで取り除くことに等しいので、これはNimゲームに帰着でき、$A_i$のgrundy数を求めてxor和を取ることで先手必勝か後手必勝かを判定することができます。
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);
public static void main(String[] args){
int N = sc.nextInt();
int[] A = sc.nextInt(N);
int[] grundy = new int[100_001];
for(int i=2;i<=100_000;i++){
int num = i;
for(int j=2;j*j<=i;j++){
while(num%j==0){
num /= j;
grundy[i]++;
}
}
if(num>1)
grundy[i]++;
}
int xorSum = 0;;
for(int a:A)
xorSum ^= grundy[a];
out.println(xorSum>0?"Anna":"Bruno");
out.close();
}
}
G - Add and Multiply Queries
問題文はこちら
制約上、$A_i$より$B_i$の方が最適な場合は高々59回しかありません(60回以上$B_i(>1)$をかけると$10^18$を超えてしまうので)。
したがって、各クエリ毎に$r-l$が十分に小さければ愚直に、それ以外は$B_i==1$であるような箇所がいくつか存在するはずなので、その区間は$A_i$の累積和を予め遅延セグ木などで求めておくことで高速に解を求めることができます。
G.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);
BIT bit = new BIT(N);
for(int i=0;i<N;i++)
bit.add(i+1,A[i]);
int[] B = sc.nextInt(N);
TreeSet<Integer> set = new TreeSet<>();
for(int i=0;i<N;i++)
if(B[i]>1)
set.add(i+1);
int Q = sc.nextInt();
while(Q-->0){
int q = sc.nextInt();
if(q==1){
int i = sc.nextInt()-1;
int x = sc.nextInt();
int sub = x-A[i];
A[i] = x;
bit.add(i+1,sub);
}
if(q==2){
int i = sc.nextInt()-1;
int x = sc.nextInt();
if(B[i]>1)
set.remove(i+1);
B[i] = x;
if(B[i]>1)
set.add(i+1);
}
if(q==3){
int l = sc.nextInt();
int r = sc.nextInt();
long v = 0;
if(r-l>100){
int index = l;
while(index<=r){
Integer next = set.ceiling(index);
if(next==null||r<next)
next = r;
v += (next==1?0:bit.sum(next-1))-(index==1?0:bit.sum(index-1));
v = Math.max(v+A[next-1],v*B[next-1]);
index = next+1;
}
}
else{
for(int i=l;i<=r;i++)
v = Math.max(v+A[i-1],v*B[i-1]);
}
out.println(v);
}
}
out.close();
}
}
感想
A,B:易しい
C:ちょっと難しく考えすぎた
D:少し手間取ったけどどうにか思いつけた
E:実装が遅い…
F:比較的簡単め？
G:通るかドキドキだったから通って良かった
って感じでした。
初全完！毎度こうだと良いんですけどねぇ…。