EvbCFfp1XB

problem and my answer.



problem https://github.com/kosakkun/Typical-MM/tree/master/GraphColoring

Approach
  • 貪欲法で有効な彩色を見つける。
  • その状態から色を1つ減らして、焼きなまし法やタブーサーチで有効な彩色を見つける。これを繰り返す。

  • 診断人さんが使ってたタブーサーチが強かった。

  • 貪欲法
    • 次数の大きい頂点から彩色する。
  • タブーサーチ
    • 有効な彩色が見つかったら、ある色を無色にして、色を1つ減らす。
    • 無色の頂点から1つランダムに選ぶ。
    • その頂点に隣接する頂点の色ごとに次数の和を求める。
    • タブーリストにない色で、最も次数の和が小さい色で彩色する。
      • 全ての色がタブーリストに載ってたら、タブーリストを無視して、最も次数の和が小さい色で彩色する。
    • 隣接する頂点が同じ色なら、その頂点を無色にする。
    • 彩色した色と頂点のペアをタブーリストに加える。





source code

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

public class GraphColoring {
private static final int NUM_TABU_LIST = 75;
private static final int NG = ((1 << 16) - 1);

private int numVertexes;
private int numEdges;
private IntSet[] nextVertexSet;
private int usedColors;
private int[] vertexToColor;

private int bestUsedColors;
private int[] bestVertexToColor;

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

private int[] tabuList = new int[NUM_TABU_LIST];
private int indexOfTabuList = 0;
private boolean[][] isTabu;

private int[] colorToSumDegree = new int[256];

private int[] run(int N, int M, int[] a, int[] b) {
init(N, M, a, b);
solve();
return vertexToColor;
}

private void init(int N, int M, int[] a, int[] b) {
this.numVertexes = N;
this.numEdges = M;

Utils.debug("numVertexes", numVertexes, "numEdges", numEdges);

nextVertexSet = new IntSet[numVertexes];
for (int i = 0; i < numVertexes; i++) {
nextVertexSet[i] = new IntSet(numVertexes);
}
for (int i = 0; i < numEdges; i++) {
nextVertexSet[a[i]].add(b[i]);
nextVertexSet[b[i]].add(a[i]);
}

vertexToColor = new int[numVertexes];
bestVertexToColor = new int[numVertexes];
for (int i = 0; i < numVertexes; i++) {
vertexToColor[i] = -1;
bestVertexToColor[i] = -1;
}

bestUsedColors = (int) 1e9;

uncoloredVertexSet = new IntSet(numVertexes);

isTabu = new boolean[numVertexes][256];
}

private void solve() {
greedy();
tabuSearch();
}

private void tabuSearch() {
for (int numIterations = 0;; numIterations++) {
if ((numIterations & ((1 << 10) - 1)) == 0) {
if (watch.getSecond() >= 9.5) {
loadBest();
Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
break;
}
}
while (uncoloredVertexSet.size() == 0) {
saveBest();
Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
usedColors--;
for (int v = 0; v < numVertexes; v++) {
if (vertexToColor[v] == usedColors) {
uncoloredVertexSet.add(v);
}
}
initTabuList();
}

int vertex = uncoloredVertexSet.get((int) (uncoloredVertexSet.size() * rng.nextDouble()));

for (int color = 0; color < usedColors; color++) {
colorToSumDegree[color] = 0;
}
for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
colorToSumDegree[vertexToColor[nextVertex]] += nextVertexSet[nextVertex].size();
}

int bestSumDegree = (int) 1e9;
int bestColor = -1;
for (int color = 0; color < usedColors; color++) {
if (isTabu[vertex][color]) {
continue;
}

if (colorToSumDegree[color] < bestSumDegree) {
bestSumDegree = colorToSumDegree[color];
bestColor = color;
}
}

if (bestColor == -1) {
for (int color = 0; color < usedColors; color++) {
if (colorToSumDegree[color] < bestSumDegree) {
bestSumDegree = colorToSumDegree[color];
bestColor = color;
}
}
}

vertexToColor[vertex] = bestColor;
uncoloredVertexSet.removeValue(vertex);

for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
if (vertexToColor[nextVertex] == bestColor) {
vertexToColor[nextVertex] = usedColors;
uncoloredVertexSet.add(nextVertex);
}
}

addTabu(vertex, bestColor);

}
}

private void addTabu(int vertex, int color) {
int tabu = tabuList[indexOfTabuList];
if (vertex(tabu) != NG) {
isTabu[vertex(tabu)][color(tabu)] = false;
}

tabuList[indexOfTabuList] = encode(vertex, color);
isTabu[vertex][color] = true;

indexOfTabuList++;
if (indexOfTabuList >= NUM_TABU_LIST) {
indexOfTabuList = 0;
}
}

private void initTabuList() {
for (int i = 0; i < NUM_TABU_LIST; ++i) {
int tabu = tabuList[i];
if (vertex(tabu) != NG) {
isTabu[vertex(tabu)][color(tabu)] = false;
}
tabuList[i] = encode(NG, NG);
}
}

private void greedy() {
ArrayList<Pair<Integer, Integer>> degreeAndVertexPairs = new ArrayList<>();
for (int vertex = 0; vertex < numVertexes; vertex++) {
degreeAndVertexPairs.add(new Pair<Integer, Integer>(-nextVertexSet[vertex].size(), vertex));
}
Collections.sort(degreeAndVertexPairs);
for (int i = 0; i < degreeAndVertexPairs.size(); i++) {
int vertex = degreeAndVertexPairs.get(i).second.intValue();
for (int color = 0; color < 256; color++) {
if (canUse(vertex, color)) {
vertexToColor[vertex] = color;
break;
}
}
}
usedColors = calculateUsedColors();
saveBest();
Utils.debug("greedy", "usedColors", usedColors, "time", watch.getSecondString());
}

private int calculateUsedColors() {
HashSet<Integer> set = new HashSet<>();
for (int vertex = 0; vertex < numVertexes; vertex++) {
set.add(vertexToColor[vertex]);
}
return set.size();
}

private boolean canUse(int vertex, int color) {
for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
if (vertexToColor[nextVertex] == color) {
return false;
}
}
return true;
}

private void saveBest() {
if (usedColors < bestUsedColors) {
bestUsedColors = usedColors;
for (int i = 0; i < numVertexes; i++) {
bestVertexToColor[i] = vertexToColor[i];
}
}
}

private void loadBest() {
usedColors = bestUsedColors;
for (int i = 0; i < numVertexes; i++) {
vertexToColor[i] = bestVertexToColor[i];
}
}

private static final int encode(int vertex, int color) {
return (vertex << 16) | color;
}

private static final int vertex(int v) {
return v >>> 16;
}

private static final int color(int v) {
return v & ((1 << 16) - 1);
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

String line = br.readLine();
String[] split = line.split(" ");
int N = Integer.parseInt(split[0]);
int M = Integer.parseInt(split[1]);
int[] a = new int[M];
int[] b = new int[M];
for (int i = 0; i < M; i++) {
line = br.readLine();
split = line.split(" ");
a[i] = Integer.parseInt(split[0]);
b[i] = Integer.parseInt(split[1]);
}

GraphColoring gc = new GraphColoring();
int[] ret = gc.run(N, M, a, b);
for (int i = 0; i < N; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (IOException e) {
e.printStackTrace();
}
}

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() <= 0;
}

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

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 long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

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

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

}

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);
}

}




Approach 複数のアプローチを試して一番スコアの良いものを返した。

  • トラックを使わずに割当問題を解く。
    • 最小費用流を使った。
    • 450000点くらい。
  • 倉庫のアイテムをトラックで顧客の近くに移動して、割当問題を解く。
    • 600000点くらい。
    • 次のアプローチを使うと、このアプローチはほとんど出番がないので最終的に使わなかった。
  • 全てのアイテムを一箇所に集めて、配る。
    • 集めるとき、最小全域木にフェルマー点を加えて、もう一度最小全域木を作った。
      • フェルマー点を求めるとき、トラックのコストはマンハッタン距離なのに、ユークリッド距離を使って良かったんだろうか?
    • 配るとき、トラックの行き先の位置と個数を焼き鈍した。
      • 近傍は、点の追加、削除、移動。
      • 時間を10倍にしても2%しか改善しない。
    • 850000点くらい。

残り10%ほどを改善するアイディア
  • 全てのアイテムを一箇所に集める必要はない。
    • 集めるとき、配るとき両方のコストが減る。

感想

  • やることが色々あって楽しかった。


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.LinkedList;
import java.util.PriorityQueue;

