#852911 (Java21) No.2254 Reverse Only

提出ソース

結果

問題	No.2254 Reverse Only
ユーザー	CuriousFairy315
提出日時	2023-03-25 00:09:28
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,427 ms / 2,000 ms
コード長	16,405 bytes
コンパイル時間	3,420 ms
コンパイル使用メモリ	96,500 KB
実行使用メモリ	88,084 KB
最終ジャッジ日時	2024-09-18 17:48:58
合計ジャッジ時間	46,547 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	153 ms 41,872 KB
testcase_01	AC	136 ms 41,428 KB
testcase_02	AC	136 ms 41,296 KB
testcase_03	AC	135 ms 41,272 KB
testcase_04	AC	135 ms 41,352 KB
testcase_05	AC	134 ms 41,368 KB
testcase_06	AC	136 ms 41,472 KB
testcase_07	AC	136 ms 41,112 KB
testcase_08	AC	1,310 ms 60,088 KB
testcase_09	AC	1,427 ms 80,988 KB
testcase_10	AC	1,127 ms 59,776 KB
testcase_11	AC	1,349 ms 60,020 KB
testcase_12	AC	1,264 ms 60,052 KB
testcase_13	AC	1,181 ms 60,008 KB
testcase_14	AC	1,195 ms 59,996 KB
testcase_15	AC	1,191 ms 59,824 KB
testcase_16	AC	1,378 ms 72,676 KB
testcase_17	AC	1,289 ms 71,604 KB
testcase_18	AC	1,343 ms 60,004 KB
testcase_19	AC	1,185 ms 59,924 KB
testcase_20	AC	1,277 ms 85,920 KB
testcase_21	AC	1,320 ms 88,084 KB
testcase_22	AC	1,334 ms 80,832 KB
testcase_23	AC	1,363 ms 87,336 KB
testcase_24	AC	1,111 ms 79,476 KB
testcase_25	AC	1,268 ms 80,024 KB
testcase_26	AC	1,225 ms 79,224 KB
testcase_27	AC	267 ms 46,836 KB
testcase_28	AC	675 ms 48,824 KB
testcase_29	AC	847 ms 52,620 KB
testcase_30	AC	855 ms 53,736 KB
testcase_31	AC	644 ms 48,512 KB
testcase_32	AC	632 ms 48,484 KB
testcase_33	AC	507 ms 48,184 KB
testcase_34	AC	846 ms 54,720 KB
testcase_35	AC	716 ms 50,984 KB
testcase_36	AC	1,176 ms 59,660 KB
testcase_37	AC	1,256 ms 59,520 KB
testcase_38	AC	613 ms 48,256 KB
testcase_39	AC	1,203 ms 59,224 KB
testcase_40	AC	294 ms 47,376 KB
testcase_41	AC	781 ms 48,936 KB
testcase_42	AC	614 ms 48,496 KB
testcase_43	AC	931 ms 57,176 KB
testcase_44	AC	1,175 ms 60,132 KB
testcase_45	AC	1,007 ms 57,656 KB
testcase_46	AC	274 ms 46,436 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import static java.lang.System.err;
import java.util.Arrays;
import java.util.Random;
import java.util.function.LongBinaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.IntStream;

public class Main {
	public static void main(String[] args) {
		java.io.PrintWriter out = new java.io.PrintWriter(System.out);
		new Main(out);
		out.flush();
		err.flush();
	}

