はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Zero Sum Game
問題文はこちら
ゲームの前後で全員の持ち点の総和は変化しないので、$A$の総和が$0$であることから、$A_1～A_{N-1}$の総和の符号を反転したものが答えになります。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N-1);
//総和求めて符号反転
long ans = MathFunction.sum(A);
out.println(-ans);
out.close();
}
}
B - Commencement
問題文はこちら
HashMapを使って各文字が何文字ずつ出現しているか調べ、出現した個数を集計して判定しました。
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の受け取り
char[] S = sc.nextCharArray();
//各文字の数え上げ
HashMap<Character,Integer> map = new HashMap<>();
for(char c:S)
map.merge(c,1,Integer::sum);
//個数ごとに集計
HashMap<Integer,Integer> map2 = new HashMap<>();
for(Integer sum:map.values())
map2.merge(sum,1,Integer::sum);
//条件を満たしているか判定
boolean isGood = true;
for(Integer sum:map2.values())
isGood &= sum==2;
//答えの出力
out.println(isGood?"Yes":"No");
out.close();
}
}
C - Airport Code
問題文はこちら
2つ目の条件を満たすかどうかは$S$の末尾にxを追加して1つ目の条件を満たすかを判定すれば良いので、$S$には予めxを付け加えておきます。
後は$T$を小文字にして各文字が順番通りに存在するかを判定してあげれば良いです。
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){
//S、Tの受け取り(前処理込み)
String S = sc.next()+"x";
String T = sc.next().toLowerCase();
//条件判定
boolean isGood = true;
int index = -1;
for(int i=0;i<3;i++){
index = S.indexOf(T.charAt(i),index+1);
isGood &= index!=-1;
}
//答えの出力
out.println(isGood?"Yes":"No");
out.close();
}
}
D - Divide Interval
問題文はこちら
セグメント木のノードの図からも分かるとおり、貪欲に区間を伸ばしながら解を構築するのが最善なので、それを実装しました。
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){
//L、Rの受け取り
long L = sc.nextLong();
long R = sc.nextLong();
//貪欲に区間構築(尺取りの要領)
ArrayList<long[]> ans = new ArrayList<>();
while(L<R){
int sub = 0;
while(L%(1L<<sub)==0&&L+(1L<<sub)<=R)
sub++;
sub--;
ans.add(new long[]{L,L+(1L<<sub)});
L += 1L<<sub;
}
//答えの出力
out.println(ans.size());
for(long[] range:ans)
out.println(range);
out.close();
}
}
E - Weighted Tic-Tac-Toe
問題文はこちら
交互に自身の得点を上げようとするのは、高橋君の得点から青木君の得点から引いた値を$K$とすると、この$K$を最大化、最小化することと同じなので、再帰関数でどっちの番かを管理しながら最善手を探索することで本問題を解きました。
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){
//Aの受け取り
int[][] A = sc.nextInt(3,3);
//答えの探索と出力
long ans = dfs(0,A,new int[3][3]);
out.println(ans>0?"Takahashi":"Aoki");
out.close();
}
//再帰関数(何ターン目か、A、今の盤面を引数に)
private static long dfs(int now,int[][] A,int[][] map){
//終了判定
int result = isEnd(map);
if(result==1)
return check(A,map);
else if(result>1)
return result==2?Long.MAX_VALUE:Long.MIN_VALUE;
//最善手模索
long ans = now==0?Long.MIN_VALUE:Long.MAX_VALUE;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(map[i][j]==0){
map[i][j] = now+1;
ans = now==0?Math.max(ans,dfs(1-now,A,map)):Math.min(ans,dfs(1-now,A,map));
map[i][j] = 0;
}
}
}
return ans;
}
//終了判定
private static int isEnd(int[][] map){
for(int i=0;i<3;i++){
if(map[i][0]>0&&map[i][0]==map[i][1]&&map[i][0]==map[i][2])
return map[i][0]+1;
if(map[0][i]>0&&map[0][i]==map[1][i]&&map[0][i]==map[2][i])
return map[0][i]+1;
}
if(map[0][0]>0&&map[0][0]==map[1][1]&&map[0][0]==map[2][2])
return map[0][0]+1;
if(map[0][2]>0&&map[0][2]==map[1][1]&&map[0][2]==map[2][0])
return map[0][2]+1;
int sum = 0;
for(int[] temp:map)
for(int num:temp)
sum += num>0?1:0;
return sum==9?1:0;
}
//得点集計メソッド
private static long check(int[][] A,int[][] map){
long ans = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ans += map[i][j]==1?A[i][j]:map[i][j]==2?-A[i][j]:0;
}
}
return ans;
}
}
実装めちゃくちゃ遅かった…悲しい…。
F - Subsequence LCM
問題文はこちら
公式解説の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);
private static final int MOD = 998244353;
public static void main(String[] args){
//N、Mの受け取り
int N = sc.nextInt();
long M = sc.nextLong();
//専用対策
if(M==1){
int count = 0;
while(N-->0){
long A = sc.nextLong();
if(A==1)
count++;
}
System.out.println((pow(2,count)+MOD-1)%MOD);
return;
}
//Mの素因数を求める
long[][] subM = primes(M);
//Aが各素因数を持つかをbitに反映させる
int L = subM.length;
int[] count = new int[1<<L];
while(N-->0){
//Aの受け取り
long num = sc.nextLong();
if(M%num>0) //そもそもMの約数でないならスルー
continue;
//各素因数を持っているか判定
int bit = 0;
for(int i=0;i<subM.length;i++){
int counter = 0;
while(num%subM[i][0]==0){
counter++;
num /= subM[i][0];
}
if(subM[i][1]==counter)
bit |= 1<<i;
}
count[bit]++;
}
//bitDP
int[] dp = new int[1<<L];
dp[0] = 1;
for(int i=0;i<1<<L;i++){
int[] next = dp.clone();
for(int j=0;j<1<<L;j++){
next[i|j] += multiply(dp[j],(int)(pow(2,count[i])+MOD-1)%MOD);
if(next[i|j]>=MOD)
next[i|j] -= MOD;
}
dp = next;
}
//答えの出力
out.println(dp[(1<<L)-1]);
out.close();
}
//オーバーフロー対策
private static int multiply(int a,int b){
return (int)((long)a*b%MOD);
}
//素因数分解メソッド
private static long[][] primes(long N){
ArrayList<long[]> ans = new ArrayList<>();
if(!MathFunction.isPrime(N)){
for(long i=2;i*i<=N;i++){
if(N%i==0){
int counter = 0;
while(N%i==0){
counter++;
N /= i;
}
ans.add(new long[]{i,counter});
}
}
}
if(N>1)
ans.add(new long[]{N,1});
return ans.toArray(new long[ans.size()][]);
}
//static変数にMODを載せたので専用メソッドを
private static long pow(long a,long b){
long ans = 1;
while(b>0){
if((b&1)==1)
ans = ans*a%MOD;
a = a*a%MOD;
b >>= 1;
}
return ans;
}
}
やっぱり$O(\sqrt{M})$はちょっとキツいなぁ…。
感想
A,B,C:易しい
D:未証明のまま通した(後からセグ木考えてみたら確かにになった)
E:実装下手くそ過ぎた…
F:撃沈…
って感じでした。
いやぁ…$O(\sqrt{M})$は通らないでしょって思ってポラードロー法を実装しようとしてたらコンテスト終わってしまいました…悲しい…。