EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)



Approach 解説とほとんど同じです。

  • 今いる場所が不明箇所なら開ける
  • 最も近いペアを作る、または最も近い不明箇所を開ける
    • (最も近い不明箇所の距離 * 3.1 < 最も近いペアの距離 ? 不明箇所 : ペア) を選ぶ
    • 同じ距離なら中心に近い方を選ぶ
  • バタフライ効果が見られる。テストケース 50 個は少ない。




Approach ビームサーチです。

  • 各点の重み : (1 << 3 * 中心からのチェビシェフ距離)
    この後、対角線上の点なら 4 倍、その隣なら 2 倍する。
  • 評価関数 : 各点ごとに、合ってたら 1 ,違ってたら -1 を重みに掛けて和をとる。
    この評価関数は、外側からそろえる。
  • 次の深さのノードの作り方 : バウンディングボックスに完全に含まれるまわし方で、バウンディングボックスの端またはその一つ内側を含むものに限定
  • 重複除去に Zobrist hashing
    • 現在の深さのノード群を評価が良い順に見ていくときに除去する方法と、次の深さのノードを作るときに除去する方法が有ると思いますが、今回は前者を使いました。ハッシュセットを使わずに、評価とハッシュで並べ替えて、直前のノードと同じハッシュなら除去した。
  • ビーム幅 : 残り時間を275等分して、各深さごとできるだけ多くノードを見る。最初の方は1とか2で、最後の方は3桁くらい。
  • たまに完全解にならない

  • うまくいった時 208手(input_1.txt)



  • 時間制限10倍 うまくいった時 193手(input_1.txt)



  • 時間制限100倍 うまくいった時 174手(input_1.txt)





Approach ビームサーチを使いました。

  • 左上から右下に文字を置くのを2周しました。
  • 1週目は長い文字、2周めは残りの文字を使いました。
  • 時間を10倍使っても、980k位しかならなそう。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;

public class CrosswordPuzzler {

private static final char EMPTY = '-';
private int R;
private int C;
private char[][] words;
private char[][] board;
private int[][] count;
private int[] used;

private static final int[] dr = new int[] { 0, 1, };
private static final int[] dc = new int[] { 1, 0, };

private int turn;
private int[] solution;
private int score;
private int duplication;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();

private int[] scores = new int[] { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 };

private int[] headCharToCount = new int[255];

private HashSet<Long> wordHashSet = new HashSet<>();
private HashMap<Long, Integer> wordHashToIndex = new HashMap<>();

private int[] turnToR;
private int[] turnToC;

public String[] createPuzzle(int width, int height, String[] dict) {
init(width, height, dict);
solve();
return makeSolution();
}

private void init(int width, int height, String[] dict) {
R = height;
C = width;
Utils.debug("R", R, "C", C);

HashSet<String> dict2 = new HashSet<>();
for (int i = 0; i < dict.length; i++) {
dict2.add(dict[i]);
}

{
int i = 0;
this.words = new char[dict2.size()][];
for (String d : dict2) {
String word = d;
this.words[i++] = word.toCharArray();
}
}

{
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String key = "" + words[i][0];
map.put(key, 1 + (map.get(key) == null ? 0 : map.get(key).intValue()));
headCharToCount[words[i][0]]++;
}
}

{
Arrays.sort(words, new Comparator<char[]>() {
@Override
public int compare(char[] o1, char[] o2) {
if (o1.length > o2.length) {
return -1;
}
if (o1.length < o2.length) {
return 1;
}

if (headCharToCount[o1[0]] > headCharToCount[o2[0]]) {
return -1;
}
if (headCharToCount[o1[0]] < headCharToCount[o2[0]]) {
return 1;
}

return 0;
}
});
}
for (int i = 0; i < words.length; i++) {
long hash = 0;
for (int j = 0; j < words[i].length; j++) {
hash <<= 5;
hash |= words[i][j] - ('A' - 1);
}
boolean add = wordHashSet.add(hash);
assert add;
wordHashToIndex.put(hash, i);
}

board = new char[R][C];
for (int r = 0; r < R; r++) {
Arrays.fill(board[r], EMPTY);
}
count = new int[R][C];

solution = new int[R * C];
turn = 0;
score = -R * C;

used = new int[words.length];
Arrays.fill(used, -1);

turnToR = new int[R * C];
turnToC = new int[R * C];
if (R < C) {
for (int sum = 0, index = 0; sum < R * C; sum++) {
for (int r = 0, c = sum; c >= 0; c--, r++) {
if (r >= R || c >= C) {
continue;
}
turnToR[index] = r;
turnToC[index] = c;
index++;
}
}
} else {
for (int sum = 0, index = 0; sum < R * C; sum++) {
for (int r = sum, c = 0; r >= 0; r--, c++) {
if (r >= R || c >= C) {
continue;
}
turnToR[index] = r;
turnToC[index] = c;
index++;
}
}
}
}