public class TrucksAndCouriers {
private int truckFixed;
private int truckVariable;
private int[] warehouseX;
private int[] warehouseY;
private int[] warehouseItem;
private int[] warehouseQuantity;
private int[] customerX;
private int[] customerY;
private int[] customerItem;
private int numWarehouses;
private int numCustomers;
private ArrayList<String> solution;
private int score;
private int bestScore;
private ArrayList<Truck> bestTrucks;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();
private ArrayList<Customer> customers2;
private ArrayList<Truck> trucks;
private HashMap<Integer, HashMap<Integer, Integer>> warePointToItemToQuantity;
private ArrayList<Integer> warePoints;
private int sumTruckCost;
private HashMap<Integer, ArrayList<Customer>> warePointToCustomers;
private HashMap<Integer, ArrayList<Customer>> warePointToCustomers0;
private int numOriginalWares;

public String[] planShipping(int truckFixed, int truckVariable, int[] warehouseX, int[] warehouseY, int[] warehouseItem, int[] warehouseQuantity, int[] customerX, int[] customerY, int[] customerItem) {
init(truckFixed, truckVariable, warehouseX, warehouseY, warehouseItem, warehouseQuantity, customerX, customerY, customerItem);
solve();
Utils.debug("score", score, "time", watch.getSecondString());
String[] solution = makeSolution();
Utils.debug("score", score, "time", watch.getSecondString());
return solution;
}

private String[] makeSolution() {
score = 0;
for (Truck truck : trucks) {
addTruck2(truck);
}

ArrayList<Pair<Integer, Integer>> warePointAndItemPairs = new ArrayList<>();
for (Integer warePoint : warePoints) {
for (Integer item : warePointToItemToQuantity.get(warePoint).keySet()) {
warePointAndItemPairs.add(new Pair<Integer, Integer>(warePoint, item));
}
}

int[][] costs = new int[customers2.size()][warePointAndItemPairs.size()];

for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int item = customer.item;
for (int wi = 0; wi < warePointAndItemPairs.size(); wi++) {
Integer warePoint = warePointAndItemPairs.get(wi).first;
Integer item2 = warePointAndItemPairs.get(wi).second;
if (item2 != item) {
costs[ci][wi] = -1;
continue;
}
if (warePointToItemToQuantity.get(warePoint).get(item2) <= 0) {
costs[ci][wi] = -1;
continue;
}
costs[ci][wi] = distance(customer, warePoint);
}
}

int R = costs.length;
int C = costs[0].length;

MinCostFlow mcf = new MinCostFlow(R + C + 2);

int s = R + C;
int t = s + 1;

for (int r = 0; r < R; r++) {
mcf.addEdge(s, r, 1, 0);
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (costs[r][c] < 0) {
continue;
}
mcf.addEdge(r, R + c, 1, costs[r][c]);
}
}
for (int c = 0; c < C; c++) {
Pair<Integer, Integer> pair = warePointAndItemPairs.get(c);
Integer warePoint = pair.first;
Integer item = pair.second;
mcf.addEdge(R + c, t, quantity(y(warePoint), x(warePoint), item), 0);
}

int minCost = mcf.run(s, t, R);

int[] rToC = new int[R];
Arrays.fill(rToC, -1);
for (int r = 0; r < R; r++) {
ArrayList<Edge> edges = mcf.G.get(r);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int c = e.to - R;
rToC[r] = c;
break;
}
}
for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int item = customer.item;
int ware = rToC[ci];
Pair<Integer, Integer> pair = warePointAndItemPairs.get(ware);
addCourier(x(pair.first), y(pair.first), customer.x, customer.y, item);
}
return (String[]) solution.toArray(new String[solution.size()]);
}

private void addTruck2(Truck truck) {
if (truck.items.size() == 0) {
return;
}
String s = "T," + truck.startX + "," + truck.startY + "," + truck.destX + "," + truck.destY;
for (Integer item : truck.items) {
s += "," + item;
}
solution.add(s);
score += truckFixed + truckVariable * (Math.abs(truck.startX - truck.destX) + Math.abs(truck.startY - truck.destY));
}

private void init(int truckFixed, int truckVariable, int[] warehouseX, int[] warehouseY, int[] warehouseItem, int[] warehouseQuantity, int[] customerX, int[] customerY, int[] customerItem) {
this.truckFixed = truckFixed;
this.truckVariable = truckVariable;
this.numWarehouses = warehouseX.length;
this.warehouseX = warehouseX;
this.warehouseY = warehouseY;
this.warehouseItem = warehouseItem;
this.warehouseQuantity = warehouseQuantity;
this.numCustomers = customerX.length;
this.customerX = customerX;
this.customerY = customerY;
this.customerItem = customerItem;
warePoints = new ArrayList<>();
warePointToItemToQuantity = new HashMap<>();
for (int i = 0; i < numWarehouses; i++) {
int z = z(this.warehouseX[i], this.warehouseY[i]);
if (warePointToItemToQuantity.get(z) == null) {
warePointToItemToQuantity.put(z, new HashMap<>());
warePoints.add(z);
}
Integer quantity = warePointToItemToQuantity.get(z).get(this.warehouseItem[i]);
warePointToItemToQuantity.get(z).put(this.warehouseItem[i], (quantity == null ? 0 : quantity.intValue()) + this.warehouseQuantity[i]);
}
solution = new ArrayList<>();

score = 0;
bestScore = (int) 1e9;
customers2 = new ArrayList<>();
for (int i = 0; i < numCustomers; i++) {
Customer customer = new Customer();
customer.x = this.customerX[i];
customer.y = this.customerY[i];
customer.item = this.customerItem[i];
customers2.add(customer);
}

trucks = new ArrayList<>();
Utils.debug("truckFixed", truckFixed, "truckVariable", truckVariable, "numWarehouses", numWarehouses, "numCustomers", numCustomers);
ArrayList<Pair<Integer, Integer>> warePointAndItemPairs = new ArrayList<>();
for (Integer warePoint : warePoints) {
for (Integer item : warePointToItemToQuantity.get(warePoint).keySet()) {
warePointAndItemPairs.add(new Pair<Integer, Integer>(warePoint, item));
}
}

int[][] costs = new int[customers2.size()][warePointAndItemPairs.size()];

for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int item = customer.item;
for (int wi = 0; wi < warePointAndItemPairs.size(); wi++) {
Integer warePoint = warePointAndItemPairs.get(wi).first;
Integer item2 = warePointAndItemPairs.get(wi).second;
if (item2 != item) {
costs[ci][wi] = -1;
continue;
}
if (warePointToItemToQuantity.get(warePoint).get(item2) <= 0) {
costs[ci][wi] = -1;
continue;
}
costs[ci][wi] = distance(customer, warePoint);
}
}

int R = costs.length;
int C = costs[0].length;

MinCostFlow mcf = new MinCostFlow(R + C + 2);

int s = R + C;
int t = s + 1;

for (int r = 0; r < R; r++) {
mcf.addEdge(s, r, 1, 0);
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (costs[r][c] < 0) {
continue;
}
mcf.addEdge(r, R + c, 1, costs[r][c]);
}
}
for (int c = 0; c < C; c++) {
Pair<Integer, Integer> pair = warePointAndItemPairs.get(c);
Integer warePoint = pair.first;
Integer item = pair.second;
mcf.addEdge(R + c, t, quantity(y(warePoint), x(warePoint), item), 0);
}

int minCost = mcf.run(s, t, R);
score = minCost;
bestScore = score;
bestTrucks = new ArrayList<>();

int[] rToC = new int[R];
Arrays.fill(rToC, -1);
for (int r = 0; r < R; r++) {
ArrayList<Edge> edges = mcf.G.get(r);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int c = e.to - R;
rToC[r] = c;
break;
}
}

warePointToCustomers = new HashMap<>();
for (int r = 0; r < rToC.length; r++) {
int c = rToC[r];
Integer warePoint = warePointAndItemPairs.get(c).first;
if (warePointToCustomers.get(warePoint) == null) {
warePointToCustomers.put(warePoint, new ArrayList<>());
}
warePointToCustomers.get(warePoint).add(customers2.get(r));
}
warePointToCustomers0 = new HashMap<>();
for (int r = 0; r < rToC.length; r++) {
int c = rToC[r];
Integer warePoint = warePointAndItemPairs.get(c).first;
if (warePointToCustomers0.get(warePoint) == null) {
warePointToCustomers0.put(warePoint, new ArrayList<>());
}
warePointToCustomers0.get(warePoint).add(customers2.get(r));
}

numOriginalWares = warePoints.size();
Utils.debug("score", score, "time", watch.getSecondString());
}

private int distance(Customer customer, Integer warePoint) {
return distance(x(warePoint), y(warePoint), customer.x, customer.y);
}

private static final int distance(int x, int y, int x2, int y2) {
return Math.abs(x - x2) + Math.abs(y - y2);
}

private static final int z(int x, int y) {
return (y << 16) | (x);
}