	/*
	 * 1. k=Nのとき: 2択
	 * 2. k<Nのとき: 実は任意？
	 *
	 * k=N-1のとき、cyclic shiftとそのreverseしかできなかったわ
	 * ……え、面倒な
	 * AとBが(cyclic shiftで)一致するか、は、Aの繰り返しにBが部分文字列として含まれるか
	 *
	 */
	public Main(java.io.PrintWriter out) {
		try (java.util.Scanner sc = new java.util.Scanner(System.in)) {
			int N = sc.nextInt(), k = sc.nextInt();
			int[] A = new int[N], B = new int[N];
			for (int i = 0; i < N; ++i) A[i] = sc.nextInt();
			for (int i = 0; i < N; ++i) B[i] = sc.nextInt();
			if (N < k) {
				out.println(Arrays.equals(A, B) ? "Yes" : "No");
			} else if (N == k) {
				boolean yes = Arrays.equals(A, B);
				for (int i = 0; i < N >> 1; ++i) {
					A[i] ^= A[N - i - 1];
					A[N - i - 1] ^= A[i];
					A[i] ^= A[N - i - 1];
				}
				yes |= Arrays.equals(A, B);
				out.println(yes ? "Yes" : "No");
			} else if (N == k + 1) {
				int[] A2 = Arrays.copyOf(A, A.length * 2);
				System.arraycopy(A, 0, A2, A.length, A.length);
				RollingHash BHash = RollingHash.create(B);
				long base = BHash.base();
				RollingHash A2Hash = RollingHash.create(A2, base);
				for (int i = 0; i < A.length; ++i) {
					if (A2Hash.subList(i, i + A.length).equals(BHash)) {
						out.println("Yes");
						return;
					}
				}
				for (int i = 0; i < N >> 1; ++i) {
					A[i] ^= A[N - i - 1];
					A[N - i - 1] ^= A[i];
					A[i] ^= A[N - i - 1];
				}
				A2 = Arrays.copyOf(A, A.length * 2);
				System.arraycopy(A, 0, A2, A.length, A.length);
				A2Hash = RollingHash.create(A2, base);
				for (int i = 0; i < A.length; ++i) {
					if (A2Hash.subList(i, i + A.length).equals(BHash)) {
						out.println("Yes");
						return;
					}
				}
				out.println("No");
			} else {
				Arrays.sort(A);
				Arrays.sort(B);
				out.println(Arrays.equals(A, B) ? "Yes" : "No");
			}
		}
	}
}

/**
 * 数列に対するローリングハッシュを求めます。
 * <p>
 * ローリングハッシュとは、基数{@code base}と法{@code mod}が与えられたとき、数列{@code S}に対して以下のように定義される値です。
 * <pre>hash = sum[i=1, |S|]S_i * base^(i-1) (modulo mod)</pre>
 * これは、数列{@code S}を{@code base}進数で表して{@code mod}で余りを取ったものと考えることができます。
 * </p>
 * @author 31536000
 *
 */
interface RollingHash extends Comparable<RollingHash> {
	/**
	 * このローリングハッシュで用いられている基数を返します。
	 * @return 基数
	 */
	long base();

	/**
	 * このローリングハッシュで用いられている法を返します。
	 * @return 法
	 */
	long mod();

	/**
	 * この数列全体のハッシュを返します。
	 * @return 数列のハッシュ値
	 */
	long hash();

	/**
	 * この数列の先頭からindex番目までのハッシュ値を返します。
	 * @param index ハッシュ値を求めたい区間
	 * @return 数列の先頭からn番目までのハッシュ値
	 * @exception IllegalArgumentException {@code 0 > index || index > size()}
	 */
	default long hash(int index) {
		return hash(0, index);
	}

	/**
	 * この数列のfromIndex番目からtoIndex番目までのハッシュ値を返します。
	 * @param fromIndex ハッシュ値を求める区間の左端(これを含む)
	 * @param toIndex ハッシュ値を求める区間の右端(これを含まない)
	 * @return 数列のfromIndex番目からtoIndex番目までのハッシュ値
	 * @exception IllegalArgumentException {@code 0 > fromIndex || fromIndex > toIndex || toIndex > size()}
	 */
	default long hash(int fromIndex, int toIndex) {
		if (0 > fromIndex || fromIndex > toIndex || toIndex > size())
			throw new IllegalArgumentException("[" + fromIndex + ", " + toIndex + ") is illegal range");
		return subList(fromIndex, toIndex).hash();
	}