private ArrayList<State> beamsearch(int maxDepth, int maxWidth, int phase, int currentTrun, double timelimit) {
int sumWidth = 0;

ArrayList<State> currents = new ArrayList<>();
ArrayList<State> nexts = new ArrayList<>();
State best = null;

State state0 = new State(null, -1, 0, 0, -1, score);
currents.add(state0);

int mask = (1 << 2) - 1;

int start = 0;
int end = 0;
for (int i = 0, sum = 0; i < words.length; i++) {
sum += words[i].length;
if (sum > 0.5 * R * C) {
end = i;
break;
}
}
for (int i = 0; i < words.length; i++) {
if (words[i].length < words[end].length) {
end = i;
break;
}
}
Utils.debug("words.length", words.length, "end", end);

double[] timelimits = new double[maxDepth];
{
double startTime = watch.getSecond();
double endTime = timelimit;
for (int i = 0; i < timelimits.length; i++) {
timelimits[i] = startTime + (endTime - startTime) * (i + 1) / timelimits.length;
}
}

for (int depth = 0; depth < maxDepth; depth++) {
if (currents.size() == 0) {
break;
}

int direction = depth & 1;
int r = turnToR[depth >>> 1];
int c = turnToC[depth >>> 1];

int beamWidth = currents.size();
Collections.sort(currents);
for (int width = 0; width < beamWidth; width++) {
if ((width & mask) == mask) {
if (watch.getSecond() > timelimits[depth]) {
sumWidth += width;
break;
}
}
if (width + 1 == beamWidth) {
sumWidth += width;
}

State currentState = currents.get(width);

if (currentState != state0) {
if (best == null || currentState.score > best.score) {
best = currentState;
}
}

set(reverse(toList(currentState)), currentTrun);

for (int wordIndex = start; wordIndex < end; wordIndex++) {
if (used[wordIndex] != -1) {
continue;
}
if (!canAdd(wordIndex, r, c, direction)) {
continue;
}

int copyScore = score;
int copyDuplication = duplication;
simulateAdd(wordIndex, r, c, direction);
State next = new State(currentState, wordIndex, r, c, direction, score);
next.duplication = duplication;
nexts.add(next);
score = copyScore;
duplication = copyDuplication;
}
nexts.add(currentState);
}
{
ArrayList<State> swap = currents;
currents = nexts;
nexts = swap;
}
nexts.clear();
}

Utils.debug("mean width", sumWidth / (R * C * 2));
Utils.debug("score", best.score, "time", watch.getSecondString());

sumWidth = 0;

start = end;
end = words.length;

{
double startTime = watch.getSecond();
double endTime = 9.5;
for (int i = 0; i < timelimits.length; i++) {
timelimits[i] = startTime + (endTime - startTime) * (i + 1) / timelimits.length;
}
}

for (int depth = 0; depth < maxDepth; depth++) {
if (currents.size() == 0) {
break;
}

int direction = depth & 1;
int r = turnToR[depth >>> 1];
int c = turnToC[depth >>> 1];

int beamWidth = currents.size();
Collections.sort(currents);
for (int width = 0; width < beamWidth; width++) {
if ((width & mask) == mask) {
if (watch.getSecond() > timelimits[depth]) {
sumWidth += width;
break;
}
}
if (width + 1 == beamWidth) {
sumWidth += width;
}

State currentState = currents.get(width);

if (currentState != state0) {
if (best == null || currentState.score > best.score) {
best = currentState;
}
}

set(reverse(toList(currentState)), currentTrun);

for (int wordIndex = start; wordIndex < end; wordIndex++) {
if (used[wordIndex] != -1) {
continue;
}
if (!canAdd(wordIndex, r, c, direction)) {
continue;
}
int copyScore = score;
int copyDuplication = duplication;
simulateAdd(wordIndex, r, c, direction);
State next = new State(currentState, wordIndex, r, c, direction, score);
next.duplication = duplication;
nexts.add(next);
score = copyScore;
duplication = copyDuplication;
}
nexts.add(currentState);
}
{
ArrayList<State> swap = currents;
currents = nexts;
nexts = swap;
}
nexts.clear();
}
Utils.debug("mean width", sumWidth / (R * C * 2));
Utils.debug("score", best.score, "time", watch.getSecondString());

for (; turn > currentTrun;) {
previous();
}

return reverse(toList(best));

}

