はじめに
今回はコンテスト中にFまで解けたのでそれを載せようと思います。
では、見ていきましょう。
A - 123233
問題文はこちら
先に各数字が存在するべき個数をメモしておいて、先頭から順に見て該当する数字の個数を減らしてみてちゃんと$0$になるかをチェックして解きました。
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){
String S = sc.next();
int[] map = new int[4];
Arrays.setAll(map,i->i);
for(char c:S.toCharArray())
if(c<'4')
map[c-'0']--;
for(int i=0;i<4;i++)
if(map[i]>0){
System.out.println("No");
return;
}
out.println("Yes");
out.close();
}
}
今思えばchar[]で受け取ってソートして122333と一致するか判定すればよかったですね。
B - Hurdle Parsing
問題文はこちら
|が出現するまでカウント用変数で-を数え上げて$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){
String S = sc.next();
int count = 0;
ArrayList<Integer> list = new ArrayList<>();
for(int i=1;i<S.length();i++){
if(S.charAt(i)=='|'){
list.add(count);
count = 0;
}
else
count++;
}
out.println(list);
out.close();
}
}
C - Move Segment
問題文はこちら
0だけの連続部分文字列、1だけの連続部分文字列を別々のArrayDequeに入れ、$K$番目の1が連続している箇所を直前の0が連続している箇所と入れ替える形で文字列を復元することで解きました。
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 K = sc.nextInt();
String S = sc.next();
ArrayDeque<String> zero = new ArrayDeque<>();
ArrayDeque<String> one = new ArrayDeque<>();
int bef = 0;
for(int i=1;i<N;i++){
if(S.charAt(i)!=S.charAt(bef)){
if(S.charAt(bef)=='0')
zero.add(S.substring(bef,i));
else
one.add(S.substring(bef,i));
bef = i;
}
}
if(S.charAt(bef)=='0')
zero.add(S.substring(bef));
else
one.add(S.substring(bef));
StringBuilder ans = new StringBuilder();
if(S.charAt(0)=='1'){
ans.append(one.pollFirst());
K--;
}
for(int i=1;i<K;i++){
ans.append(zero.pollFirst());
ans.append(one.pollFirst());
}
ans.append(one.pollFirst());
ans.append(zero.pollFirst());
while(zero.size()+one.size()>0){
if(zero.size()>0)
ans.append(zero.pollFirst());
if(one.size()>0)
ans.append(one.pollFirst());
}
out.println(ans);
out.close();
}
}
D - Strange Mirroring
問題文はこちら
反転している部分を$T$、元と同じ部分を$S$とすると、先頭から順に$STTSTSSTTSSTSTTS \dots$といった具合になっています。
パッと見わかりにくいですが、一番最初を$0$番目としてみると、$0$から$2^K-1$までの文字列を大小反転したものが$2^K$から$2^{K+1}-1$までとなっているのがわかるかと思います。この"何番目"という数字を$2$進数として見てよく観察すると、さっきの例で言えば$K$番目の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){
String S = sc.next();
int Q = sc.nextInt();
char[] ans = new char[Q];
for(int i=0;i<Q;i++){
long K = sc.nextLong();
long count = (K+S.length()-1)/S.length();
K = (K-1)%S.length();
ans[i] = S.charAt((int)K);
if(isReversed(count))
ans[i] ^= 32;
}
out.println(ans," ");
out.close();
}
private static final boolean isReversed(long K){
if(K==1)
return false;
long mid = 1;
while(K>(mid<<1))
mid <<= 1;
int ans = 0;
while(mid>0){
K -= mid;
while(K<=mid)
mid >>= 1;
ans ^= 1;
}
return ans==1;
}
}
E - 1D Bucket Tool
問題文はこちら
条件より、同じ色で塗られている区間がどこかで別の色に塗られて分けられる、みたいな場面は考えなくて良いことがわかります。
したがって、問題を解くにはある区間に隣接するマス、塗られている色、各色の個数がわかっていれば十分です。
色と個数は配列で持てばいいので問題となるのは隣接するマスについてですが、色の更新に対して区間全体に処理していては実行時間制限に間に合わないです。したがって、UnionFindなどを使って代表となるマスを決めておけばそのマスに対してのみ区間が隣接するマスを記録すれば良いことになります。
これで本問題を解きました。
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[] count = new int[N+1];
int[] color = new int[N+1];
int[] left = new int[N+1];
int[] right = new int[N+1];
UnionFind uf = new UnionFind(N+1);
for(int i=1;i<=N;i++){
count[i] = 1;
color[i] = i;
left[i] = i;
right[i] = i;
}
int Q = sc.nextInt();
while(Q-->0){
int t = sc.nextInt();
if(t==1){
int x = uf.root(sc.nextInt());
int c = sc.nextInt();
count[color[x]] -= uf.size(x);
color[x] = c;
count[c] += uf.size(x);
int l = left[x];
int r = right[x];
if(1<l&&color[uf.root(l-1)]==c){
int temp = left[uf.root(l-1)];
uf.unite(l-1,x);
x = uf.root(x);
l = temp;
}
if(r<N&&color[uf.root(r+1)]==c){
int temp = right[uf.root(r+1)];
uf.unite(x,r+1);
x = uf.root(x);
r = temp;
}
left[x] = l;
right[x] = r;
}
else{
int c = sc.nextInt();
out.println(count[c]);
}
}
out.close();
}
}
F - Exchange Game
問題文はこちら
高橋君、青木君、場の三か所に最大$12$枚のカードを$0$枚以上振り分けると考えると、状態として考えられる通り数は$3^{N+M+L} \le 531441$通りです。
したがって、愚直に全通り調べても適切にメモ化処理をしてあげれば十分高速に解を求めることができます。
メモ化の方法はいろいろあるかと思いますが、今回は簡便な方法の一つとして状態をそのまま文字列にしてそれをkeyとしたHashMapで管理してみました。
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);
public static void main(String[] args){
int N = sc.nextInt();
int M = sc.nextInt();
int L = sc.nextInt();
ArrayList<Integer> A = new ArrayList<>();
while(N-->0)
A.add(sc.nextInt());
ArrayList<Integer> B = new ArrayList<>();
while(M-->0)
B.add(sc.nextInt());
ArrayList<Integer> C = new ArrayList<>();
while(L-->0)
C.add(sc.nextInt());
Collections.sort(A);
Collections.sort(B);
Collections.sort(C);
out.println(dfs(false,A,B,C)?"Takahashi":"Aoki");
out.close();
}
private static final HashMap<String,Boolean> memo = new HashMap<>();
private static final boolean dfs(boolean flag,ArrayList<Integer> A,ArrayList<Integer> B,ArrayList<Integer> C){
String key = A.toString();
key += B.toString();
key += C.toString();
key += flag;
if(memo.containsKey(key))
return memo.get(key);
if(flag){
for(int i=0;i<B.size();i++){
for(int j=0;j<C.size();j++){
if(B.get(i)>C.get(j)){
Integer tempB = B.get(i);
Integer tempC = C.get(j);
B.set(i,tempC);
C.set(j,tempB);
Collections.sort(B);
Collections.sort(C);
boolean ans = !dfs(false,A,B,C);
B.remove(tempC);
C.remove(tempB);
B.add(tempB);
C.add(tempC);
Collections.sort(B);
Collections.sort(C);
if(ans){
memo.put(key,false);
return false;
}
}
Integer tempB = B.get(i);
B.remove(i);
C.add(tempB);
Collections.sort(C);
boolean ans = !dfs(false,A,B,C);
B.add(tempB);
C.remove(tempB);
Collections.sort(B);
if(ans){
memo.put(key,false);
return false;
}
}
}
}
else{
for(int i=0;i<A.size();i++){
for(int j=0;j<C.size();j++){
if(A.get(i)>C.get(j)){
Integer tempA = A.get(i);
Integer tempC = C.get(j);
A.set(i,tempC);
C.set(j,tempA);
Collections.sort(A);
Collections.sort(C);
boolean ans = dfs(true,A,B,C);
A.remove(tempC);
C.remove(tempA);
A.add(tempA);
C.add(tempC);
Collections.sort(A);
Collections.sort(C);
if(ans){
memo.put(key,true);
return true;
}
}
Integer tempA = A.get(i);
A.remove(i);
C.add(tempA);
Collections.sort(C);
boolean ans = dfs(true,A,B,C);
A.add(tempA);
C.remove(tempA);
Collections.sort(A);
if(ans){
memo.put(key,true);
return true;
}
}
}
}
memo.put(key,flag);
return flag;
}
}
感想
A,B:易しい
C:めんどい…
D:気づけば易しい
E:Eにしては易しめ？
F:通り数さえ気づけばサクッといけた
って感じでした。
易しめのコンテストだったからか、Fまで解いてもあんまりレート上がらなかったなぁ…。