	/**
	 * この数列の先頭からindex番目までのハッシュ値を返します。
	 * @param index ハッシュ値を求めたい区間
	 * @return 数列の先頭からn番目までのハッシュ値
	 * @exception IllegalArgumentException {@code 0 > index || index > size()}
	 */
	default RollingHash subList(int index) {
		return subList(0, index);
	}

	/**
	 * この数列のfromIndex番目からtoIndex番目までのハッシュ値を返します。
	 * @param fromIndex ハッシュ値を求める区間の左端(これを含む)
	 * @param toIndex ハッシュ値を求める区間の右端(これを含まない)
	 * @return 数列のfromIndex番目からtoIndex番目までのハッシュ値
	 * @exception IllegalArgumentException {@code 0 > fromIndex || fromIndex > toIndex || toIndex > size()}
	 */
	RollingHash subList(int fromIndex, int toIndex);

	/**
	 * 二つの数列をこの順に結合したときのハッシュ値を返します。
	 * @param l 左側の数列
	 * @param r 右側の数列
	 * @return 数列{@code l}, {@code r}をこの順に結合したときのハッシュ値
	 * @exception IllegalArgumentException {@code l.base() != r.base() || l.mod() != r.mod()}
	 * @exception NullPointerException {@code l == null || r == null}
	 */
	RollingHash merge(RollingHash l, RollingHash r);

	/**
	 * この数列の長さを返します。
	 * @return 数列長
	 */
	int size();

	/**
	 * 二つの数列の最長共通接頭辞の長さを求めます。
	 * @param l 数列
	 * @param r 数列
	 * @return {@code l}と{@code r}の最長共通接頭辞
	 * @exception IllegalArgumentException {@code l.base() != r.base() || l.mod() != r.mod()}
	 * @exception NullPointerException {@code l == null || r == null}
	 */
	static int lcp(RollingHash l, RollingHash r) {
		if (l == null || r == null) throw new NullPointerException();
		if (l.base() != r.base() || l.mod() != r.mod()) throw new IllegalArgumentException();
		int min = 0, max = Math.min(l.size(), r.size()) + 1;
		while (max - min > 1) {
			int mid = min + (max - min >> 1);
			if (l.hash(mid) == r.hash(mid)) min = mid;
			else max = mid;
		}
		return min;
	}

	/**
	 * 二つの数列の最長共通接頭辞の長さを求めます。
	 * @param S 数列
	 * @return 自身と{@code S}の最長共通接頭辞
	 * @exception IllegalArgumentException {@code base() != S.base() || mod() != S.mod()}
	 * @exception NullPointerException {@code S == null}
	 */
	default int lcp(RollingHash S) {
		return lcp(this, S);
	}

	@Override
	default int compareTo(RollingHash o) {
		int lcp = lcp(this, o);
		if (size() == lcp) { return o.size() == lcp ? 0 : -1; }
		if (o.size() == lcp) return 1;
		return Long.compare(hash(lcp, lcp + 1), o.hash(lcp, lcp + 1));
	}

	/**
	 * この数列の中に{@code s}を連続部分列として含む場合、その先頭のインデックスを返します。そのようなものが無い場合、{@code -1}を返します。
	 * @param s 調べる数列
	 * @return {@code s}を連続部分列として含む場合はその先頭のインデックス、無ければ{@code -1}
	 * @exception IllegalArgumentException {@code base() != s.base() || mod() != s.mod()}
	 * @exception NullPointerException {@code s == null}
	 */
	default int find(RollingHash s) {
		if (s == null) throw new NullPointerException();
		if (base() != s.base() || mod() != s.mod()) throw new IllegalArgumentException();
		int size = s.size();
		long hash = s.hash();
		for (int i = 0, l = size() - size; i <= l; ++i) {
			if (hash(i, i + size) == hash) return i;
		}
		return -1;
	}

