はじめに
今回はDまで、コンテスト後にEとFを解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Past ABCs
問題文はこちら
$S$の末尾$3$文字の数字だけ見れば良いので、substringで切り出して数値に変換し、条件を満たすか判定しました。
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の受け取り
int N = Integer.parseInt(sc.next().substring(3));
//判定
out.println(0<N&&N!=316&&N<350?"Yes":"No");
out.close();
}
}
000を省くのを忘れてて$1$ペナ…。
B - Dentist Aoki
問題文はこちら
今歯が生えているかどうかをBitSetを使って保持して解きました。
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){
//Nの受け取り
int N = sc.nextInt();
//歯の状態を保持するBitSet
var bit = new java.util.BitSet(N+1);
bit.set(1,N+1);
//Qの受け取り
int Q = sc.nextInt();
//クエリ処理
while(Q-->0){
//Tの受け取り
int T = sc.nextInt();
//反転
bit.flip(T);
}
//総和を求める
out.println(bit.cardinality());
out.close();
}
}
C - Sort
問題文はこちら
先頭から条件を満たすように貪欲に操作を行なえば$N-1$回以下で構築可能なので、これを実装しました。
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();
//Aに対する位置、位置に対するAを記録するMap
HashMap<Integer,Integer> mapA = new HashMap<>();
HashMap<Integer,Integer> indexA = new HashMap<>();
//記録
for(int i=1;i<=N;i++){
int A = sc.nextInt();
mapA.put(A,i);
indexA.put(i,A);
}
//貪欲に操作
ArrayList<int[]> ans = new ArrayList<>();
for(int i=1;i<=N;i++){
if(mapA.get(i)!=i){
int index = mapA.get(i);
int val = indexA.get(i);
mapA.put(val,index);
indexA.put(index,val);
mapA.put(i,i);
indexA.put(i,i);
ans.add(new int[]{i,index});
}
}
//答えの出力
out.println(ans.size());
for(int[] answer:ans)
out.println(answer);
out.close();
}
}
D - New Friends
問題文はこちら
操作は同一の連結成分内でしか行えず、頂点数$V$に対して辺は$\frac{1}{2}V(V-1)$本張れることに着目すれば、UnionFindで各連結成分を管理し、その中の辺の本数から追加で張れる本数を求めながら答えを数え上げました。
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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//UnionFindの構築
UnionFind uf = new UnionFind(N+1);
while(M-->0){
int A = sc.nextInt();
int B = sc.nextInt();
uf.unite(A,B);
}
//各連結成分のrootを求める
HashSet<Integer> set = new HashSet<>();
for(int i=1;i<=N;i++)
set.add(uf.root(i));
//各連結成分ごとに張れる辺の本数を求めて数え上げ
long ans = 0;
for(int r:set){
long s = uf.size(r);
long p = uf.pathCount(r);
ans += s*(s-1)/2-p;
}
//答えの出力
out.println(ans);
out.close();
}
}
E - Toward 0
問題文はこちら
公式解説の通りです。
E.java
import java.util.Scanner;
import java.util.HashMap;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、A、X、Yの受け取り
long N = sc.nextLong();
int A = sc.nextInt();
int X = sc.nextInt();
int Y = sc.nextInt();
//メモ化再帰で求める
System.out.println(dfs(N,A,X,Y));
}
private static final HashMap<Long,Double> map = new HashMap<>();
private static double dfs(long N,int A,int X,int Y){
//Nが0なら終わり
if(N==0){
return 0L;
}
//すでに答えがわかってるならそれを返す
if(map.containsKey(N)){
return map.get(N);
}
//答えを求める
double ans = Y;
for(int i=2;i<7;i++){
ans += dfs(N/i,A,X,Y)+Y;
}
ans /= 5.0;
double sum = 0;
long num = N;
while(num>0){
num /= A;
sum += X;
}
//記録
map.put(N,Math.min(ans,sum));
//答えを返す
return Math.min(ans,sum);
}
}
う～ん…再帰で実装するという判断になれず…無念…。
F - Transpose
問題文はこちら
直前までの(の数と)の数の差が偶数か奇数かで文字列が反転するかは求められるので、再帰的に処理することで答えを構築しました。
文字列同士の連結はArrayDeque<Character>で保持しておいて連結するときに文字数が少ない方を多い方に加えることで全体で$O(\log |S|)$回の処理で構築できます。
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 HashMap<Integer,Integer> map = new HashMap<>();
public static void main(String[] args){
//Sの受け取り
String S = sc.next();
//各'('の位置を保持しながら、"()"で括られた区間を求める
ArrayDeque<Integer> d = new ArrayDeque<>();
for(int i=0;i<S.length();i++){
if(S.charAt(i)=='(')
d.add(i);
if(S.charAt(i)==')')
map.put(d.pollLast(),i);
}
//答えを求める
ArrayDeque<Character> deq = dfs(0,0,S);
//答えの出力
StringBuilder ans = new StringBuilder();
for(char c:deq)
ans.append(c);
out.println(ans);
out.close();
}
//再帰用メソッド
private static ArrayDeque<Character> dfs(int now,int depth,String S){
ArrayDeque<Character> deq = new ArrayDeque<>();
//"()"の中を処理
while(now<S.length()){
//"()"の中に入るなら深さを1加算して再帰
if(S.charAt(now)=='('){
ArrayDeque<Character> sub = dfs(now+1,depth+1,S);
now = map.get(now)+1; //終点にポインタを移動
//反転させるか否かで順番を入れ替える
if(depth%2==0)
deq = merge(deq,sub);
else
deq = merge(sub,deq);
}
//"()"を抜けたら復帰させる
else if(S.charAt(now)==')'){
return deq;
}
//文字は反転させるか否かで場合分けしながら記録
else{
if(depth%2==0)
deq.addLast(S.charAt(now++));
else{
char c = S.charAt(now++);
if(c<'a')
deq.addFirst((char)(c+'a'-'A'));
else
deq.addFirst((char)(c-'a'+'A'));
}
}
}
//答えを返す
return deq;
}
//マージテク用メソッド
private static ArrayDeque<Character> merge(ArrayDeque<Character> d1, ArrayDeque<Character> d2){
if(d1.size()>d2.size()){
while(d2.size()>0)
d1.addLast(d2.pollFirst());
return d1;
}
else{
while(d1.size()>0)
d2.addFirst(d1.pollLast());
return d2;
}
}
}
なんとか解けて良かった…。
感想
A:しょうもないミスを…
B,C,D:易しい
E:難しい…><
F:構文解析っぽくて面白かった
って感じでした。
う～ん…あまりにも精進不足が響いてる…。