private static final ArrayList<State> list = new ArrayList<>();

public static final ArrayList<State> toList(State state0) {
list.clear();
for (State state = state0; state.parent != null; state = state.parent) {
list.add(state);
}
return list;
}

public static final <T> ArrayList<T> reverse(ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

private void set(ArrayList<State> list, int startIndex) {
int startIndexMinus1 = startIndex - 1;
for (int i = 0; i < list.size() && startIndex + i < turn; i++) {
int v = solution[startIndex + i];
int wordIndex = (v >>> 16) & ((1 << 16) - 1);
int r = (v >>> 7) & ((1 << 6) - 1);
int c = (v >>> 1) & ((1 << 6) - 1);
int direction = (v >>> 0) & ((1 << 1) - 1);

State state = list.get(i);
if (!(state.wordIndex == wordIndex && state.r == r && state.c == c && state.direction == direction)) {
break;
}
startIndexMinus1 = startIndex + i;
}
for (; turn > startIndexMinus1 + 1;) {
previous();
}
for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
State state2 = list.get(i);
next(state2.wordIndex, state2.r, state2.c, state2.direction);
}
}

private void previous() {
remove(turn - 1);
}

private void next(int wordIndex, int r, int c, int direction) {
add(wordIndex, r, c, direction);
}

private void solve() {

ArrayList<State> moves = beamsearch(R * C * 2, 1, 0, 0, 7.5);
if (moves != null) {
for (State state : moves) {
next(state.wordIndex, state.r, state.c, state.direction);
}
}
Utils.debug("score", score, "time", watch.getSecondString());

}