private static final int x(int z) {
return z & ((1 << 16) - 1);
}

private static final int y(int z) {
return z >>> 16;
}

private void solve() {
moveToCenterMST();
SA2();
Utils.debug("points.size()", points.size());
score += score2;
makeTrucks();

saveBest();
loadBest();
}

private void makeTrucks() {
MinimumSpanningTree mst = new MinimumSpanningTree(points.size());
for (int i = 0; i < points.size(); i++) {
Point pi = points.get(i);
for (int j = i + 1; j < points.size(); j++) {
Point pj = points.get(j);
mst.addEdge(i, j, truckFixed + truckVariable * distance(pi.x, pi.y, pj.x, pj.y));
}
}

Utils.debug("mst.kruskal()", mst.kruskal());

ArrayList<Integer>[] pointToCustomers = new ArrayList[points.size()];
for (int i = 0; i < pointToCustomers.length; i++) {
pointToCustomers[i] = new ArrayList<>();
}
int[] customerToPoint = new int[customers2.size()];
for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int min = (int) 1e9;
int mini = -1;
for (int pi = 0; pi < points.size(); pi++) {
int distance = distance(customer.x, customer.y, points.get(pi).x, points.get(pi).y);
if (distance < min) {
min = distance;
mini = pi;
}
}
customerToPoint[ci] = mini;
pointToCustomers[mini].add(ci);
}

indexToCustomerIndexes = new ArrayList[points.size()];
for (int i = 0; i < indexToCustomerIndexes.length; i++) {
indexToCustomerIndexes[i] = new ArrayList<>();
}
dfs(0, mst, new boolean[points.size()], customerToPoint, pointToCustomers);
Utils.debug("0 size", indexToCustomerIndexes[0].size(), customers2.size());

bfs(0, mst);
}

private void bfs(int index0, MinimumSpanningTree mst) {
LinkedList<Integer> queue = new LinkedList<>();
boolean[] used = new boolean[points.size()];
{
queue.add(index0);
used[index0] = true;
}
for (; !queue.isEmpty();) {
int index = queue.pollFirst().intValue();
for (int i = 0; i < mst.G.get(index).size(); i++) {
Edge3 edge3 = mst.G.get(index).get(i);

if (used[edge3.to]) {
continue;
}
used[edge3.to] = true;
queue.add(edge3.to);

Point point = points.get(index);
Point point2 = points.get(edge3.to);
ArrayList<Integer> items = new ArrayList<>();
for (Integer ci : indexToCustomerIndexes[edge3.to]) {
items.add(customers2.get(ci.intValue()).item);
}
Truck truck = new Truck(point.x, point.y, point2.x, point2.y, items);
addTruck(truck);

}
}
}

private ArrayList<Integer>[] indexToCustomerIndexes;

private void dfs(int index, MinimumSpanningTree mst, boolean[] used, int[] customerToPoint, ArrayList<Integer>[] pointToCustomers) {
used[index] = true;

for (int i = 0; i < mst.G.get(index).size(); i++) {
Edge3 edge3 = mst.G.get(index).get(i);
if (used[edge3.to]) {
continue;
}
dfs(edge3.to, mst, used, customerToPoint, pointToCustomers);
indexToCustomerIndexes[index].addAll(indexToCustomerIndexes[edge3.to]);
}
indexToCustomerIndexes[index].addAll(pointToCustomers[index]);
}

private Point FermatPoint(Point a, Point b, Point c) {
double da = dist(b, c);
double db = dist(a, c);
double dc = dist(a, b);

if (da * da >= db * db + dc * dc + db * dc)
return null;
if (db * db >= dc * dc + da * da + dc * da)
return null;
if (dc * dc >= da * da + db * db + da * db)
return null;

double A = Math.acos((db * db + dc * dc - da * da) / (2 * db * dc));
double B = Math.acos((dc * dc + da * da - db * db) / (2 * dc * da));
double C = Math.acos((da * da + db * db - dc * dc) / (2 * da * db));

double ra = csc(A + Math.PI / 3);
double rb = csc(B + Math.PI / 3);
double rc = csc(C + Math.PI / 3);

double wa = da * ra;
double wb = db * rb;
double wc = dc * rc;

double wall = wa + wb + wc;

double x = a.x * wa + b.x * wb + c.x * wc;
double y = a.y * wa + b.y * wb + c.y * wc;
return new Point((int) (0.5 + x / wall), (int) (0.5 + y / wall));
}

private double csc(double x) {
return 1.0 / Math.sin(x);
}

private double dist(Point a, Point b) {
int dx = a.x - b.x;
int dy = a.y - b.y;
return Math.sqrt(dx * dx + dy * dy);
}

private void moveToCenterMST() {
score = 0;

MinimumSpanningTree mst = new MinimumSpanningTree(warePoints.size());
for (int from = 0; from < warePoints.size(); from++) {
for (int to = from + 1; to < warePoints.size(); to++) {
mst.addEdge(from, to, truckFixed + truckVariable * distance(x(warePoints.get(from)), y(warePoints.get(from)), x(warePoints.get(to)), y(warePoints.get(to))));
}
}
int cost = mst.kruskal();
Utils.debug("MST cost", cost);

for (int from = 0, size = warePoints.size(); from < size; from++) {
Integer za = warePoints.get(from);
Point a = new Point(x(za), y(za));
ArrayList<Edge3> edges = mst.G.get(from);
for (int i = 0; i < edges.size(); i++) {
Edge3 edge = edges.get(i);
Integer zb = warePoints.get(edge.to);
Point b = new Point(x(zb), y(zb));
for (int j = i + 1; j < edges.size(); j++) {
Edge3 edge2 = edges.get(j);
Integer zc = warePoints.get(edge2.to);
Point c = new Point(x(zc), y(zc));
Point fermat = FermatPoint(a, b, c);
if (fermat == null) {
continue;
}

if (truckCost(fermat, a) + truckCost(fermat, b) + truckCost(fermat, c) < truckCost(a, b) + truckCost(a, c)) {
warePoints.add(z(fermat.x, fermat.y));
}
}
}
}

mst = new MinimumSpanningTree(warePoints.size());
for (int from = 0; from < warePoints.size(); from++) {
for (int to = from + 1; to < warePoints.size(); to++) {
mst.addEdge(from, to, truckFixed + truckVariable * distance(x(warePoints.get(from)), y(warePoints.get(from)), x(warePoints.get(to)), y(warePoints.get(to))));
}
}
cost = mst.kruskal();
Utils.debug("MST cost", cost);

LinkedList<Integer> queue = new LinkedList<>();
boolean[] used = new boolean[warePoints.size()];
{
int min = (int) 1e9;
int mini = -1;
for (int i = 0; i < warePoints.size(); i++) {
Integer warePoint = warePoints.get(i);
int x = x(warePoint);
int y = y(warePoint);
int distance = distance(x, y, 500, 500);
if (distance < min) {
min = distance;
mini = i;
}
}
queue.add(mini);
used[mini] = true;
}
ArrayList<Pair<Integer, Integer>> edgesAndWarePairs = new ArrayList<>();
for (; !queue.isEmpty();) {
Integer v = queue.pollFirst();
int size = (v.intValue() >>> 16);
int index = v.intValue() & ((1 << 16) - 1);

edgesAndWarePairs.add(new Pair<Integer, Integer>(-size, index));

for (Edge3 edge3 : mst.G.get(index)) {
if (used[edge3.to]) {
continue;
}
used[edge3.to] = true;
queue.add(((size + 1) << 16) | edge3.to);
}
}
Collections.sort(edgesAndWarePairs);

used = new boolean[warePoints.size()];
for (int i = 0; i < edgesAndWarePairs.size() - 1; i++) {
Integer index = edgesAndWarePairs.get(i).second;
Integer warePoint = warePoints.get(index);
used[index] = true;
int fromX = x(warePoint);
int fromY = y(warePoint);
ArrayList<Customer> customers = warePointToCustomers.get(warePoint);
if (customers == null || customers.size() == 0) {
continue;
}

int toX = 500;
int toY = 500;

ArrayList<Edge3> edge3s = mst.G.get(index);
for (int j = 0; j < edge3s.size(); j++) {
if (used[edge3s.get(j).to]) {
continue;
}
Integer warePointTo = warePoints.get(edge3s.get(j).to);
toX = x(warePointTo);
toY = y(warePointTo);
break;
}
int truckCost = truckFixed + truckVariable * distance(toX, toY, fromX, fromY);
ArrayList<Integer> items = new ArrayList<>();
for (Customer customer : customers) {
items.add(customer.item);
}

Truck truck = new Truck(fromX, fromY, toX, toY, items);

if (!canAddTruck(truck.startX, truck.startY, truck.destX, truck.destY, truck.items)) {
return;
}
addTruck(truck);

if (warePointToCustomers.get(z(toX, toY)) == null) {
warePointToCustomers.put(z(toX, toY), new ArrayList<>());
}
warePointToCustomers.get(z(toX, toY)).addAll(customers);
warePointToCustomers.get(warePoint).clear();
score += truckCost;
Utils.debug(i, "score", score);
}

Pair<Integer, Integer> pair = edgesAndWarePairs.get(edgesAndWarePairs.size() - 1);
Integer warePoint = warePoints.get(pair.second.intValue());
points.add(new Point(x(warePoint), y(warePoint)));

Utils.debug("score", score);
}

