はじめに
今回はコンテスト中にEまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果をご確認ください。
では、見ていきましょう。
A - Subsegment Reverse
問題文はこちら
区間反転はライブラリ化してあるのでそれを使いましたが、内部的には愚直に交換を行なっています。
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、L、Rの受け取り
int N = sc.nextInt();
int L = sc.nextInt();
int R = sc.nextInt();
//答えの構築
int[] ans = new int[N];
Arrays.setAll(ans,i->i+1);
//区間反転
ArrayFunction.reverseRange(ans,L-1,R);
//答えの出力
out.println(ans);
out.close();
}
}
B - Nutrients
問題文はこちら
$A$から$X$を引いていって、$0$より大きい値が$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){
//N、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(M);
//Xだけ引いていく
while(N-->0)
for(int i=0;i<M;i++)
A[i] -= sc.nextInt();
//全て0以下か判定して出力
boolean isGood = true;
for(int num:A)
isGood &= num<=0;
out.println(isGood?"Yes":"No");
out.close();
}
}
C - Keys
問題文はこちら
各鍵が正しいかダミーかの組み合わせは$2^N$通りであり、矛盾しない組み合わせかの判定も$O(K)$で行えるので、bit全探索で愚直にシミュレーションして解きました。
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、M、Kの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
//Aをbit列として、Rをbooleanとして受け取る
int[] A = new int[M];
boolean[] R = new boolean[M];
for(int i=0;i<M;i++){
int C = sc.nextInt();
for(int a:sc.nextInt(C))
A[i] |= 1<<(a-1);
R[i] = sc.nextChar()=='o';
}
//数え上げ用変数
int ans = 0;
//bit全探索
Loop:for(int i=0;i<1<<N;i++){
for(int j=0;j<M;j++)
if((Integer.bitCount(i&A[j])>=K)^R[j]) //テスト結果が正しくなかったらスルー
continue Loop;
//直前のループを抜けた=矛盾が無いので加算
ans++;
}
//答えの出力
out.println(ans);
out.close();
}
}
D - Masked Popcount
問題文はこちら
$N$以下でとあるビットが立っている数の総和は桁DPを用いることで高速に求められます。
ですので、$M$の立っているビットそれぞれに対してそのビットが立っているものの総和を数え上げることで答えを求めることができます。
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);
private static final int MOD = 998244353;
public static void main(String[] args){
//N、Mの受け取り
long N = sc.nextLong();
long M = sc.nextLong();
//数え上げ用変数
long ans = 0;
//全bitを調べる
for(int i=0;i<60;i++){
//bitが立っていて、かつNの最高位bit以下なら桁DPで数え上げる
if((M&(1L<<i))>0&&1L<<i<=N){
ans += dp(N,i);
ans %= MOD;
}
}
out.println(ans);
out.close();
}
//桁DP用メソッド
private static long dp(long N,int index){
String S = Long.toBinaryString(N);
index = S.length()-1-index;
long[][] dp = new long[S.length()][4];
dp[0][1] = 1;
dp[0][2] = index!=0?1:0;
for(int i=1;i<S.length();i++){
dp[i][S.charAt(i)-'0'] += dp[i-1][0]+dp[i-1][1];
dp[i][2] += dp[i-1][2]+dp[i-1][3];
if(dp[i][2]>=MOD)
dp[i][2] -= MOD;
dp[i][3] += dp[i-1][2]+dp[i-1][3];
if(dp[i][3]>=MOD)
dp[i][3] -= MOD;
if(S.charAt(i)=='1')
dp[i][2] += dp[i-1][0]+dp[i-1][1];
if(dp[i][2]>=MOD)
dp[i][2] -= MOD;
if(i==index)
dp[i][0] = dp[i][2] = 0;
}
return MathFunction.modSum(MOD,dp[S.length()-1]);
}
}
E - Max/Min
問題文はこちら
それぞれの値が$A$の中にいくつあるかを数え上げた配列$A'$を定義します。
$i=1,2,\dots,10^6$について、$\lfloor \frac{A'_j}{A'_i}\rfloor = K (0<K,i<j)$となるような$j$の範囲は$O(1)$で求まり、該当する$A'j$の個数はBinary Indexed Treeを用いることで高速に求めることができます。調べるべき$K$の個数は調和級数の考え方から、$i$の上限を$M$とすると全部で$O(M \log M)$個程度なのでこれは十分高速に処理できます。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//上記のA'に該当するBITを構築
BIT bit = new BIT(1_000_001);
for(int a:A)
bit.add(a,1);
//数え上げ用変数
long ans = 0;
//全探索
for(int i=1;i<=1_000_000;i++){
//自身と同じ値を事前の数え上げ
long sum = bit.sum(i)-(i==1?0:bit.sum(i-1));
bit.add(i,-sum);
//上記のKを全探索(i*jの値で適切に枝切り)
for(int j=1;i*j<=1_000_000;j++){
ans += sum*(bit.sum(1_000_000)-(i*j==1?0:bit.sum(i*j-1)));
}
ans += sum*(sum-1)>>1;
}
//答えの出力
out.println(ans);
out.close();
}
}
感想
A,B:易しい
C:久々にまんまbit全探索って感じの問題解いた気がする
D:かなり手間取った
E:もっと手間取った
って感じでした。
むむむ…ペナが最近多いな…圧倒的注意不足…。