private boolean canAdd(int wordIndex, int r, int c, int direction) {
char[] word = words[wordIndex];
if (r + (word.length - 1) * dr[direction] >= R) {
return false;
}
if (c + (word.length - 1) * dc[direction] >= C) {
return false;
}

{
int nr = r - dr[direction];
int nc = c - dc[direction];
if (nr >= 0 && nc >= 0 && board[nr][nc] != EMPTY) {
return false;
}
}
{
int nr = r + word.length * dr[direction];
int nc = c + word.length * dc[direction];
if (nr < R && nc < C && board[nr][nc] != EMPTY) {
return false;
}
}

boolean hasEmpty = false;
for (int i = 0; i < word.length; i++) {
int nr = r + i * dr[direction];
int nc = c + i * dc[direction];
if (board[nr][nc] == EMPTY) {
hasEmpty = true;
{
int nr2 = nr + dr[direction ^ 1];
int nc2 = nc + dc[direction ^ 1];
if (nr2 < R && nc2 < C && board[nr2][nc2] != EMPTY) {
return false;
}
}
{
int nr2 = nr - dr[direction ^ 1];
int nc2 = nc - dc[direction ^ 1];
if (nr2 >= 0 && nc2 >= 0 && board[nr2][nc2] != EMPTY) {
return false;
}
}

} else if (board[nr][nc] == word[i]) {
} else {
return false;
}
}

if (!hasEmpty) {
return false;
}

add(wordIndex, r, c, direction);

int minR = direction == 0 ? Math.max(0, r - 0) : Math.max(0, r - 0);
int maxR = direction == 0 ? Math.min(R, r + 1) : Math.min(R, r + words[wordIndex].length);
{
for (int r2 = minR; r2 < maxR; r2++) {
long hash = 0;
int length = 0;
for (int c2 = 0; c2 < C; c2++) {
if (board[r2][c2] == EMPTY) {
if (length > 12) {
remove(turn - 1);
return false;
}
if (length > 1) {
Integer index = wordHashToIndex.get(hash);
if (index == null) {
remove(turn - 1);
return false;
} else {
}

if (used[index.intValue()] == -1) {
remove(turn - 1);
return false;
}
if (used[index.intValue()] != ((index.intValue() << 16) | (r2 << 7) | ((c2 - (length - 0)) << 1) | (0))) {
remove(turn - 1);
return false;
}
}
hash = 0;
length = 0;
if (c2 > c) {
break;
}
continue;
}
assert (board[r2][c2] - ('A' - 1)) == ((board[r2][c2] - ('A' - 1)) & ((1 << 5) - 1));
hash <<= 5;
hash |= board[r2][c2] - ('A' - 1);
length++;
}
if (length > 12) {
remove(turn - 1);
return false;
}
if (length > 1) {
Integer index = wordHashToIndex.get(hash);
if (index == null) {
remove(turn - 1);
return false;
} else {
}
if (used[index.intValue()] == -1) {
remove(turn - 1);
return false;
}
if (used[index.intValue()] != ((index.intValue() << 16) | (r2 << 7) | ((C - (length - 0)) << 1) | (0))) {
remove(turn - 1);
return false;
}
}
}
}

int minC = direction == 0 ? Math.max(0, c - 0) : Math.max(0, c - 0);
int maxC = direction == 0 ? Math.min(C, c + words[wordIndex].length) : Math.min(C, c + 1);
{
for (int c2 = minC; c2 < maxC; c2++) {
long hash = 0;
int length = 0;
for (int r2 = 0; r2 < R; r2++) {
if (board[r2][c2] == EMPTY) {
if (length > 12) {
remove(turn - 1);
return false;
}
if (length > 1) {
Integer index = wordHashToIndex.get(hash);
if (index == null) {
remove(turn - 1);
return false;
} else {
}

if (used[index.intValue()] == -1) {
remove(turn - 1);
return false;
}

if (used[index.intValue()] != ((index.intValue() << 16) | ((r2 - (length - 0)) << 7) | (c2 << 1) | (1))) {
remove(turn - 1);
return false;
}
}
hash = 0;
length = 0;
if (r2 > r) {
break;
}
continue;
}
hash <<= 5;
hash |= board[r2][c2] - ('A' - 1);
length++;
}
if (length > 12) {
remove(turn - 1);
return false;
}
if (length > 1) {
Integer index = wordHashToIndex.get(hash);
if (index == null) {
remove(turn - 1);
return false;
} else {
}
if (used[index.intValue()] == -1) {
remove(turn - 1);
return false;
}

if (used[index.intValue()] != ((index.intValue() << 16) | ((R - (length - 0)) << 7) | (c2 << 1) | (1))) {
remove(turn - 1);
return false;
}
}
}
}

remove(turn - 1);

return true;
}