private int truckCost(Point a, Point b) {
return truckFixed + truckVariable * distance(a.x, a.y, b.x, b.y);
}

private ArrayList<Point> points = new ArrayList<>();

private void SA2() {
score2 = calculateScore(points);
double second = Math.ceil(watch.getSecond());
sa.endTime = 8.0;
sa.init();
for (;; sa.numIterations++) {
{
sa.update();
if (sa.isTLE()) {
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%6.0f", score2), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}
if (sa.time > second) {
second++;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%6.0f", score2), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

mutate2();

}
}

private void mutate2() {
double random = 3 * rng.nextDouble();
if (random < 1) {
addPoint();
} else if (random < 2) {
removePoint();
} else if (random < 3) {
movePoint();
}
}

private double score2;

private void addPoint() {
int x = (int) (1001 * rng.nextDouble());
int y = (int) (1001 * rng.nextDouble());
points.add(new Point(x, y));

double score = calculateScore(points);

if (sa.accept(score - score2)) {
score2 = score;
} else {
points.remove(points.size() - 1);
}
}

private MinimumSpanningTree mst10 = new MinimumSpanningTree(1000);

private double calculateScore(ArrayList<Point> points2) {
mst10.clear(points2.size());
for (int i = 0; i < points2.size(); i++) {
Point pi = points2.get(i);
for (int j = i + 1; j < points2.size(); j++) {
Point pj = points2.get(j);
mst10.addEdge(i, j, truckFixed + truckVariable * distance(pi.x, pi.y, pj.x, pj.y));
}
}
int score = mst10.kruskal();
for (Customer customer : customers2) {
int min = (int) 1e9;
for (int i = 0; i < points2.size(); i++) {
int distance = distance(customer.x, customer.y, points2.get(i).x, points2.get(i).y);
if (distance < min) {
min = distance;
}
}
score += min;
}
return score;
}

private void removePoint() {
if (points.size() <= 1) {
return;
}
int index = 1 + (int) ((points.size() - 1) * rng.nextDouble());
Point p = points.remove(index);

double score = calculateScore(points);

if (sa.accept(score - score2)) {
score2 = score;
} else {
points.add(p);
}
}

private void movePoint() {
if (points.size() <= 1) {
return;
}

int index = 1 + (int) ((points.size() - 1) * rng.nextDouble());
int x = points.get(index).x;
int y = points.get(index).y;

points.get(index).x += (int) (-0.5 * sa.range + sa.range * rng.nextDouble());
points.get(index).x = Math.min(1000, Math.max(0, points.get(index).x));
points.get(index).y += (int) (-0.5 * sa.range + sa.range * rng.nextDouble());
points.get(index).y = Math.min(1000, Math.max(0, points.get(index).y));

double score = calculateScore(points);

if (sa.accept(score - score2)) {
score2 = score;
} else {
points.get(index).x = x;
points.get(index).y = y;
}
}

private void addTruck(Truck truck) {
trucks.add(truck);
addTruck(truck.startX, truck.startY, truck.destX, truck.destY, truck.items);
}

private void removeTruck(Truck truck) {
trucks.remove(truck);
removeTruck(truck.startX, truck.startY, truck.destX, truck.destY, truck.items);
}

private void addTruck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
for (Integer item : items) {
if (quantity(startY, startX, item) <= 0) {
Utils.debug("warehouses[startY][startX][item] <= 0");
return;
}
}
for (Integer item : items) {
add(startY, startX, item, -1);
add(destY, destX, item, 1);
}
}

private void removeTruck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
for (Integer item : items) {
add(startY, startX, item, 1);
add(destY, destX, item, -1);
}
}

private boolean canAddTruck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
for (Integer item : items) {
if (quantity(startY, startX, item) <= 0) {
return false;
}
}
return true;
}

private int quantity(int y, int x, Integer item) {
if (warePointToItemToQuantity.get(z(x, y)) == null) {
return 0;
}
if (warePointToItemToQuantity.get(z(x, y)).get(item) == null) {
return 0;
}
return warePointToItemToQuantity.get(z(x, y)).get(item);
}

private void add(int y, int x, Integer item, int value) {
assert item != null;
int z = z(x, y);
if (warePointToItemToQuantity.get(z) == null) {
warePointToItemToQuantity.put(z, new HashMap<>());
warePoints.add(z);
}
assert warePointToItemToQuantity.get(z) != null;
Integer quantity = warePointToItemToQuantity.get(z).get(item);
int value2 = (quantity == null ? 0 : quantity.intValue()) + value;
warePointToItemToQuantity.get(z).put(item, value2);
}

private void addCourier(int startX, int startY, int destX, int destY, int item) {
solution.add("C," + startX + "," + startY + "," + destX + "," + destY + "," + item);
score += Math.abs(startX - destX) + Math.abs(startY - destY);
}

private void saveBest() {
if (score < bestScore) {
bestScore = score;
bestTrucks.clear();
for (Truck truck : trucks) {
ArrayList<Integer> items = new ArrayList<>();
for (Integer item : truck.items) {
items.add(item);
}
bestTrucks.add(new Truck(truck.startX, truck.startY, truck.destX, truck.destY, items));
}
}
}

private void loadBest() {
score = bestScore;
for (int i = trucks.size() - 1; i >= 0; i--) {
Truck truck = trucks.get(i);
removeTruck(truck);
}
trucks.clear();
for (Truck truck : bestTrucks) {
ArrayList<Integer> items = new ArrayList<>();
for (Integer item : truck.items) {
items.add(item);
}
Truck e = new Truck(truck.startX, truck.startY, truck.destX, truck.destY, items);
addTruck(e);
}
}

private static int[] readArray(BufferedReader br) throws Exception {
int[] ret = new int[Integer.parseInt(br.readLine())];
for (int i = 0; i < ret.length; i++)
ret[i] = Integer.parseInt(br.readLine());
return ret;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
TrucksAndCouriers sol = new TrucksAndCouriers();
int truckFixed = Integer.parseInt(br.readLine());
int truckVariable = Integer.parseInt(br.readLine());
int[] warehouseX = readArray(br);
int[] warehouseY = readArray(br);
int[] warehouseItem = readArray(br);
int[] warehouseQuantity = readArray(br);
int[] customerX = readArray(br);
int[] customerY = readArray(br);
int[] customerItem = readArray(br);
String[] ret = sol.planShipping(truckFixed, truckVariable, warehouseX, warehouseY, warehouseItem, warehouseQuantity, customerX, customerY, customerItem);
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();
}
}
}

class Edge {
int to;
int cap;
int cost;
int rev;

public Edge(int to, int cap, int cost, int rev) {
this.to = to;
this.cap = cap;
this.cost = cost;
this.rev = rev;
}
}

class MinCostFlow {

private static final int INF = (int) 1e9;
public ArrayList<ArrayList<Edge>> G;
private int[] dist;
private int[] prevv;
private int[] preve;

public MinCostFlow(int v) {
clear(v);
}

public void clear(int v) {
G = new ArrayList<ArrayList<Edge>>();
for (int i = 0; i < v; i++) {
G.add(new ArrayList<Edge>());
}
dist = new int[v];
prevv = new int[v];
preve = new int[v];
}

public void addEdge(int from, int to, int cap, int cost) {
assert cost >= 0;
assert cost <= INF;

int edgeIndex = G.get(from).size();
int reverseEdgeIndex = G.get(to).size();
G.get(from).add(new Edge(to, cap, cost, reverseEdgeIndex));
G.get(to).add(new Edge(from, 0, -cost, edgeIndex));
}

public int run(int s, int t, int f) {
int res = 0;
while (f > 0) {
Arrays.fill(dist, INF);
dist[s] = 0;

for (;;) {
boolean update = false;

for (int v = 0; v < dist.length; v++) {
if (dist[v] >= INF) {
continue;
}
for (int i = 0; i < G.get(v).size(); i++) {
Edge e = G.get(v).get(i);
if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}

if (!update) {
break;
}
}

if (dist[t] >= INF) {
return -1;
}

int d = f;
for (int v = t; v != s; v = prevv[v]) {
d = Math.min(d, G.get(prevv[v]).get(preve[v]).cap);
}

f -= d;
res += d * dist[t];

for (int v = t; v != s; v = prevv[v]) {
Edge e = G.get(prevv[v]).get(preve[v]);
e.cap -= d;
G.get(v).get(e.rev).cap += d;
}

}

return res;
}

public static int[] bestMatching(int[][] costs) {
assert check(costs);

int R = costs.length;
int C = costs[0].length;

MinCostFlow mcf = new MinCostFlow(R + C + 2);

int s = R + C;
int t = s + 1;

for (int r = 0; r < R; r++) {
mcf.addEdge(s, r, 1, 0);
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (costs[r][c] < 0) {
continue;
}
mcf.addEdge(r, R + c, 1, costs[r][c]);
}
}
for (int c = 0; c < C; c++) {
mcf.addEdge(R + c, t, 1, 0);
}

int minCost = mcf.run(s, t, R);

int[] rToC = new int[R];
Arrays.fill(rToC, -1);
for (int r = 0; r < R; r++) {
ArrayList<Edge> edges = mcf.G.get(r);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int c = e.to - R;
rToC[r] = c;
break;
}
}
return rToC;
}