	/**
	 * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 各要素が0以上2^{61}-1未満の数列
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(long[] S) {
		Random rnd = new Random();
		long MOD = (1L << 61) - 1;
		long MASK0 = (1L << 30) - 1;
		long MASK1 = (1L << 31) - 1;
		LongUnaryOperator mod = x -> {
			final long xu = x >>> 61;
			final long xd = x & MOD;
			long res = xu + xd;
			if (res >= MOD) res -= MOD;
			return res;
		};
		LongBinaryOperator mul = (a, b) -> {
			final long au = a >>> 31;
			final long ad = a & MASK1;
			final long bu = b >>> 31;
			final long bd = b & MASK1;
			final long mid = ad * bu + au * bd;
			final long midu = mid >>> 30;
			final long midd = mid & MASK0;
			return mod.applyAsLong((au * bu << 1) + midu + (midd << 31) + ad * bd);
		};
		LongBinaryOperator gcd = (a, b) -> {
			while (a != 0) if ((b %= a) != 0) a %= b;
			else return a;
			return b;
		};
		while (true) {
			long e = mod.applyAsLong(rnd.nextLong());
			if (gcd.applyAsLong(e, MOD - 1) == 1) {
				long base = 1;
				for (long x = 37; e > 0; e >>= 1, x = mul.applyAsLong(x, x))
					if ((e & 1) != 0) base = mul.applyAsLong(base, x);
				return create(S, base);
			}
		}
	}

	/**
	 * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 数列
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(int[] S) {
		return create(Arrays.stream(S).mapToLong(i -> i).toArray());
	}

	/**
	 * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 文字列
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(char[] S) {
		return create(IntStream.range(0, S.length).mapToLong(i -> S[i]).toArray());
	}

	/**
	 * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 文字列
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(String S) {
		return create(IntStream.range(0, S.length()).mapToLong(S::charAt).toArray());
	}

	/**
	 * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 各要素が0以上2^{61}-1未満の数列
	 * @param base 基数
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(long[] S, long base) {
		long MOD = (1L << 61) - 1;

		class DefaultRollingHash implements RollingHash {
			final long[] hash;
			final long[] pow;
			static final long MASK0 = (1L << 30) - 1;
			static final long MASK1 = (1L << 31) - 1;
			final int len = S.length;

			long mod(final long x) {
				final long xu = x >>> 61;
				final long xd = x & MOD;
				long res = xu + xd;
				if (res >= MOD) res -= MOD;
				return res;
			}

			long mul(final long a, final long b) {
				final long au = a >>> 31;
				final long ad = a & MASK1;
				final long bu = b >>> 31;
				final long bd = b & MASK1;
				final long mid = ad * bu + au * bd;
				final long midu = mid >>> 30;
				final long midd = mid & MASK0;
				return mod((au * bu << 1) + midu + (midd << 31) + ad * bd);
			}

			DefaultRollingHash() {
				hash = new long[S.length + 1];
				pow = new long[S.length + 1];
				pow[0] = 1;
				for (int i = 0; i < S.length; ++i) {
					hash[i + 1] = mod(mul(hash[i], base) + S[i]);
					pow[i + 1] = mul(pow[i], base);
				}
			}

			@Override
			public long base() {
				return base;
			}

			@Override
			public long mod() {
				return MOD;
			}

			@Override
			public long hash() {
				return hash[hash.length - 1];
			}

			@Override
			public long hash(int fromIndex, int toIndex) {
				return mod(hash[toIndex] - mul(hash[fromIndex], pow[toIndex - fromIndex]) + MOD);
			}

			@Override
			public RollingHash subList(int fromIndex, int toIndex) {
				class SubRollingHash implements RollingHash {
					final int l, r;
					final long hash;

					SubRollingHash(int l, int r) {
						this.l = l;
						this.r = r;
						hash = DefaultRollingHash.this.hash(l, r);
					}

					private void check(int from, int to) {
						if (0 > from || from > to || to > r - l) throw new IllegalArgumentException(
								"[" + from + ", " + to + ") is out of range: [0, " + (r - l) + ")");
					}

					@Override
					public long base() {
						return base;
					}

					@Override
					public long mod() {
						return MOD;
					}

					@Override
					public long hash() {
						return hash;
					}

					@Override
					public long hash(int fromIndex, int toIndex) {
						check(fromIndex, toIndex);
						return DefaultRollingHash.this.hash(l + fromIndex, l + toIndex);
					}

					@Override
					public RollingHash subList(int fromIndex, int toIndex) {
						check(fromIndex, toIndex);
						return new SubRollingHash(l + fromIndex, l + toIndex);
					}

					@Override
					public RollingHash merge(RollingHash l, RollingHash r) {
						return merge(l, r);
					}

					@Override
					public int size() {
						return r - l;
					}

					@Override
					public int hashCode() {
						return Long.hashCode(hash());
					}

					@Override
					public boolean equals(Object o) {
						if (o instanceof RollingHash) {
							RollingHash hash = (RollingHash) o;
							return hash() == hash.hash();
						}
						return false;
					}
				}
				return new SubRollingHash(fromIndex, toIndex);
			}

			@Override
			public RollingHash merge(RollingHash l, RollingHash r) {
				class MergeRollingHash implements RollingHash {

					final RollingHash l, r;
					final long hash;
					final int size;

					MergeRollingHash(RollingHash l, RollingHash r) {
						this.l = l;
						this.r = r;
						hash = DefaultRollingHash.this.mod(mul(l.hash(), pow[r.size()]) + r.hash());
						size = l.size() + r.size();
					}

					@Override
					public long base() {
						return base;
					}

					@Override
					public long mod() {
						return MOD;
					}

					@Override
					public long hash() {
						return hash;
					}

					@Override
					public RollingHash subList(int fromIndex, int toIndex) {
						if (0 > fromIndex || fromIndex > toIndex || toIndex > size())
							throw new IllegalArgumentException(
									"[" + fromIndex + ", " + toIndex + ") is out of range: [0, " + size() + ")");
						if (toIndex <= l.size()) return l.subList(fromIndex, toIndex);
						if (fromIndex >= l.size()) return r.subList(fromIndex - l.size(), toIndex - l.size());
						return merge(l.subList(fromIndex, l.size()), r.subList(0, toIndex - l.size()));
					}

					@Override
					public RollingHash merge(RollingHash l, RollingHash r) {
						return new MergeRollingHash(l, r);
					}

					@Override
					public int size() {
						return size;
					}

					@Override
					public int hashCode() {
						return Long.hashCode(hash());
					}

					@Override
					public boolean equals(Object o) {
						if (o instanceof RollingHash) {
							RollingHash hash = (RollingHash) o;
							return hash() == hash.hash();
						}
						return false;
					}
				}
				return new MergeRollingHash(l, r);
			}

			@Override
			public int size() {
				return len;
			}

			@Override
			public int hashCode() {
				return Long.hashCode(hash());
			}

			@Override
			public boolean equals(Object o) {
				if (o instanceof RollingHash) {
					RollingHash hash = (RollingHash) o;
					return hash() == hash.hash();
				}
				return false;
			}
		}
		return new DefaultRollingHash();
	}

	/**
	 * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 数列
	 * @param base 基数
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(int[] S, long base) {
		return create(Arrays.stream(S).mapToLong(i -> i).toArray(), base);
	}

	/**
	 * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 文字列
	 * @param base 基数
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(char[] S, long base) {
		return create(IntStream.range(0, S.length).mapToLong(i -> S[i]).toArray(), base);
	}

	/**
	 * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
	 * @param S 文字列
	 * @param base 基数
	 * @return {@code S}のローリングハッシュ
	 */
	static RollingHash create(String S, long base) {
		return create(IntStream.range(0, S.length()).mapToLong(S::charAt).toArray(), base);
	}
}

yukicoder

結果

テストケース

ソースコード