はじめに
今回はコンテストに参加できなかったのでそのあとに解いたFまでを載せようと思います。
では、見ていきましょう。
A - delete .
問題文はこちら
System.in::readから直接読んでみました。
A.java
class Main{
public static void main(String[] args){
StringBuilder ans = new StringBuilder();
try{
int c;
while((c=System.in.read())>0)
if(c!='.')
ans.append((char)c);
System.out.println(ans);
}catch(Exception e){
}
}
}
B - 3^A
問題文はこちら
三進数の要領で答えを求めてあげれば解が構築できます。
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 M = sc.nextInt();
ArrayList<Integer> ans = new ArrayList<>();
for(int i=0;M>0;i++){
int sub = M%3;
while(sub-->0)
ans.add(i);
M /= 3;
}
out.println(ans.size());
out.println(ans);
out.close();
}
}
C - Count ABC Again
問題文はこちら
変更することでABCが連続する部分列として新しく含まれる、含まれなくなる可能性があるとしたら変更箇所と前後2つだけ見ればいいのでそれを実装しました。
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 Q = sc.nextInt();
char[] S = sc.nextCharArray();
int ans = 0;
for(int i=2;i<N;i++)
if(S[i-2]=='A'&&S[i-1]=='B'&&S[i]=='C')
ans++;
while(Q-->0){
int X = sc.nextInt()-1;
char C = sc.nextChar();
for(int i=Math.max(X,2);i<Math.min(X+3,N);i++)
if(S[i-2]=='A'&&S[i-1]=='B'&&S[i]=='C')
ans--;
S[X] = C;
for(int i=Math.max(X,2);i<Math.min(X+3,N);i++)
if(S[i-2]=='A'&&S[i-1]=='B'&&S[i]=='C')
ans++;
out.println(ans);
}
out.close();
}
}
D - Buildings
問題文はこちら
高い順に、自分と組み合わせとしてあり得る一番左端を求めてその区間に1を足すBITで処理し、最後数え上げをしました。
今思えばBITなんて使わなくてその場で数え上げればよかった…？()
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();
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Integer.compare(b[0],a[0]));
for(int i=0;i<N;i++)
queue.add(new int[]{sc.nextInt(),i});
TreeSet<Integer> set = new TreeSet<>();
BITInt bit = new BITInt(N);
while(queue.size()>0){
int[] query = queue.poll();
Integer left = set.floor(query[1]);
if(left==null)
left = 0;
bit.add(left+1,1);
bit.add(query[1]+1,-1);
set.add(query[1]);
}
int[] ans = new int[N];
for(int i=0;i<N;i++)
ans[i] = bit.sum(i+1);
out.println(ans);
out.close();
}
}
E - K-th Largest Connected Components
問題文はこちら
UnionFindで連結状態を管理しながら、Tree(TreeSet)で頂点番号を管理する方法で解きました。
Tree同士のマージには、要素数が少ない方を多い方に加える方法で計算量を落としています。
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 Q = sc.nextInt();
UnionFind uf = new UnionFind(N+1);
ArrayList<Tree<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++){
Tree<Integer> set = new Tree<>();
set.add(i);
list.add(set);
}
while(Q-->0){
int q = sc.nextInt();
if(q==1){
int u = sc.nextInt();
int v = sc.nextInt();
Tree<Integer> set1 = list.get(uf.root(u));
Tree<Integer> set2 = list.get(uf.root(v));
if(set1==set2)
continue;
uf.unite(u,v);
if(set1.size()<set2.size()){
var temp = set1;
set1 = set2;
set2 = temp;
}
for(Integer value:set2.toList())
set1.add(value);
list.set(uf.root(u),set1);
}
else{
int v = sc.nextInt();
int k = sc.nextInt();
Tree<Integer> set = list.get(uf.root(v));
if(set.size()<k)
out.println(-1);
else
out.println(set.get(set.size()-k));
}
}
out.close();
}
}
F - Teleporting Takahashi 2
問題文はこちら
動的計画法で解きました。
頂点$i$から頂点$i+1$への移動の分はテーブルの先頭を一つずらせば良く、$M$本の有向辺の分だけ追加で計算をすることで解を高速に求めることができます。
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);
private static final int MOD = 998244353;
public static void main(String[] args){
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[][] path = sc.nextInt(M,2);
for(int i=0;i<M;i++){
path[i][0]--;
path[i][1]--;
}
int[] dp = new int[N];
dp[0] = 1;
int head = (K+N-1)/N*N;
while(K-->0){
int[] sub = new int[M];
for(int i=0;i<M;i++)
sub[i] = dp[(path[i][0]+head)%N];
head--;
for(int i=0;i<M;i++){
dp[(path[i][1]+head)%N] += sub[i];
if(dp[(path[i][1]+head)%N]>=MOD)
dp[(path[i][1]+head)%N] -= MOD;
}
}
out.println(MathFunction.modSum(MOD,dp));
out.close();
}
}
感想
A:易しい
B:Bにしては難しめ？
C:気づけばどうってことはない
D:比較的易しい？
E:悩んだけど$k$が小さめだったのでそれを利用した
F:配列使いまわすのと発想が似ててわかりやすかった
という感じでした。
う～ん…コンテスト後だから解けたようなもんで、実際コンテスト中に解けるかと言われると…。