private static boolean check(int[][] costs) {
assert costs.length > 0;
assert costs[0].length > 0;
for (int i = 1; i < costs.length; i++) {
assert costs[i].length == costs[i - 1].length;
}
return true;
}
}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 9.0;
public double time = startTime;

public double startTemperature = 10;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 100;
public double endRange = 5;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? TrucksAndCouriers.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateTime() {
time = useTime ? TrucksAndCouriers.watch.getSecond() : numIterations;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
return acceptS(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (TrucksAndCouriers.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}

assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (TrucksAndCouriers.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

}

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 long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

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

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

}

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 Customer {
int x;
int y;
int item;
}

class Ware {
int x;
int y;
int[] quantity = new int[100];
}

class Truck {
int startX;
int startY;
int destX;
int destY;
ArrayList<Integer> items;

public Truck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
super();
this.startX = startX;
this.startY = startY;
this.destX = destX;
this.destY = destY;
this.items = items;
}
}

class Edge3 {
int to;
int cost;

public Edge3(int to, int cost) {
this.to = to;
this.cost = cost;
}
}

class Edge2 {
int from;
int to;
int cost;

public Edge2(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}

class MinimumSpanningTree {

private static final int INF = (int) 1e9;
public ArrayList<ArrayList<Edge3>> G;
private ArrayList<Edge2> edges;
private int numVertexes;

public MinimumSpanningTree(int v) {
clear(v);
}

public void clear(int v) {
this.numVertexes = v;

if (G == null) {
G = new ArrayList<ArrayList<Edge3>>();
}
for (int i = 0; i < v; i++) {
if (i < G.size()) {
G.get(i).clear();
} else {
G.add(new ArrayList<Edge3>());
}
}
if (edges == null) {
edges = new ArrayList<Edge2>();
} else {
edges.clear();
}
}

public void addEdge(int from, int to, int cost) {
assert cost >= 0;
assert cost <= INF;
edges.add(new Edge2(from, to, cost));
}

private UnionFind unionFind = new UnionFind();

public int kruskal() {
unionFind.init(numVertexes);

Collections.sort(edges, new Comparator<Edge2>() {
@Override
public int compare(Edge2 o1, Edge2 o2) {
if (o1.cost < o2.cost) {
return -1;
}
if (o1.cost > o2.cost) {
return 1;
}
return 0;
}
});

int cost = 0;
int numEdges = 0;
for (Edge2 edge2 : edges) {
if (unionFind.isSame(edge2.from, edge2.to)) {
continue;
}
unionFind.unite(edge2.from, edge2.to);

G.get(edge2.from).add(new Edge3(edge2.to, edge2.cost));
G.get(edge2.to).add(new Edge3(edge2.from, edge2.cost));

cost += edge2.cost;
numEdges++;
if (numEdges >= numVertexes - 1) {
break;
}
}
return cost;
}

public int prim() {

ArrayList<ArrayList<Edge2>> G = new ArrayList<>();
for (int i = 0; i < numVertexes; i++) {
G.add(new ArrayList<>());
}
for (Edge2 edge2 : edges) {
G.get(edge2.from).add(new Edge2(edge2.from, edge2.to, edge2.cost));
G.get(edge2.to).add(new Edge2(edge2.to, edge2.from, edge2.cost));
}

int cost = 0;
int numEdges = 0;

boolean[] used = new boolean[numVertexes];
PriorityQueue<Edge2> pq = new PriorityQueue<>(new Comparator<Edge2>() {
@Override
public int compare(Edge2 o1, Edge2 o2) {
if (o1.cost < o2.cost) {
return -1;
}
if (o1.cost > o2.cost) {
return 1;
}
return 0;
}
});
{
int vertex = (int) (numVertexes * Math.random());
pq.add(new Edge2(vertex, vertex, 0));
}
for (; !pq.isEmpty();) {
Edge2 current = pq.poll();

if (used[current.to]) {
continue;
}

used[current.to] = true;
cost += current.cost;

if (current.from != current.to) {
numEdges++;
if (numEdges == numVertexes - 1) {
break;
}

this.G.get(current.from).add(new Edge3(current.to, current.cost));
this.G.get(current.to).add(new Edge3(current.from, current.cost));
}

for (Edge2 edge : G.get(current.to)) {
if (used[edge.to]) {
continue;
}
pq.add(edge);
}

}

return cost;
}

}

class Point {

public int x;
public int y;

public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}

}

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 Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class UnionFind {
private int[] par;
private int[] rank;

public void init(int n) {
if (par == null || par.length < n) {
par = new int[n];
}
if (rank == null || rank.length < n) {
rank = new int[n];
}
for (int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
}
}

public int getRoot(int x) {
if (par[x] == x) {
return x;
} else {
par[x] = getRoot(par[x]);
return par[x];
}
}

public void unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y) {
return;
}
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}

public boolean isSame(int x, int y) {
return getRoot(x) == getRoot(y);
}
}





Approach beam search を使いました。

  • ケーキを8個以下に切るときは、すべての切り方を試す。そうでないときは、長方形に切る。
  • beam width : 切り方により, 10〜数千まで変わる。
  • 評価関数 : 理想的な切り方ができたときのスコアにした。あと、親のスコアをちょっと足してみた、効果はなかった。
  • 切るケーキの選び方 : 小さいものを選んだ。スコアを早く確定するのが良いらしい。

難しかったところ
  • 高速化しても(beam width を増やしても)精度が良くならなかった。
  • 重複の除去もうまくいってなかった。
  • たまに、切れない形になって、0点を出す。

