はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解けたのでそれを載せようと思います。
では、見ていきましょう。
A - September
問題文はこちら
愚直に調べました。
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){
String[] S = sc.next(12);
int ans = 0;
for(int i=0;i<12;i++)
if(S[i].length()==i+1)
ans++;
out.println(ans);
out.close();
}
}
B - 1D Keyboard
問題文はこちら
最初のキーを始点に、貪欲に移動するのが最適なのでシミュレーションで解きました。
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){
String S = sc.next();
int ans = 0;
for(char c='B';c<='Z';c++)
ans += Math.abs(S.indexOf(c+"")-S.indexOf((char)(c-1)+""));
out.println(ans);
out.close();
}
}
C - Max Ai+Bj
問題文はこちら
$A$と$B$の最大値同士を選ぶのが最適なのでそれを求めました。
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);
int maxA = MathFunction.max(A);
int maxB = MathFunction.max(B);
out.println(maxA+maxB);
out.close();
}
}
D - Hidden Weights
問題文はこちら
制約より、必ず解が存在するので各連結成分に対してテキトーに選んだ始点からBFSの要領で愚直に解を求めれば$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<int[]>> list = new ArrayList<>();
for(int i=0;i<N;i++)
list.add(new ArrayList<>());
while(M-->0){
int v = sc.nextInt()-1;
int u = sc.nextInt()-1;
int w = sc.nextInt();
list.get(v).add(new int[]{u,w});
list.get(u).add(new int[]{v,-w});
}
long[] ans = new long[N];
HashSet<Integer> set = new HashSet<>();
for(int i=1;i<=N;i++)
set.add(i);
ArrayDeque<Integer> deq = new ArrayDeque<>();
int index = 0;
while(index<N){
deq.add(index);
while(deq.size()>0){
int now = deq.pollFirst();
for(int[] p:list.get(now)){
if(set.remove(p[0])){
ans[p[0]] = ans[now]+p[1];
deq.add(p[0]);
}
}
}
while(!set.remove(index))
index++;
}
out.println(ans);
out.close();
}
}
E - How to Win the Election
問題文はこちら
「$i$番目の候補者に$c$票追加で入った後に自分以外に$A[i]+c$を超えるように愚直に票を割り振ったときに$i$番目の候補者は当選できるか」という判定問題に帰着させ、$c$を二分探索することで解を求めることができます。
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();
if(N==M){
out.println(new int[N]);
out.close();
return;
}
long K = sc.nextLong();
long[] A = sc.nextLong(N);
long subK = K-MathFunction.sum(A);
long[] subA = A.clone();
Arrays.sort(subA);
long[] sumA = new long[N+1];
for(int i=N;i>0;i--)
sumA[i-1] = sumA[i]+subA[i-1];
long[] answer = new long[N];
for(int i=0;i<N;i++){
long a = 0;
long b = subK;
long ans = -1;
while(a-b<1){
long c = (a+b)>>1;
int index = Searcher.overSearch(subA,A[i]+c);
if(0<index&&A[i]+c<subA[index-1]){
throw new NullPointerException();
}
if(index<=N-M){
a = c+1;
continue;
}
long sum = N-M<=Searcher.upSearch(subA,A[i])?
sumA[N-M-1]-sumA[index]-A[i]:sumA[N-M]-sumA[index];
if(subK-c<(A[i]+c+1)*(M+index-N)-sum)
b = (ans=c)-1;
else
a = c+1;
}
answer[i] = ans;
}
out.println(answer);
out.close();
}
}
F - Knapsack with Diminishing Values
問題文はこちら
問題文より、考慮すべき$k_i$は$O(W)$個なので動的計画法の要領で愚直に$k_i$を調べると$O(N^2W)$であり、$1$個あたりのうれしさは$v_i-k_i$で表されることから、DPテーブルに変化が無くなるまでループを回しても実際は高速に処理することができます。
これは公式解説のものと本質が変わらないことからも高速に動作することがわかるかと思います(考慮する量が少し増えるのでちょっと重いかもしれませんが)。
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 W = sc.nextInt();
int[][] goods = sc.nextInt(N,2);
boolean[] checked = new boolean[N];
long[] dp = new long[W+1];
int k = 1;
while(true){
int count = 0;
for(int i=0;i<N;i++){
if(checked[i])
continue;
count++;
long[] next = dp.clone();
boolean flag = false;
int g = goods[i][0];
long v = (long)goods[i][1]-k-k+1;
for(int j=g;j<=W;j++){
if(next[j]<dp[j-g]+v){
next[j] = dp[j-g]+v;
flag = true;
}
}
dp = next;
checked[i] = !flag;
}
if(count==0)
break;
k++;
}
out.println(MathFunction.max(dp));
out.close();
}
}
感想
A,B,C:易しい
D:実装に時間かかった…
E:全然合わなくて終了ギリギリに…
F:さすがに間に合わなかった…
って感じでした。
う～ん…速度が…出ない…。