はじめに
今回はコンテスト中にEまで解けたのでそれをそのまま載せようかなと思います。
なお、僕のライブラリに関しては提出結果をご確認ください。
では、見ていきましょう。
A - Divisible
問題文はこちら
$K$で割れる物をArrayList<Integer>にaddしていって答えを構築しました。
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、Kの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//答え用List
ArrayList<Integer> list = new ArrayList<>();
//Kで割り切れるものをadd
for(int A:sc.nextInt(N))
if(A%K==0)
list.add(A/K);
//答えの出力
out.println(list);
out.close();
}
}
B - Substring
問題文はこちら
部分文字列の個数は$\frac{1}{2}N(N+1)$個なので、制約上全探索しても十分高速に処理できます。
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の受け取り
String S = sc.next();
//部分列を入れる用のSet
HashSet<String> set = new HashSet<>();
for(int i=0;i<S.length();i++)
for(int j=i;j<S.length();j++)
set.add(S.substring(i,j+1));
//種類数を答える
out.println(set.size());
out.close();
}
}
C - Ideal Holidays
問題文はこちら
$1$週間のどこに位置するかだけが重要なので$D_i$は$A+B$で割ったあまりだけで考えて良いです。あとは昇順に並べ替えて、前後の差が$B$より大きい区間があるかを判定すれば良いです($D$の全部が休日なら、平日の区間を$D_i$と$D_{i+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、A、B、Dの受け取り
int N = sc.nextInt();
int A = sc.nextInt();
int B = sc.nextInt();
int[] D = sc.nextInt(N);
//昇順で処理したいのでTreeSetで
TreeSet<Integer> set = new TreeSet<>();
//あまりで考える
for(int num:D)
set.add((num-1)%(A+B));
//判定用変数
boolean isOK = false;
//各区間がBより大きいか調べる
for(int d:set){
Integer next = set.higher(d);
if(next==null)
next = set.ceiling(0)+A+B;
isOK |= next-d>B;
}
//答えの出力
out.println(isOK?"Yes":"No");
out.close();
}
}
実装に手間取りました…。
D - Popcount and XOR
問題文はこちら
まず、以下の条件を一つでも満たすなら答えは無いです。
- $a+b-\mathrm{popcount}(C)$が奇数
$\mathrm{popcount}(C)$を超過した分は$X$と$Y$のどちらもビットを立てて辻褄を合わせるしかなく、奇数だと片方だけビットが立ってしまうので構築不可 - $120-\mathrm{popcount}(C)<a+b$
$C$のビットが立っている箇所以外でしか上記の辻褄合わせはできないので、$a+b$が$120-\mathrm{popcount}(C)$を超過したら構築不可 - $a+b<\mathrm{popcount}(C)$
そもそも立てられるビットの個数が不足しているなら構築不可 - $|a-b|>\mathrm{popcount}(C)$
片方だけ立てるビットが多すぎると排他的論理和を取った時に$\mathrm{popcount}(X \oplus Y)$が$\mathrm{popcount}(C)$を超過してしまうため構築不可
以上を除いて考えます。
まず、$a+b>\mathrm{popcount}(C)$を満たすなら$C$のビットが立っていない箇所で$X$、$Y$の両方ビットを立てることで辻褄を合わせます。あとは$\mathrm{popcount}(X)=a$、$\mathrm{popcount}(Y)=b$を満たすように適当に振り分ければ解が構築できます。
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){
//a、b、Cの受け取り
int a = sc.nextInt();
int b = sc.nextInt();
long C = sc.nextLong();
//Cの立っているビットを数える
int bc = Long.bitCount(C);
//構築不可なら-1
if((a+b-bc)%2!=0||120-bc<a+b||a+b<bc||Math.abs(a-b)>bc)
out.println(-1);
//構築できる場合
else{
//先にXもYも立てるビットを立てておく
long X = 0;
long Y = 0;
for(int i=0;a+b>bc;i++)
if((C&(1L<<i))==0){
X |= 1L<<i;
Y |= 1L<<i;
a--;
b--;
}
//あとはCの立っているビットをよしなに
for(int i=0;a>0;i++)
if((C&(1L<<i))>0){
X |= 1L<<i;
C ^= 1L<<i;
a--;
}
for(int i=0;b>0;i++)
if((C&(1L<<i))>0){
Y |= 1L<<i;
b--;
}
//答えの出力
out.println(X+" "+Y);
}
out.close();
}
}
E - Set Add Query
問題文はこちら
セグメント木を用いて解きました。
各時点での$|S|$と$A_i$を同時に求めるのは難しいですが、各時点での$|S|$だけを求めるのは高速に行なうことができ、各$i$について、$i$が奇数回出現したタイミングから偶数回出現したタイミングまでの区間で$|S|$が$A_i$に加算されることを考えると、各区間における$|S|$の区間和が求められれば良くて、これはセグメント木で処理できます。
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、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//出現回数の偶奇を管理する用のSet
HashSet<Integer> set = new HashSet<>();
//加算する区間の記録用List
ArrayList<int[]> list = new ArrayList<>();
//前回出現した時刻を記録する用
int[] bef = new int[N+1];
//区間加算用
SegmentTree<Long> segT = new SegmentTree<>(Q,0L,false){
public Long function(Long a,Long b){
return a+b;
}
};
//クエリ処理
for(int i=0;i<Q;i++){
//xの受け取り
int x = sc.nextInt();
//偶奇に合わせて処理
if(set.add(x))
bef[x] = i;
else{
set.remove(x);
list.add(new int[]{x,bef[x],i-1});
}
//|S|の記録
segT.update(i,(long)set.size());
}
//最後にsetに残ってるやつも記録
for(int x:set)
list.add(new int[]{x,bef[x],Q-1});
//答えの構築
long[] ans = new long[N];
for(int[] range:list){
ans[range[0]-1] += segT.query(range[1],range[2]);
}
//答えの出力
out.println(ans);
out.close();
}
}
少し悩みましたが、比較的速く気付くことができました。
感想
A,B:易しい
C:いっぱいペナ出しちゃった…
D:気付けばそんなに難しくない
E:ちょっと発想が必要だけど、易しめ
って感じでした。
う～ん…ペナが痛い…。詰めの甘さが目立ってしまった回でした。