source code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class CakeSharing {
    private static final double d = 0.01;
    private int count = 0;

    private int R;
    private int C;
    private int numCakes;

    private ArrayList pieces2;
    private ArrayList cuts2;

    public String[] cut(String[] roses, int NP) {
        init(roses, NP);
        solve();
        Utils.debug("count", count);
        return makeSolution();
    }

    TwoDimensionalCumulativeSum cumulativeSum;

    private void init(String[] roses, int NP) {
        Constants.watch.init();

        numCakes = NP;
        R = roses.length;
        H = R;
        C = roses[0].length();
        W = C;

        Utils.debug("R", R, "C", C, "NP", NP);
        this.roses = new char[R][C];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                char charAt = roses[r].charAt(c);
                this.roses[r][c] = charAt;
            }
        }

        {
            int[][] values = new int[R][C];
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    values[r][c] = this.roses[r][c] == 'R' ? 1 : 0;
                }
            }
            cumulativeSum = new TwoDimensionalCumulativeSum(values);
        }

        pieces2 = new ArrayList<>();
        cuts2 = new ArrayList<>();

        ArrayList convexHull = new ArrayList<>();
        convexHull.add(new Point(0, 0));
        convexHull.add(new Point(0, R));
        convexHull.add(new Point(C, R));
        convexHull.add(new Point(C, 0));
        pieces2.add(new Piece(convexHull, true));
    }

    private void solve() {
        ArrayList beamsearch = beamsearch(numCakes - 1, 20);
        set(beamsearch, 0);
    }

    private ArrayList beamsearch(int maxDepth, int maxBeamWidth) {
        double meanArea = R * C / (double) numCakes;
        maxBeamWidth = 10000;
        MeanHelper widthHelper = new MeanHelper();
        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        currents.add(new State());

        double[] timeLimits = getTimeLimits(maxDepth);

        for (int depth = 0; depth < maxDepth; depth++) {
            int beamWidth = Math.min(maxBeamWidth, currents.size());
            Collections.sort(currents);
            widthLoop: for (int width = 0;; width++) {
                if (width >= beamWidth) {
                    widthHelper.add(width);
                    break;
                }

                State currentState = currents.get(width);

                if (depth % 10 == 0) {
                    if (width == 0) {
                        if (currentState != null) {
                            Utils.debug("depth", depth, "score", currentState.score, "currents.size()", currents.size());
                        }
                    }
                }
                set(reverse(toList(currentState)), 0);
                int maxIndex = getPieceIndex();
                Piece piece = pieces2.get(maxIndex);
                int numCakes0 = (int) Math.round(piece.getPieceArea() / meanArea);

                MeanHelper areaHelper = new MeanHelper();
                MeanHelper roseHelper = new MeanHelper();
                for (Piece piece2 : pieces2) {
                    if (piece2 == piece) {
                        continue;
                    }
                    double area = piece2.getPieceArea();
                    int numCakes3 = (int) (Math.round(area / meanArea));
                    minAreaSD(area, numCakes3);
                    areaHelper.add(this.area[0], number[0]);
                    areaHelper.add(this.area[1], number[1]);

                    int rose = piece2.countRose();
                    minRoseSD(rose, numCakes3);
                    roseHelper.add(this.area[0], number[0]);
                    roseHelper.add(this.area[1], number[1]);
                }
                if (numCakes0 > 8 && piece.isRectangle) {
                    int maxX = (int) -1e9;
                    int minX = (int) 1e9;
                    int maxY = (int) -1e9;
                    int minY = (int) 1e9;
                    for (int i = 0; i < piece.convexHull.size(); i++) {
                        Point point = piece.convexHull.get(i);
                        maxX = Math.max(maxX, point.x);
                        minX = Math.min(minX, point.x);
                        maxY = Math.max(maxY, point.y);
                        minY = Math.min(minY, point.y);
                    }

                    for (int r = minY + 1; r < maxY; r++) {
                        Point p1 = new Point(minX, r);
                        Point p2 = new Point(maxX, r);
                        simulateCut(maxIndex, p1, p2);
                        if (areaAndRose[0] == -1) {
                            continue;
                        }

                        if (pruning(meanArea, areaHelper)) {
                            continue;
                        }

                        int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));
                        int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));

                        double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2);

                        setNext(nexts, currentState, piece, p1, p2, expectedScore);
                        if (Constants.watch.getSecond() > timeLimits[depth]) {
                            widthHelper.add(width);
                            break widthLoop;
                        }
                    }
                    for (int c = minX + 1; c < maxX; c++) {
                        Point p1 = new Point(c, minY);
                        Point p2 = new Point(c, maxY);
                        simulateCut(maxIndex, p1, p2);
                        if (areaAndRose[0] == -1) {
                            continue;
                        }

                        if (pruning(meanArea, areaHelper)) {
                            continue;
                        }

                        int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));
                        int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));

                        double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2);

                        setNext(nexts, currentState, piece, p1, p2, expectedScore);
                        if (Constants.watch.getSecond() > timeLimits[depth]) {
                            widthHelper.add(width);
                            break widthLoop;
                        }
                    }
                } else {
                    for (int i = 0; i < piece.pointSize(); i++) {
                        Point p1 = piece.getPoint(i);
                        for (int j = i + 1; j < piece.pointSize(); j++) {
                            Point p2 = piece.getPoint(j);
                            if (numCakes0 > 8) {
                                if (p2.x != p1.x && p2.y != p1.y) {
                                    continue;
                                }
                            }
                            simulateCut(maxIndex, p1, p2);
                            if (areaAndRose[0] == -1) {
                                continue;
                            }

                            if (pruning(meanArea, areaHelper)) {
                                continue;
                            }

                            int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));
                            int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));

                            double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2);

                            setNext(nexts, currentState, piece, p1, p2, expectedScore);
                            if (Constants.watch.getSecond() > timeLimits[depth]) {
                                widthHelper.add(width);
                                break widthLoop;
                            }
                        }
                    }
                }

            }

            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }
        Utils.debug("mean width", widthHelper.mean());

        Collections.sort(currents);
        State best = currents.get(0);

        Utils.debug("time", Constants.watch.getSecondString(), "score", best.score);

        return reverse(toList(best));
    }

    private boolean pruning(double meanArea, MeanHelper areaHelper) {
        int numCakes1p = (int) (Math.round(d + areaAndRose[0] / meanArea));
        int numCakes1m = (int) (Math.round(-d + areaAndRose[0] / meanArea));
        if (numCakes1p != numCakes1m) {
            count++;
            return true;
        }
        int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));

        int numCakes2p = (int) (Math.round(d + areaAndRose[2] / meanArea));
        int numCakes2m = (int) (Math.round(-d + areaAndRose[2] / meanArea));
        if (numCakes2p != numCakes2m) {
            count++;
            return true;
        }
        int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));
        if (areaHelper.count() + numCakes1 + numCakes2 != numCakes) {
            return true;
        }
        if (numCakes1 < 1) {
            return true;
        }
        if (numCakes2 < 1) {
            return true;
        }
        return false;
    }

    private double calculateExpectedScore(MeanHelper areaHelper, MeanHelper roseHelper, int numCakes1, int numCakes2) {
        double expectedScore = 0;
        {
            minAreaSD(areaAndRose[0], numCakes1);
            areaHelper.add(this.area[0], number[0]);
            areaHelper.add(this.area[1], number[1]);
            minAreaSD(areaAndRose[2], numCakes2);
            areaHelper.add(this.area[0], number[0]);
            areaHelper.add(this.area[1], number[1]);
            double sdArea = areaHelper.standardDeviation(1e9);
            areaHelper.add(this.area[0], -number[0]);
            areaHelper.add(this.area[1], -number[1]);
            minAreaSD(areaAndRose[0], numCakes1);
            areaHelper.add(this.area[0], -number[0]);
            areaHelper.add(this.area[1], -number[1]);
            minRoseSD((int) areaAndRose[1], numCakes1);
            roseHelper.add(this.area[0], number[0]);
            roseHelper.add(this.area[1], number[1]);
            minRoseSD((int) areaAndRose[3], numCakes2);
            roseHelper.add(this.area[0], number[0]);
            roseHelper.add(this.area[1], number[1]);
            double sdRose = roseHelper.standardDeviation(1e9);
            roseHelper.add(this.area[0], -number[0]);
            roseHelper.add(this.area[1], -number[1]);
            minRoseSD((int) areaAndRose[1], numCakes1);
            roseHelper.add(this.area[0], -number[0]);
            roseHelper.add(this.area[1], -number[1]);
            expectedScore = (1.0 + sdArea) * (1.0 + sdRose);
            if (Double.isNaN(expectedScore)) {
                expectedScore = 1e9;
            }
        }
        return expectedScore;
    }

    private void setNext(ArrayList nexts, State currentState, Piece piece, Point p1, Point p2, double expectedScore) {
        {
            State nextState = new State();
            nextState.parent = currentState;
            nextState.piece = piece;
            nextState.cut = new Cut(p1, p2);
            nextState.score = 0.9 * expectedScore + 0.1 * currentState.score;
            nexts.add(nextState);
        }
    }

    private double[] area = new double[2];
    private int[] number = new int[2];

    private void minAreaSD(double area, int numCakes) {
        double meanArea = area / (double) numCakes;
        double less = 0.5 * ((int) (2 * meanArea));
        double more = Math.abs(less - meanArea) < 1e-5 ? less : (less + 0.5);

        int numMore = (int) (1e-9 + (area - less * numCakes) / 0.5);
        int numLess = numCakes - numMore;
        this.area[0] = less;
        this.area[1] = more;
        number[0] = numLess;
        number[1] = numMore;
        assert Math.abs(area - (less * numLess + more * numMore)) < 1e-5;
    }

    private void minRoseSD(int rose, int numCakes) {
        double meanRose = rose / (double) numCakes;
        double less = Math.floor(1e-9 + meanRose);
        double more = Math.ceil(-1e-9 + meanRose);

        int numMore = (int) (1e-9 + (rose - less * numCakes));
        int numLess = numCakes - numMore;
        this.area[0] = less;
        this.area[1] = more;
        number[0] = numLess;
        number[1] = numMore;
        assert Math.abs(rose - (less * numLess + more * numMore)) < 1e-5;
    }

    private double[] getTimeLimits(int maxDepth) {
        double[] timeLimits = new double[maxDepth];
        double end = 9.5;
        double start = Constants.watch.getSecond();
        for (int i = 0; i < maxDepth; i++) {
            timeLimits[i] = start + (end - start) * ((i + 1.0) / maxDepth);
        }
        return timeLimits;
    }

    private Piece getMaxAreaPiece() {
        Piece piece = null;
        for (int i = 0; i < pieces2.size(); i++) {
            Piece piece2 = pieces2.get(i);
            if (piece == null || piece2.getPieceArea() > piece.getPieceArea()) {
                piece = piece2;
            }
        }
        return piece;
    }

    private int getMaxAreaPieceIndex() {
        int maxIndex = 0;
        for (int i = 0; i < pieces2.size(); i++) {
            if (pieces2.get(i).getPieceArea() > pieces2.get(maxIndex).getPieceArea()) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    private int getMinAreaPieceIndex() {
        double meanArea = R * C / (double) numCakes;
        int minIndex = -1;
        for (int i = 0; i < pieces2.size(); i++) {
            if (pieces2.get(i).getPieceArea() / meanArea < 1.5) {
                continue;
            }
            if (minIndex == -1 || pieces2.get(i).getPieceArea() < pieces2.get(minIndex).getPieceArea()) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    private int getPieceIndex() {
        double meanArea = R * C / (double) numCakes;
        int bestIndex = -1;
        double bestZ = (int) 1e9;
        for (int i = 0; i < pieces2.size(); i++) {
            Piece piece = pieces2.get(i);
            if (piece.getPieceArea() / meanArea < 1.5) {
                continue;
            }

            int minZ = (int) 1e9;
            int sumZ = 0;
            for (int j = 0; j < piece.convexHull.size(); j++) {
                Point point = piece.convexHull.get(j);
                int z = point.y + point.x;
                minZ = Math.min(minZ, z);
                sumZ += z;
            }
            double meanZ = sumZ / (double) piece.convexHull.size();

            if (bestIndex == -1 || pieces2.get(i).getPieceArea() < pieces2.get(bestIndex).getPieceArea()) {
                bestIndex = i;
                bestZ = meanZ;
            } else if (Math.abs(pieces2.get(i).getPieceArea() - pieces2.get(bestIndex).getPieceArea()) < 1e-5 && meanZ < bestZ) {
                bestIndex = i;
                bestZ = meanZ;
            }
        }
        return bestIndex;
    }

    private double[] areaAndRose = new double[4];

    private void simulateCut(int ind, Point p1, Point p2) {
        if (p1.equals(p2)) {
            areaAndRose[0] = -1;
            return;
        }
        if (!isInside(p1) || !isInside(p2)) {
            areaAndRose[0] = -1;
            return;
        }

        int i1 = -1, i2 = -1;
        Piece piece = pieces2.get(ind);
        i1 = piece.isOnPieceEdge(p1);
        i2 = piece.isOnPieceEdge(p2);
        if (i1 > i2) {
            int t = i2;
            i2 = i1;
            i1 = t;
            Point tmp = p2;
            p2 = p1;
            p1 = tmp;
        }
        ArrayList pnew = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i1 && index < i2) {
                pnew.add(point);
            }
            if (index >= i2) {
                break;
            }
        }
        pnew.add(p2);
        pnew.add(p1);
        Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double anew = newPiece.getPieceArea();
        if (anew < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        double aold = piece.getPieceArea() - newPiece.getPieceArea();
        if (aold < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        ArrayList pold_updated = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index < i1) {
                pold_updated.add(point);
            } else {
                break;
            }
        }
        pold_updated.add(p1);
        pold_updated.add(p2);
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i2) {
                pold_updated.add(point);
            }
        }
        Piece newPiece2 = new Piece(pold_updated, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        areaAndRose[0] = newPiece.getPieceArea();
        areaAndRose[1] = newPiece.countRose();
        areaAndRose[2] = piece.getPieceArea() - newPiece.getPieceArea();
        areaAndRose[3] = newPiece2.countRose();
    }

    private void simulateCutFast(int ind, Point p1, Point p2) {
        if (p1.equals(p2)) {
            areaAndRose[0] = -1;
            return;
        }
        if (!isInside(p1) || !isInside(p2)) {
            areaAndRose[0] = -1;
            return;
        }

        int i1 = -1, i2 = -1;
        Piece piece = pieces2.get(ind);
        i1 = piece.isOnPieceEdge(p1);
        i2 = piece.isOnPieceEdge(p2);
        if (i1 > i2) {
            int t = i2;
            i2 = i1;
            i1 = t;
            Point tmp = p2;
            p2 = p1;
            p1 = tmp;
        }
        ArrayList pnew = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i1 && index < i2) {
                pnew.add(point);
            }
        }
        pnew.add(p2);
        pnew.add(p1);
        Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double anew = newPiece.getPieceArea();
        if (anew < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        double aold = piece.getPieceArea() - newPiece.getPieceArea();
        if (aold < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        areaAndRose[0] = newPiece.getPieceArea();
        areaAndRose[1] = newPiece.countRose();
        areaAndRose[2] = piece.getPieceArea() - newPiece.getPieceArea();
        areaAndRose[3] = piece.countRose() - newPiece.countRose();
    }

    private int turn = 0;

    private void next(Cut cut) {
        makeCut(cut.start, cut.end);
        turn++;
    }

    private void previous() {
        turn--;
        pieces2.set(indHistory[turn], pieceHistory[turn]);
        pieces2.remove(pieces2.size() - 1);
        cuts2.remove(cuts2.size() - 1);
    }

    private void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;

        for (int i = 0; i < list.size() && startIndex + i < cuts2.size(); i++) {
            State state = list.get(i);
            if (state.cut.equals(cuts2.get(startIndex + i))) {
                startIndexMinus1 = startIndex + i;
                continue;
            }
            break;
        }

        for (; turn > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.cut);
        }
    }

    private ArrayList reverse(ArrayList 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 ArrayList toList(State state2) {
        ArrayList res = new ArrayList<>();
        for (State current = state2; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private static int cross(int x, int y, int x2, int y2) {
        return x * y2 - y * x2;
    }

    private String[] makeSolution() {
        ArrayList res = new ArrayList<>();
        for (int i = 0; i < cuts2.size(); i++) {
            Cut cut = cuts2.get(i);
            res.add(cut.start.x + " " + cut.start.y + " " + cut.end.x + " " + cut.end.y);
        }
        return (String[]) res.toArray(new String[res.size()]);
    }

    private int H, W;
    private char[][] roses;
    private Piece[] pieceHistory = new Piece[321];
    private int[] indHistory = new int[321];

    private boolean isInside(Point p) {
        return (p.y >= 0 && p.y <= H && p.x >= 0 && p.x <= W);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private String makeCut(Point p1, Point p2) {
        if (p1.equals(p2)) {
            Utils.debug("A");
            return "The cut must have non-zero length.";
        }
        if (!isInside(p1) || !isInside(p2)) {
            Utils.debug("B");
            return "The cut can not start or end outside the cake.";
        }
        int ind = -1, i1 = -1, i2 = -1;
        for (int i = 0; i < pieces2.size(); ++i) {
            Piece piece = pieces2.get(i);
            i1 = piece.isOnPieceEdge(p1);
            if (i1 == -1)
                continue;
            i2 = piece.isOnPieceEdge(p2);
            if (i2 == -1) {
                i1 = -1;
                continue;
            }
            ind = i;
            break;
        }
        if (ind == -1) {
            Utils.debug("C");
            return "The cut must divide one piece in two pieces.";
        }
        Piece piece = pieces2.get(ind);
        if (i1 > i2) {
            int t = i2;
            i2 = i1;
            i1 = t;
            Point tmp = p2;
            p2 = p1;
            p1 = tmp;
        }

        ArrayList pnew = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i1 && index < i2) {
                pnew.add(point);
            }
            if (index >= i2) {
                break;
            }
        }
        pnew.add(p2);
        pnew.add(p1);
        Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double anew = newPiece.getPieceArea();
        if (anew < 0.25) {
            return "The pieces produced by the cut must have non-zero area.";
        }

        ArrayList pold_updated = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index < i1) {
                pold_updated.add(point);
            } else {
                break;
            }
        }
        pold_updated.add(p1);
        pold_updated.add(p2);
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i2) {
                pold_updated.add(point);
            }
        }
        Piece newPiece2 = new Piece(pold_updated, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double aold = newPiece2.getPieceArea();
        if (aold < 0.25) {
            return "The pieces produced by the cut must have non-zero area.";
        }

        indHistory[turn] = ind;
        pieceHistory[turn] = pieces2.set(ind, newPiece);
        pieces2.add(newPiece2);
        cuts2.add(new Cut(p1, p2));
        return "";
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int size = Integer.parseInt(br.readLine());
            String[] roses = new String[size];
            for (int i = 0; i < size; ++i) {
                roses[i] = br.readLine();
            }

            int NP = Integer.parseInt(br.readLine());

            CakeSharing cs = new CakeSharing();
            String[] ret = cs.cut(roses, NP);

            System.out.println(ret.length);
            for (int i = 0; i < ret.length; ++i) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class Piece {
        ArrayList convexHull;
        IntSet points;
        boolean isRectangle;

        public Piece(ArrayList convexHull, boolean isRectangle) {
            super();
            this.convexHull = convexHull;
            this.isRectangle = isRectangle;
        }

        @Override
        public String toString() {
            return convexHull.toString();
        }

        public boolean isConvexHull(Point point) {
            for (int i = 0; i < convexHull.size(); i++) {
                if (convexHull.get(i).equals(point)) {
                    return true;
                }
            }
            return false;
        }

        public int pointSize() {
            if (points == null) {
                initPoints();
            }
            return points.size();
        }

        public Point getPoint(int i) {
            if (points == null) {
                initPoints();
            }
            int z = points.get(i);
            return new Point(c(z), r(z));
        }

        private int isOnPieceEdge(Point p) {
            if (points == null) {
                initPoints();
            }
            return points.indexOf(z(p.y, p.x));
        }

        private void initPoints() {
            points = new IntSet((R + 1) * (C + 1));
            for (int i = 0; i < convexHull.size(); i++) {
                int j = (i + 1) % convexHull.size();
                Point p1 = convexHull.get(i);
                Point p2 = convexHull.get(j);
                addPointsOnCut(p1, p2);
            }
        }

        private void addPointsOnCut(Point p1, Point p2) {
            assert p1.x != p2.x || p1.y != p2.y : Utils.toString("p1.x", p1.x, "p2.x", p2.x, "p1.y", p1.y, "p2.y", p2.y);
            int dx = p2.x - p1.x, dy = p2.y - p1.y;
            int g = Math.abs(gcd(dx, dy));
            for (int i = 0; i <= g; ++i) {
                int x = p1.x + (dx / g) * i;
                int y = p1.y + (dy / g) * i;
                points.add(z(y, x));
            }
        }

        private double area = -1;

        private double getPieceArea() {
            if (area < 0) {
                area = 0;
                for (int i = 0; i < convexHull.size(); ++i) {
                    Point p1 = convexHull.get(i);
                    Point p2 = convexHull.get((i + 1) % convexHull.size());
                    area += cross(p1.x, p1.y, p2.x, p2.y);
                }
                area = 0.5 * Math.abs(area);
            }
            return area;
        }

        private int countRose = -1;

        private int countRose() {
            if (countRose < 0) {
                int maxX = (int) -1e9;
                int minX = (int) 1e9;
                int maxY = (int) -1e9;
                int minY = (int) 1e9;
                for (int i = 0; i < convexHull.size(); i++) {
                    Point point = convexHull.get(i);
                    maxX = Math.max(maxX, point.x);
                    minX = Math.min(minX, point.x);
                    maxY = Math.max(maxY, point.y);
                    minY = Math.min(minY, point.y);
                }

                if (isRectangle) {
                    countRose = cumulativeSum.cumulativeSum(minY, minX, maxY, maxX);
                } else {
                    int n = 0;
                    for (int r = minY; r < maxY; ++r)
                        for (int c = minX; c < maxX; ++c) {
                            if (roses[r][c] != 'R') {
                                continue;
                            }

                            if (isRoseInsidePiece(new Point(2 * c + 1, 2 * r + 1))) {
                                n++;
                            }
                        }
                    countRose = n;
                }
            }
            return countRose;
        }

        private boolean isRoseInsidePiece(Point point) {
            for (int i = 0; i < convexHull.size(); i++) {
                Point p = convexHull.get(i);
                Point p2 = convexHull.get((i + 1) % convexHull.size());
                if (cross(2 * (p2.x - p.x), 2 * (p2.y - p.y), point.x - 2 * p.x, point.y - 2 * p.y) >= 0) {
                    return false;
                }
            }
            return true;
        }

    }

    private int c(int z) {
        return z % (C + 1);
    }

    private int r(int z) {
        return z / (C + 1);
    }

    private int z(int r, int c) {
        return r * (C + 1) + c;
    }

    class State implements Comparable {
        State parent;
        Piece piece;
        Cut cut;
        double score;

        @Override
        public int compareTo(State o) {
            if (score < o.score) {
                return -1;
            }
            if (score > o.score) {
                return 1;
            }
            return 0;
        }

    }

}

