はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果をご確認ください。
では、見ていきましょう。
A - AtCoder Line
問題文はこちら
条件を数式に落とし込むと$\min(X,Y)<Z<\max(X,Y)$と表せるので、これを判定しました。
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,X,Y,Zの受け取り
int N = sc.nextInt();
int X = sc.nextInt();
int Y = sc.nextInt();
int Z = sc.nextInt();
//条件の判定
out.println(MathFunction.rangeCheckClose(Z,Math.min(X,Y),Math.max(X,Y))?"Yes":"No");
out.close();
}
}
B - Typing
問題文はこちら
$S$の各文字について、$T$の何番目に表れるかを調べることで解を構築しました。
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){
//S、Tの受け取り
String S = sc.next();
String T = sc.next();
//各文字がTの何文字目に出てくるか調べる
int[] ans = new int[S.length()];
int index = 0;
for(int i=0;i<S.length();i++){
index = T.indexOf(S.charAt(i),index);
ans[i] = ++index;
}
//答えの出力
out.println(ans);
out.close();
}
}
C - Standing On The Shoulders
問題文はこちら
一番上に来る巨人の頭の大きさ($B_i-A_i$)を$C$とすると、全体の高さは$\sum{A_i}+C$なので、$B_i-A_i$を最大の最大値を求めてあげれば答えが求まります。
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){
//Nの受け取り
int N = sc.nextInt();
//B-Aの最大値を求めつつ、Aの総和を求める
int max = 0;
long sum = 0;
while(N-->0){
int A = sc.nextInt();
int B = sc.nextInt();
max = Math.max(max,B-A);
sum += A;
}
//答えの出力
out.println(sum+max);
out.close();
}
}
D - Permutation Subsequence
問題文はこちら
$A'_{A_i}=i$なる$A'$を構築し、先頭から$K$個ずつTreeSetに追加することで、答えをset.last()-set.first()で求められるようになり、これは十分高速に動作します。
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、Kの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//上記のA'の構築
int[] invP = new int[N+1];
for(int i=1;i<=N;i++)
invP[sc.nextInt()] = i;
//順にK個ずつ入れて最小値を求める
int index = 1;
TreeSet<Integer> set = new TreeSet<>();
int ans = Integer.MAX_VALUE;
while(index<=N){
//最初のK個入れる部分もまとめて処理したかったのでwhileで
while(index<=N&&set.size()<K){
set.add(invP[index++]);
}
if(set.size()==K)
ans = Math.min(ans,set.last()-set.first());
set.remove(invP[index-K]);
}
//答えの出力
out.println(ans);
out.close();
}
}
最初$\lbrace P_{i_1}, P_{i_2}, \dots, P_{P_K} \rbrace$の意味を集合ではなく数列だと勘違いして「本問題の制約下では良い添字列が必ず$1$つ以上存在することが示せます。」が本当か…？になってしまい、時間を食いました…。注意力さん…。
E - Clique Connect
問題文はこちら
各操作は「$i=2,3,\dots,K_1$に対して、$A_{i-1}$と$A_i$の間に辺を張る」と言い換えられるので、辺の総数は$O(\mathrm{sum}(K_i))$であり、クラスカル法の要領で解を高速に求めることができます。
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、M、C、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] C = new int[M];
int[][] A = new int[M][];
for(int i=0;i<M;i++){
int K = sc.nextInt();
C[i] = sc.nextInt();
A[i] = sc.nextInt(K);
}
//クラスカル法
PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->Integer.compare(C[a],C[b]));
for(int i=0;i<M;i++)
queue.add(i);
UnionFind uf = new UnionFind(N+1);
long ans = 0;
while(queue.size()>0){
int index = queue.poll();
for(int i=1;i<A[index].length;i++)
if(uf.unite(A[index][i-1],A[index][i]))
ans += C[index];
}
//答えの出力
out.println(uf.size(1)==N?ans:-1);
out.close();
}
}
F - Estimate Order
問題文はこちら
F.java
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、M、条件(重み付き有向辺)の受け取り
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 A = sc.nextInt()-1;
int B = sc.nextInt()-1;
int C = sc.nextInt();
list.get(A).add(makeArray(B,-C));
list.get(B).add(makeArray(A,C));
}
//集合ごとにまとめる
boolean[] checked = new boolean[N];
ArrayList<ArrayList<Integer>> subList = new ArrayList<>();
ArrayList<ArrayList<Integer>> valList = new ArrayList<>();
ArrayList<Integer> bit = new ArrayList<>();
for(int i=0;i<N;i++){
if(checked[i])
continue;
checked[i] = true;
ArrayList<Integer> sub = new ArrayList<>();
ArrayList<Integer> val = new ArrayList<>();
sub.add(i);
val.add(0);
for(int j=0;j<sub.size();j++){
int now = sub.get(j);
int num = val.get(j);
for(int[] path:list.get(now)){
if(!checked[path[0]]){
sub.add(path[0]);
val.add(num+path[1]);
checked[path[0]] = true;
}
}
}
int min = 0;
for(int num:val)
min = Math.min(min,num);
int b = 0;
for(int j=0;j<val.size();j++){
int num = val.get(j)-min;
b |= 1<<num;
val.set(j,num);
}
subList.add(sub);
valList.add(val);
bit.add(b);
}
int count = 0;
for(ArrayList<Integer> l:subList)
count += Math.max(0,2-l.size());
//ユーザー解説より
if(count>1)
for(int i=subList.size()-1;i>=0;i--)
if(subList.get(i).size()==1){
subList.remove(i);
valList.remove(i);
bit.remove(i);
}
//再帰で解を求める
ArrayList<ArrayList<Integer>> index = new ArrayList<>();
for(int i=0;i<subList.size();i++)
index.add(new ArrayList<>());
dfs(0,0,bit,index,N);
//答えの構築&出力
int[] ans = new int[N];
Arrays.fill(ans,-1);
for(int i=0;i<subList.size();i++)
for(int j=0;j<subList.get(i).size();j++)
if(index.get(i).size()==1)
ans[subList.get(i).get(j)] = index.get(i).get(0)+valList.get(i).get(j)+1;
String answer = Arrays.toString(ans);
System.out.println(answer.substring(1,answer.length()-1).replace(",",""));
}
//全探索用の再帰メソッド
private static boolean dfs(int now,int sum,ArrayList<Integer> bit,ArrayList<ArrayList<Integer>> index,int N){
if(now==bit.size())
return true;
boolean flag = false;
for(int i=0;i<N;i++){
int sub = bit.get(now)<<i;
if(1<<N<=sub)
break;
if((sum&sub)>0)
continue;
if(dfs(now+1,sum|sub,bit,index,N)){
if(!index.get(now).contains(i))
index.get(now).add(i);
flag = true;
}
}
return flag;
}
private static int[] makeArray(int... nums){
return nums;
}
}
感想
A,B,C:易しい
D:問題文読むのに時間かかっちゃった…
E:気付けば簡単め
F:う～ん…解けなかった…
って感じでした。
Eまでの速度感はそこまで悪くない気はしますが、もっと速く解きたいですね…。