結果
| 問題 | No.3587 Too Good to Swap |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-07-11 08:01:45 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 146 ms / 2,000 ms |
| + 613µs | |
| コード長 | 15,753 bytes |
| 記録 | |
| コンパイル時間 | 3,662 ms |
| コンパイル使用メモリ | 107,960 KB |
| 実行使用メモリ | 47,352 KB |
| 最終ジャッジ日時 | 2026-07-11 08:01:55 |
| 合計ジャッジ時間 | 9,192 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 49 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Random;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
// new Main().test();
pw.flush();
}
void run() {
ImplicitDigraph<int[]> g = new ImplicitDigraph<int[]>() {
// 0112を禁止
@Override
public Iterable<int[]> nextStates(int[] v) {
ArrayList<int[]> list = new ArrayList<>();
for (int i = 0; i < (v.length - 1); i++) {
if (v[i] == v[i + 1]) {
continue;
}
int[] u = v.clone();
{
var tmp = u[i];
u[i] = u[i + 1];
u[i + 1] = tmp;
}
if (check(u)) {
list.add(u);
}
}
return list;
}
boolean check(int[] v) {
for (int i = 0; (i + 3) < v.length; i++) {
if ((((v[i] == 0) && (v[i + 1] == 1)) && (v[i + 2] == 1)) && (v[i + 3] == 2)) {
return false;
}
}
return true;
}
};
int Q = sc.nextInt();
for (int TEST = 0; TEST < Q; TEST++) {
char[] S = sc.next().toCharArray();
char[] T = sc.next().toCharArray();
var A = f(S);
var B = f(T);
pw.printlnYesNo(solve(A, B));
}
// 11201
// 11021
// 10121
// 10211
// 01211
// 01121
// for (int T = 0; T < 10000; T++) {
// int n=7;
// int[]a=ArrayUtils.randomIntArray(0, 3, n);
// int[]b=ArrayUtils.randomIntArray(0, 3, n);
// if(!check(a)||!check(b))continue;
// boolean ans=solve(a.clone(), b.clone());
// boolean naive=g.onPath(a.clone(), b.clone());
// if(ans != naive) {
// tr(a, b);
// tr((int[])g.reachables(a).fold((U, V) -> Arrays.compare(U, V) < 0 ? U : V));
// tr((int[])g.reachables(b).fold((U, V) -> Arrays.compare(U, V) < 0 ? U : V));
// tr("ans,naive",ans, naive);
// var path=g.path(a, b);
// for (var v : path) {
// tr("v",v);
// }
// throw new AssertionError();
// /11221
// }
// [0,1][1][1,2] と分けられる
//
// int LEN=8;
// OpenHashSet<int[]>set=new OpenHashSet<int[]>();
// for (var A : Itertools.product(IntStream.range(0, 3).toArray(), LEN)) {
// boolean f=false;
// for (var a : Itertools.permutations(A.clone())) {
// if(!check(a))continue;
// var X=g.reachables(a.clone());
// if(set.contains(a))continue;
// var min=a;
// for (var x : X) {
// set.add(x.clone());
// f=true;
// if(Arrays.compare(min, x) > 0) min=x;
// }
// tr(min);
// }
// if(f)System.out.println();
// }
}
boolean check(int[] v) {
for (int i = 0; (i + 3) < v.length; i++) {
if ((((v[i] == 0) && (v[i + 1] == 1)) && (v[i + 2] == 1)) && (v[i + 3] == 2)) {
return false;
}
}
return true;
}
int type(int[] S) {
int a = ArrayUtils.indexOf(S, 2);
int b = ArrayUtils.lastIndexOf(S, 0);
if (a < b) {
return 1;
}
for (int i = 0; (i + 1) < S.length; i++) {
if (S[i] == 0) {
int j = i;
while (((j + 1) < S.length) && (S[j + 1] == 1)) {
j++;
}
if ((((j + 1) < S.length) && ((j - i) >= 2)) && (S[j + 1] == 2)) {
return 0;
}
i = j;
}
}
return 1;
}
boolean solve(int[] S, int[] T) {
int[] cnt0 = new int[10];
int[] cnt1 = new int[10];
for (int v : S) {
cnt0[v]++;
}
for (int v : T) {
cnt1[v]++;
}
if (!Arrays.equals(cnt0, cnt1)) {
return false;
}
if (((cnt0[0] == 0) || (cnt0[1] <= 1)) || (cnt0[2] == 0)) {
return true;
}
return type(S) == type(T);
}
int[] f(char[] a) {
int[] ret = new int[a.length];
for (int i = 0; i < a.length; i++) {
if (a[i] == 'g') {
ret[i] = 0;
}
if (a[i] == 'o') {
ret[i] = 1;
}
if (a[i] == 'd') {
ret[i] = 2;
}
}
return ret;
}
}
class ArrayUtils {
/**
* a[i]=vとなる最初のindexを返す。存在しないときは-1を返す。
*
* @param v
* @param a
* @return */
public static int indexOf(int[] a, int v) {
int i = 0;
while ((i < a.length) && (a[i] != v)) {
++i;
}
if (i == a.length) {
return -1;
}
return i;
}
/**
* a[i]=vとなる最後のindexを返す。存在しないときは-1を返す。
*
* @param v
* @param a
* @return */
public static int lastIndexOf(int[] a, int v) {
int i = a.length - 1;
while ((i >= 0) && (a[i] != v)) {
--i;
}
return i;
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public String next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
}
class Hash {
public interface Strategy<K> {
int hashCode(K o);
boolean equals(K a, K b);
}
public static <K> Strategy<K> defaultStrategy() {
return new Strategy<K>() {
@Override
public int hashCode(K o) {
if (o instanceof int[]) {
return Arrays.hashCode(((int[]) (o)));
}
if (o instanceof long[]) {
return Arrays.hashCode(((long[]) (o)));
}
if (o instanceof Long x) {
x ^= x >>> 33;
x *= 0xff51afd7ed558ccdL;
x ^= x >>> 33;
x *= 0xc4ceb9fe1a85ec53L;
x ^= x >>> 33;
return x.intValue();
}
return o.hashCode();
}
@Override
public boolean equals(K a, K b) {
if ((a instanceof int[]) && (b instanceof int[])) {
return Arrays.equals(((int[]) (a)), ((int[]) (b)));
}
if ((a instanceof long[]) && (b instanceof long[])) {
return Arrays.equals(((long[]) (a)), ((long[]) (b)));
}
return a.equals(b);
}
};
}
}
/**
* 暗黙的に定義された有向グラフを扱うための抽象クラス。
*
* <p>頂点集合が膨大または未知であり、隣接リストが動的に生成される場合に使用する。
* 到達可能な範囲の探索や、各種グラフアルゴリズムをサポートする。</p>
*
* @param <V>
* 頂点（状態）の型。{@code equals} と {@code hashCode} が適切に実装されている必要がある。
*/
abstract class ImplicitDigraph<V> {
/**
* ハッシュ戦略。
*/
protected final Hash.Strategy<V> strategy;
/**
* デフォルトのハッシュ戦略を使用するコンストラクタ。
*/
protected ImplicitDigraph() {
this(Hash.defaultStrategy());
}
/**
* 指定されたハッシュ戦略を使用するコンストラクタ。
*
* @param strategy
* ハッシュ戦略
*/
protected ImplicitDigraph(Hash.Strategy<V> strategy) {
this.strategy = strategy;
}
/**
* 指定された頂点から遷移可能な次の頂点の集合を返す。
*
* @param v
* 現在の頂点
* @return 次の頂点のイテラブル
*/
public abstract Iterable<V> nextStates(V v);
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
public void printlnYesNo(boolean flag) {
println(flag ? "Yes" : "No");
}
}
// --- Original Code ---
// import java.io.IOException;
// import java.util.ArrayList;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.collections.IntArrayList;
// import library.util.graph.ImplicitDigraph;
//
// public class Main {
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// // new Main().test();
// pw.flush();
// MergeFiles.export();
// }
//
// void run() {
// ImplicitDigraph<int[]>g=new ImplicitDigraph<int[]>() {
// //0112を禁止
// @Override
// public Iterable<int[]> nextStates(int[] v) {
// ArrayList<int[]>list=new ArrayList<>();
// for (int i = 0; i < v.length-1; i++) {
// if(v[i]==v[i+1])continue;
// int[]u=v.clone();
// {
// var tmp = u[i];
// u[i] = u[i+1];
// u[i+1] = tmp;
// }
// if (check(u)) list.add(u);
// }
// return list;
// }
//
// boolean check(int[] v) {
// for (int i = 0; i+3 < v.length; i++) {
// if(v[i]==0&&v[i+1]==1&&v[i+2]==1&&v[i+3]==2) return false;
// }
// return true;
// }
// };
// int Q=sc.nextInt();
// for (int TEST = 0; TEST < Q; TEST++) {
// char[]S=sc.next().toCharArray();
// char[]T=sc.next().toCharArray();
// var A=f(S);
// var B=f(T);
// pw.printlnYesNo(solve(A, B));
// }
// //11201
// //11021
// //10121
// //10211
// //01211
// //01121
//
// // for (int T = 0; T < 10000; T++) {
// // int n=7;
// // int[]a=ArrayUtils.randomIntArray(0, 3, n);
// // int[]b=ArrayUtils.randomIntArray(0, 3, n);
// // if(!check(a)||!check(b))continue;
// // boolean ans=solve(a.clone(), b.clone());
// // boolean naive=g.onPath(a.clone(), b.clone());
// // if(ans != naive) {
// // tr(a, b);
// // tr((int[])g.reachables(a).fold((U, V) -> Arrays.compare(U, V) < 0 ? U : V));
// // tr((int[])g.reachables(b).fold((U, V) -> Arrays.compare(U, V) < 0 ? U : V));
// // tr("ans,naive",ans, naive);
// // var path=g.path(a, b);
// // for (var v : path) {
// // tr("v",v);
// // }
// // throw new AssertionError();
// // }//11221
// // }
//
// // [0,1][1][1,2] と分けられる
// //
//
// // int LEN=8;
// // OpenHashSet<int[]>set=new OpenHashSet<int[]>();
// // for (var A : Itertools.product(IntStream.range(0, 3).toArray(), LEN)) {
// // boolean f=false;
// // for (var a : Itertools.permutations(A.clone())) {
// // if(!check(a))continue;
// // var X=g.reachables(a.clone());
// // if(set.contains(a))continue;
// // var min=a;
// // for (var x : X) {
// // set.add(x.clone());
// // f=true;
// // if(Arrays.compare(min, x) > 0) min=x;
// // }
// // tr(min);
// // }
// // if(f)System.out.println();
// // }
// }
//
// boolean check(int[] v) {
// for (int i = 0; i+3 < v.length; i++) {
// if(v[i]==0&&v[i+1]==1&&v[i+2]==1&&v[i+3]==2) return false;
// }
// return true;
// }
//
// int type(int[]S) {
// int a=ArrayUtils.indexOf(S, 2);
// int b=ArrayUtils.lastIndexOf(S, 0);
// if (a < b) return 1;
// for (int i = 0; i+1 < S.length; i++) {
// if(S[i]==0) {
// int j=i;
// while(j+1<S.length && S[j+1]==1)j++;
// if(j+1<S.length && j-i>=2 && S[j+1]==2) return 0;
// i=j;
// }
// }
// return 1;
// }
//
// boolean solve(int[]S, int[] T) {
// int[]cnt0=new int[10];
// int[]cnt1=new int[10];
// for (int v : S)cnt0[v]++;
// for (int v : T)cnt1[v]++;
// if(!Arrays.equals(cnt0, cnt1))return false;
// if(cnt0[0]==0||cnt0[1]<=1||cnt0[2]==0) return true;
// return type(S)==type(T);
// }
//
// int[] f(char[] a) {
// int[]ret=new int[a.length];
// for (int i = 0; i < a.length; i++) {
// if(a[i]=='g')ret[i]=0;
// if(a[i]=='o')ret[i]=1;
// if(a[i]=='d')ret[i]=2;
// }
// return ret;
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//