class Constants {
    public static final XorShift rng = new XorShift(System.nanoTime());
    public static final Watch watch = new Watch();
}

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 long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

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

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

}

class IntSet {
    private static final int EMPTY = -1;
    private int size;
    private int[] indexToValue;
    private int[] valueToIndex;

    public IntSet(int capacity) {
        this.size = 0;
        indexToValue = new int[capacity];
        valueToIndex = new int[capacity];
        Arrays.fill(valueToIndex, EMPTY);
    }

    public boolean add(int value) {
        assert value < valueToIndex.length : Utils.toString("value", value, "valueToIndex.length", valueToIndex.length);
        if (valueToIndex[value] != EMPTY) {
            return false;
        }
        indexToValue[size] = value;
        valueToIndex[indexToValue[size]] = size;
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[size - 1];
        indexToValue[size - 1] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[size - 1]] = EMPTY;

        size--;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int get(int index) {
        return indexToValue[index];
    }

    public int indexOf(int value) {
        return valueToIndex[value];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

}

class Point {
    public int x, y;

    public Point(int px, int py) {
        x = px;
        y = py;
    }

    public boolean equals(Point p) {
        return x == p.x && y == p.y;
    }

    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

class Cut {
    public Point start, end;

    public Cut(Point s, Point e) {
        start = s;
        end = e;
    }

