結果
| 問題 | No.3428 Palindromic Path (Easy) |
| コンテスト | |
| ユーザー |
 tenten
|
| 提出日時 | 2026-01-21 13:42:42 |
| 言語 | Java (openjdk 25.0.1) |
| 結果 |
AC
|
| 実行時間 | 54 ms / 2,000 ms |
| コード長 | 6,204 bytes |
| 記録 | |
| コンパイル時間 | 2,789 ms |
| コンパイル使用メモリ | 90,080 KB |
| 実行使用メモリ | 44,516 KB |
| 最終ジャッジ日時 | 2026-01-21 13:42:47 |
| 合計ジャッジ時間 | 4,182 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 6 |
ソースコード
import java.io.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;
public class Main {
static final int MOD = 998244353;
public static void main(String[] args) throws Exception {
FastScanner sc = new FastScanner();
int n = sc.nextInt();
StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) {
s.append(sc.next());
}
char[] base = s.toString().toCharArray();
if (base[0] != base[n * n - 1]) {
System.out.println(0);
return;
}
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < n * 2 - 1; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < n * n; i++) {
list.get((i % n) + (i / n)).add(i);
}
Map<Unit, Integer> counts = new HashMap<>();
counts.put(new Unit(0, n * n - 1), 1);
for (int i = 1; i < n - 1; i++) {
int op = n * 2 - 2 - i;
for (int x : list.get(i)) {
for (int y : list.get(op)) {
if (base[x] != base[y]) {
continue;
}
int current = 0;
if (x / n > 0) {
if (y / n < n - 1) {
current += counts.getOrDefault(new Unit(x - n, y + n), 0);
current %= MOD;
}
if (y % n < n - 1) {
current += counts.getOrDefault(new Unit(x - n, y + 1), 0);
current %= MOD;
}
}
if (x % n > 0) {
if (y / n < n - 1) {
current += counts.getOrDefault(new Unit(x - 1, y + n), 0);
current %= MOD;
}
if (y % n < n - 1) {
current += counts.getOrDefault(new Unit(x - 1, y + 1), 0);
current %= MOD;
}
}
if (current > 0) {
counts.put(new Unit(x, y), current);
}
}
}
}
int ans = 0;
for (int x : list.get(n - 1)) {
if (x / n > 0) {
if (x / n < n - 1) {
ans += counts.getOrDefault(new Unit(x - n, x + n), 0);
ans %= MOD;
}
if (x % n < n - 1) {
ans += counts.getOrDefault(new Unit(x - n, x + 1), 0);
ans %= MOD;
}
}
if (x % n > 0) {
if (x / n < n - 1) {
ans += counts.getOrDefault(new Unit(x - 1, x + n), 0);
ans %= MOD;
}
if (x % n < n - 1) {
ans += counts.getOrDefault(new Unit(x - 1, x + 1), 0);
ans %= MOD;
}
}
}
System.out.println(ans);
}
static class Unit {
int left;
int right;
public Unit(int left, int right) {
this.left = left;
this.right = right;
}
public int hashCode() {
return left * 50000 + right;
}
public boolean equals(Object o) {
return hashCode() == o.hashCode();
}
public String toString() {
return left + ":" + right;
}
}
}
class FastScanner {
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
private static final int BUFFER_SIZE = 1 << 16; // 65,536 バイト
public FastScanner() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
private byte read() {
try {
if (bufferPointer == bytesRead) {
bytesRead = din.read(buffer, 0, BUFFER_SIZE);
if (bytesRead == -1) return -1;
bufferPointer = 0;
}
return buffer[bufferPointer++];
} catch (IOException e) {
throw new RuntimeException(e);
}
}
public String next() {
byte b = read();
// 空白文字を読み飛ばす
while (isSpaceChar(b)) {
b = read();
}
StringBuilder sb = new StringBuilder();
while (!isSpaceChar(b)) {
sb.append((char) b);
b = read();
}
return sb.toString();
}
public int nextInt() {
int ret = 0;
byte c = read();
while (isSpaceChar(c)) c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10 + c - '0';
c = read();
} while (!isSpaceChar(c));
return neg ? -ret : ret;
}
public long nextLong() {
long ret = 0;
byte c = read();
while (isSpaceChar(c)) c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10L + c - '0';
c = read();
} while (!isSpaceChar(c));
return neg ? -ret : ret;
}
public double nextDouble() {
double ret = 0, div = 1;
byte c = read();
while (isSpaceChar(c)) c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10 + c - '0';
c = read();
} while (!isSpaceChar(c) && c != '.');
if (c == '.') {
while (!isSpaceChar(c = read())) {
ret += (c - '0') / (div *= 10);
}
}
return neg ? -ret : ret;
}
private boolean isSpaceChar(byte c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public void close() {
try {
if (din != null) din.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}