結果
| 問題 |
No.1405 ジグザグロボット
|
| コンテスト | |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2020-11-28 08:41:13 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 12,964 bytes |
| コンパイル時間 | 3,561 ms |
| コンパイル使用メモリ | 93,452 KB |
| 実行使用メモリ | 42,516 KB |
| 最終ジャッジ日時 | 2024-09-16 23:27:22 |
| 合計ジャッジ時間 | 14,685 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 1 RE * 34 |
ソースコード
import java.awt.Point;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.NoSuchElementException;
import java.util.TreeSet;
public class Main {
public static void main(final String[] args) {
new Main();
}
public Main() {
final InputChecker ic = new InputChecker(System.in);
final java.io.PrintWriter out = new java.io.PrintWriter(System.out);
solve(ic, out);
out.flush();
}
public void solve(final InputChecker ic, final java.io.PrintWriter out) {
final int N = ic.nextInt(1, 600);
ic.nextChar(' ');
final int X = ic.nextInt(0, N);
ic.nextChar(' ');
final int Y = ic.nextInt(0, N);
ic.readNewLine();
final CharSet query = new CharSet();
query.add('L', 'S', 'R');
final char[] S = ic.next(query).toCharArray();
if (S.length != N) throw new AssertionError();
ic.readNewLine();
ic.checkEOF();
Range[] range; // range[i]はy座標がiの時に左にl, 右にr動いて最終的に右にs動くことを示す
int up = 0, right = 0;
{
final ArrayList<Range> list = new ArrayList<>();
int l = 0, r = 0, s = 0, l2 = 0, i = 0;
for (final char c : S) {
if (c == 'S') {
list.add(new Range(l, s, r, l2, i + 1));
l = r = s = 0;
l2 = i + 1;
++ up;
} else if (c == 'L') {
-- s;
l = Math.max(l, -s);
} else if (c == 'R') {
++ s;
r = Math.max(r, s);
++ right;
} else throw new AssertionError();
++ i;
}
list.add(new Range(l, s, r, l2, i + 1));
range = list.toArray(new Range[0]);
}
if (up < Y || right < X) {
out.println(-1);
return;
}
final Range[][] merge = new Range[range.length][range.length + 1]; // merge[i][j]: y座標が[i, j)の区間を併合したときの合成区間
for (int i = 0;i < merge.length;++ i) {
final Range[] array = merge[i];
array[i] = new Range(0, 0, 0, N, N);
for (int j = i;j < merge.length;++ j)
array[j + 1] = new Range(Math.max(array[j].l, range[j].l - array[j].s), array[j].s + range[j].s, Math.max(array[j].r, range[j].r + array[j].s), Math.min(array[j].l2, range[j].l2), range[j].r2);
}
final int[][] dp = new int[Y + 2][range.length + 1]; // dp[i][j]: i個の区間を選び、使用した区間がj個の時の右へ移動できる最大
final int[][] restore = new int[Y + 2][range.length + 1]; // 復元
for (int i = 1;i < dp.length;++ i) {
final int[] last = dp[i - 1], now = dp[i];
Arrays.fill(now, Integer.MIN_VALUE);
final int[] res = restore[i];
for (int j = 1;j < now.length;++ j)
for (int k = j - 1;k >= 0;-- k)
if (now[j] <= last[k] + merge[k][j].l + merge[k][j].s) { // 左はせき止めるため
now[j] = last[k] + merge[k][j].l + merge[k][j].s;
res[j] = k;
}
}
int remain = dp[Y + 1][range.length] - X;
if (remain < 0) {
out.println(-1);
return;
}
final ArrayDeque<Range> move = new ArrayDeque<>(); // 併合区間
for (int i = Y + 1, j = range.length;i > 0;-- i) {
final int next = restore[i][j];
move.add(merge[next][j]);
j = next;
}
final ArrayList<Point> ans = new ArrayList<>(); // 置いた岩の情報
{
int x = 0; // 現在の侵入座標
for (int i = 0;i <= Y;++ i) {
final Range m = move.pollLast();
if (m.l + m.s <= remain) { // 移動しない
ans.add(new Point(x - 1, i));
ans.add(new Point(x + 1, i));
remain -= m.l + m.s;
} else if (remain == 0) {
ans.add(new Point(x - 1, i));
for (int j = 0;j < m.l + m.s;++ j) ans.add(new Point(x + j, i + 1));
x += m.l + m.s;
} else {
ans.add(new Point(x - 1, i));
for (int j = 0;j < m.l + m.s - remain;++ j) ans.add(new Point(x + j, i + 1));
{
int r = 0, s = 0;
for (int j = m.l2;j < m.r2;++ j) {
final char c = S[j];
if (c == 'L') {
-- s;
if (s <= 0) {
r = 0;
s = 0;
}
} else if (c == 'R') {
++ s;
r = Math.max(r, s);
}
}
r = Math.max(r, m.l + m.s);
ans.add(new Point(x + r + 1 - remain, i));
}
x += m.l + m.s - remain;
remain = 0;
}
}
for (int i = 0;i <= N;++ i) ans.add(new Point(i, Y + 1));
}
{
final TreeSet<Point> ans2 = new TreeSet<>((l, r) -> Integer.compare(l.x * 10000 + l.y, r.x * 10000 + r.y));
final TreeSet<Integer> set = new TreeSet<>();
for (final Point i : ans) set.add(i.x * 10000 + i.y);
int x = 0, y = 0;
for (final char c : S)
if (c == 'S') {
if (set.contains(x * 10000 + y + 1)) ans2.add(new Point(x, y + 1));
else ++ y;
} else if (c == 'L') {
if (set.contains((x - 1) * 10000 + y)) ans2.add(new Point(x - 1, y));
else -- x;
} else if (c == 'R') if (set.contains((x + 1) * 10000 + y)) ans2.add(new Point(x + 1, y));
else ++ x;
if (x != X || y != Y) throw new AssertionError();
out.println(ans2.size());
for (final Point p : ans2)
out.println(p.x + " " + p.y);
}
}
class Range {
final int l, s, r, l2, r2;
Range(final int L, final int S, final int R, final int L2, final int R2) {
l = L;
s = S;
r = R;
l2 = L2;
r2 = R2;
}
@Override
public String toString() {
return "[" + l2 + ", " + r2 + ") : " + "(" + l + "," + s + "," + r + ")";
}
}
public static int exponent10(final int n, final int e) {
return n * pow(10, e);
}
public static long exponent10L(final int n, final int e) {
return n * pow(10L, e);
}
public static int pow(final int a, int b) {
int ans = 1;
for (int mul = a;b > 0;b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static long pow(final long a, long b) {
long ans = 1;
for (long mul = a;b > 0;b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static class CharSet {
private final BitSet set = new BitSet(256);
public void add(final char... c) {
for (final char i : c) set.set(i);
}
public void add(final CharSet... s) {
for (final CharSet i : s) set.or(i.set);
}
public boolean contains(final char... c) {
for (final char i : c) if (!set.get(i)) return false;
return true;
}
public boolean contains(final String s) {
return contains(s.toCharArray());
}
private static final class Chars extends CharSet {
public Chars(final char... c) {
super.add(c);
}
public Chars(final CharSet... s) {
super.add(s);
}
@Override
public void add(final char... c) {
throw new UnsupportedOperationException();
}
@Override
public void add(final CharSet... s) {
throw new UnsupportedOperationException();
}
}
public static final CharSet NUMBER = new Chars('0','1','2','3','4','5','6','7','8','9');
public static final CharSet LOWER = new Chars('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');
public static final CharSet UPPER = new Chars('A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z');
public static final CharSet ALPHABET = new Chars(LOWER, UPPER);
}
public static class InputChecker {
private InputStream in;
private final byte[] buffer = new byte[1024];
private final byte[] undo = new byte[1024];
private int undoSize = 0;
private int read = 0;
private int length = 0;
public InputChecker(final InputStream in) {
this.in = in;
}
public final void setInputStream(final InputStream in) {
this.in = in;
}
public final void setInputStream(final File in) {
try {
this.in = new FileInputStream(in);
} catch (final FileNotFoundException e) {
e.printStackTrace();
}
}
private boolean hasNextByte() {
if (undoSize > 0) return true;
if (read < length) return true;
read = 0;
try {
length = in.read(buffer);
} catch (final IOException e) {
e.printStackTrace();
}
return length > 0;
}
private byte readByte() {
if (hasNextByte()) return undoSize > 0 ? undo[--undoSize] : buffer[read++];
throw new NoSuchElementException();
}
private void undo(final byte b) {
undo[undoSize ++] = b;
}
private void undo(final char c) {
if ((c & 0xFF80) == 0) {
undo((byte)c);
return;
}
undo((byte)(c & 0x3F | 0x80));
if ((c & 0xF800) == 0) undo((byte)(c >> 6 & 0x1F | 0xC0));
else {
undo((byte)(c >> 6 & 0x3F | 0x80));
undo((byte)(c >> 12 | 0xE0));
}
}
public final boolean hasNext() {
return hasNextByte();
}
public final char nextChar() {
final byte b = readByte();
if ((b & 0x80) == 0) return (char)b;
if ((b & 0x20) == 0) return (char)((b & 0x1F) << 6 | readByte() & 0x3F);
return (char)((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | readByte() & 0x3F);
}
public final char nextChar(final char estimate) {
final char c = nextChar();
if (estimate == c) return estimate;
undo(c);
throw new AssertionError();
}
public final char nextChar(final CharSet estimate) {
final char c = nextChar();
if (estimate.contains(c)) return c;
undo(c);
throw new AssertionError();
}
public final void readNewLine() {
char c = nextChar();
if (c == '\r') {
c = nextChar();
if (c != '\n') undo(c);
return;
} else if (c == '\n') return;
undo(c);
throw new AssertionError();
}
public final void checkEOF() {
if (hasNextByte()) throw new AssertionError();
}
public final String next(final CharSet contains) {
final StringBuilder sb = new StringBuilder();
try {
do {
final char c = nextChar();
if (!contains.contains(c)) {
undo(c);
return sb.toString();
}
sb.append(c);
} while(true);
} catch (final NoSuchElementException e) {
if (sb.length() <= 0) throw new AssertionError();
return sb.toString();
}
}
public final int nextInt() {
byte b = readByte();
int n = 0;
if (b == '-') {
if (!isNumber(b = readByte())) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while(isNumber(b = readByte()));
undo(b);
} catch (final NoSuchElementException e) {
}
return n;
}
if (!isNumber(b)) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while(isNumber(b = readByte()));
undo(b);
} catch (final NoSuchElementException e) {
}
return n;
}
public final int nextInt(final int min, final int max) {
final int n = nextInt();
if (min <= n && n <= max) return n;
throw new NumberFormatException();
}
private static boolean isNumber(final byte c) {
return '0' <= c && c <= '9';
}
public final long nextLong() {
byte b = readByte();
long n = 0;
if (b == '-') {
if (!isNumber(b = readByte())) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while(isNumber(b = readByte()));
undo(b);
} catch (final NoSuchElementException e) {
}
return n;
}
if (!isNumber(b)) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while(isNumber(b = readByte()));
undo(b);
} catch (final NoSuchElementException e) {
}
return n;
}
public final long nextLong(final long min, final long max) {
final long n = nextLong();
if (min <= n && n <= max) return n;
throw new NumberFormatException();
}
public final double nextDouble() {
final StringBuilder sb = new StringBuilder();
byte b = readByte();
if (b == '-') {
sb.append(b);
b = readByte();
}
if (b == '0') {
sb.append(b);
b = readByte();
} else while(isNumber(b)) {
sb.append(b);
b = readByte();
}
if (b == '.') {
sb.append(b);
b = readByte();
while(isNumber(b)) {
sb.append(b);
b = readByte();
}
}
if (b == 'e' || b == 'E') {
sb.append(b);
b = readByte();
if (b == '-' || b == '+') {
sb.append(b);
b = readByte();
}
while(isNumber(b)) {
sb.append(b);
b = readByte();
}
}
undo(b);
return Double.parseDouble(sb.toString());
}
}
}