    public Cut(int x1, int y1, int x2, int y2) {
        start = new Point(x1, y1);
        end = new Point(x2, y2);
    }

    public boolean equals(Cut obj) {
        return (start.equals(obj.start) && end.equals(obj.end)) || (start.equals(obj.end) && end.equals(obj.start));
    }

    public String toString() {
        return start + " - " + end;
    }
}

class Pair, S> implements Comparable> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair other = (Pair) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair o) {
        return first.compareTo(o.first);
    }
}

class MeanHelper {
    private double max;
    private double min;
    private double sum;
    private double sumSquared;
    private double sumCubed;
    private double sumFourth;
    private int count;

    public MeanHelper() {
        clear();
    }

    public void add(double value) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value;
        double valueSquared = value * value;
        sumSquared += valueSquared;
        sumCubed += valueSquared * value;
        sumFourth += valueSquared * valueSquared;
        count++;
    }

    public void add(double value, int number) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value * number;
        double valueSquared = value * value;
        sumSquared += valueSquared * number;
        sumCubed += valueSquared * value * number;
        sumFourth += valueSquared * valueSquared * number;
        count += number;
    }

    public double kurtosis(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
    }

    public double skewness(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
    }

    public double mean() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sum / count;
    }

    public double mean(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sum / count;
    }

    public double sumOfSquaredError() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sumSquared - sum * sum / count;
    }

    public double sumOfSquaredError(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sumSquared - sum * sum / count;
    }

    public double variance() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double variance(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double unbiasedVariance() {
        if (count - 1 == 0) {
            throw new AssertionError();
        }
        return (count * variance()) / (count - 1);
    }

    private double unbiasedVariance(double defaultValue) {
        if (count - 1 == 0) {
            return defaultValue;
        }
        return (count * variance()) / (count - 1);
    }

    public double standardDeviation() {
        return Math.sqrt(variance());
    }

    public double standardDeviation(double defaultValue) {
        double variance = variance(defaultValue);
        if (Math.abs(variance) < 1e-9) {
            return 0;
        }
        return Math.sqrt(variance);
    }

    public double unbiasedStandardDeviation() {
        return Math.sqrt(unbiasedVariance());
    }

    public double unbiasedStandardDeviation(double defaultValue) {
        return Math.sqrt(unbiasedVariance(defaultValue));
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void clear() {
        max = Double.NEGATIVE_INFINITY;
        min = Double.POSITIVE_INFINITY;
        sum = 0;
        sumSquared = 0;
        sumCubed = 0;
        sumFourth = 0;
        count = 0;
    }

    public double max() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return max;
    }

    public double max(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return max;
    }

    public double min() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return min;
    }

    public double min(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return min;
    }

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}

class TwoDimensionalCumulativeSum {
    private int[][] sum;

    public TwoDimensionalCumulativeSum(int[][] values) {
        int R = values.length;
        int C = values[0].length;
        sum = new int[R + 1][C + 1];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                sum[r + 1][c + 1] = sum[r + 1][c] + sum[r][c + 1] - sum[r][c] + values[r][c];
            }
        }
    }

    public int cumulativeSum(int startRInclusive, int startCInclusive, int endRExclusive, int endCExclusive) {
        return sum[startRInclusive][startCInclusive] - sum[endRExclusive][startCInclusive] - sum[startRInclusive][endCExclusive] + sum[endRExclusive][endCExclusive];
    }
}


このページのトップヘ