private void simulateAdd(int wordIndex, int r, int c, int direction) {
char[] word = words[wordIndex];
for (int i = 0; i < word.length; i++) {
int nr = r + i * dr[direction];
int nc = c + i * dc[direction];

if (count[nr][nc] == 0) {
score++;
} else {
duplication++;
}
}

score += scores[word.length];
}

private void add(int wordIndex, int r, int c, int direction) {
assert used[wordIndex] == -1;
used[wordIndex] = ((wordIndex << 16) | (r << 7) | (c << 1) | (direction));
solution[turn] = ((wordIndex << 16) | (r << 7) | (c << 1) | (direction));
char[] word = words[wordIndex];
for (int i = 0; i < word.length; i++) {
int nr = r + i * dr[direction];
int nc = c + i * dc[direction];
assert board[nr][nc] == word[i] || board[nr][nc] == EMPTY;

if (count[nr][nc] == 0) {
assert count[nr][nc] == 0 && board[nr][nc] == EMPTY;
} else {
assert count[nr][nc] > 0 && board[nr][nc] == word[i];
}

if (count[nr][nc] == 0) {
board[nr][nc] = word[i];
score++;
} else {
duplication++;
}
assert count[nr][nc] >= 0;
count[nr][nc]++;
}

score += scores[word.length];
turn++;
}

private void remove(int index) {
turn--;
int v = solution[index];
int wordIndex = (v >>> 16) & ((1 << 16) - 1);
int r = (v >>> 7) & ((1 << 6) - 1);
int c = (v >>> 1) & ((1 << 6) - 1);
int direction = (v >>> 0) & ((1 << 1) - 1);
remove(wordIndex, r, c, direction);
}

private void remove(int wordIndex, int r, int c, int direction) {
used[wordIndex] = -1;
char[] word = words[wordIndex];
for (int i = 0; i < word.length; i++) {
int nr = r + i * dr[direction];
int nc = c + i * dc[direction];
assert board[nr][nc] == word[i] : Utils.toString("word, r, c, direction", word, r, c, direction, "nr, nc", nr, nc, board[nr][nc], word[i]);
count[nr][nc]--;
assert count[nr][nc] >= 0;
if (count[nr][nc] == 0) {
board[nr][nc] = EMPTY;
score--;
} else {
duplication--;
}
}

score -= scores[word.length];
}

private String[] makeSolution() {
String[] res = new String[R];
for (int r = 0; r < R; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < C; c++) {
sb.append(board[r][c]);
}
res[r] = sb.toString();
}
return res;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
CrosswordPuzzler sol = new CrosswordPuzzler();
int width = Integer.parseInt(br.readLine());
int height = Integer.parseInt(br.readLine());
String[] dict = new String[Integer.parseInt(br.readLine())];
for (int i = 0; i < dict.length; i++)
dict[i] = br.readLine();
String[] ret = sol.createPuzzle(width, height, dict);
System.out.println(ret.length);
for (int i = 0; i < ret.length; i++)
System.out.println(ret[i]);
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}

}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class State implements Comparable<State> {
State parent;
int wordIndex;
int r;
int c;
int direction;
int score;
int less6;
private double random;
int duplication;

public State(State parent, int wordIndex, int r, int c, int direction, int score) {
super();
this.parent = parent;
this.wordIndex = wordIndex;
this.r = r;
this.c = c;
this.direction = direction;
this.score = score;
random = CrosswordPuzzler.rng.nextDouble();
}

@Override
public int compareTo(State o) {

if (duplication + score > o.duplication + o.score) {
return -1;
}
if (duplication + score < o.duplication + o.score) {
return 1;
}

if (duplication > o.duplication) {
return -1;
}
if (duplication < o.duplication) {
return 1;
}

if (score > o.score) {
return -1;
}
if (score < o.score) {
return 1;
}

return 0;
}

}


このページのトップヘ