必要な 1 秒の応答時間を達成するために従うことができる戦略を指摘しようとします。もちろん、この要件を満たすように実装する必要があります。
解決策は、次の事実に依存しています。
基本的に、位置 P の加重距離 WP の合計が与えられると、各モンスターは、その強さの 1 倍を WP に加算または減算することによって、P 近隣の加重距離の合計に寄与します。隣人が P よりモンスターに近ければ強さが加算され、遠ければ減ります。
この事実を念頭に置いて、解決策は、最初のステップでいくつかの初期位置の加重距離の合計を計算し、他の位置の加重距離の合計を、その近傍について以前に計算された値に基づいて計算することにあります。
初期位置の値を計算するだけでなく、初期ステップで次のように定義する必要があります。
- 加重距離の合計を計算するために位置をトラバースする方向 (時計回りなど)
- 定義された方向にトラバースするときに、モンスターの強さ (SADD) の合計 (追加)。
- 定義された方向にトラバースするときに近づく (差し引く) モンスターの強さ (SSUB) の合計。
次に、最初の位置の隣から始めて、定義された方向のすべての位置をトラバースし、それぞれについて、SADD と SSUB を更新します (円形のパスをトラバースすると、近づいていたモンスターが遠ざかり始め、逆に近づき始めます)。逆）、（SADD - SSUB）を前のネイバーに対して計算された値に追加します。
したがって、位置ごとにすべてのモンスターを反復することなく、すべての位置の加重距離の合計を計算できます。
Java でソリューションの初期バージョンを実装しました。
次のクラスはモンスターを表します。
class Monster {
private long strenght;
private int position;
// omitting getters and setters...
}
次のクラスは、正方形の辺の位置を表します。
class SquareSidePositions {
private List<Monster>[] positionWithMosters;
private List<Monster> monstersOnSquareSides = new ArrayList<Monster>();
@SuppressWarnings("unchecked")
public SquareSidePositions(int numberOfPositions) {
positionWithMosters = new LinkedList[numberOfPositions];
}
public void add(int position, Monster monster) {
if (positionWithMosters[position] == null) {
positionWithMosters[position] = new LinkedList<Monster>();
}
positionWithMosters[position].add(monster);
monster.setPosition(position);
monstersOnSquareSides.add(monster);
}
public int size() {
return positionWithMosters.length;
}
public boolean hasMonsters(int position) {
return positionWithMosters[position] != null;
}
public long getSumOfStrenghtsOfMonstersOnThePosition(int i) {
long sum = 0;
for (Monster monster : positionWithMosters[i]) {
sum += monster.getStrenght();
}
return sum;
}
public List<Monster> getMonstersOnSquareSides() {
return monstersOnSquareSides;
}
}
最後に、最適化は次の方法で実行されます。
public static int findBest(SquareSidePositions positions) {
long tini = System.currentTimeMillis();
long sumOfGettingNearer = 0;
long sumOfGettingFarther = 0;
int currentBestPosition;
long bestSumOfWeight = 0;
long currentSumOfWeight;
final int numberOfPositions = positions.size();
int halfNumberOfPositions = numberOfPositions/2;
long strenghtsOnPreviousPosition = 0;
long strenghtsOnCurrentPosition = 0;
long strenghtsOnPositionStartingGetNearer = 0;
int positionStartGetNearer;
// initial step. Monsters from initial position (0) are skipped because they are at distance 0
for (Monster monster : positions.getMonstersOnSquareSides()) {
// getting nearer
if (monster.getPosition() < halfNumberOfPositions) {
bestSumOfWeight += monster.getStrenght()*monster.getPosition();
sumOfGettingNearer += monster.getStrenght();
} else {
// getting farther
bestSumOfWeight += monster.getStrenght()*(numberOfPositions - monster.getPosition());
sumOfGettingFarther += monster.getStrenght();
}
}
currentBestPosition = 0;
currentSumOfWeight = bestSumOfWeight;
// computing sum of weighted distances for other positions
for (int i = 1; i < numberOfPositions; ++i) {
strenghtsOnPreviousPosition = 0;
strenghtsOnPositionStartingGetNearer = 0;
strenghtsOnCurrentPosition = 0;
positionStartGetNearer = (halfNumberOfPositions + i - 1);
if (positionStartGetNearer >= numberOfPositions) {
positionStartGetNearer -= numberOfPositions;
}
// monsters on previous position start to affect current and next positions, starting to get farther
if (positions.hasMonsters(i-1)) {
strenghtsOnPreviousPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i-1);
sumOfGettingFarther += strenghtsOnPreviousPosition;
}
// monsters on current position will not affect current position and stop to get nearer
if (positions.hasMonsters(i)) {
strenghtsOnCurrentPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i);
currentSumOfWeight -= strenghtsOnCurrentPosition;
sumOfGettingNearer -= strenghtsOnCurrentPosition;
}
// monsters on position next to a half circuit start to get nearer
if (positions.hasMonsters(positionStartGetNearer)) {
strenghtsOnPositionStartingGetNearer = positions.getSumOfStrenghtsOfMonstersOnThePosition(positionStartGetNearer);
sumOfGettingNearer += strenghtsOnPositionStartingGetNearer;
sumOfGettingFarther -= strenghtsOnPositionStartingGetNearer;
}
currentSumOfWeight += sumOfGettingFarther - sumOfGettingNearer;
// if current is better than previous best solution
if (currentSumOfWeight > bestSumOfWeight) {
bestSumOfWeight = currentSumOfWeight;
currentBestPosition = i;
}
}
final long executionTime = System.currentTimeMillis() - tini;
System.out.println("Execution time: " + executionTime + " ms");
System.out.printf("best position: %d with sum of weighted distances: %d\n", currentBestPosition, bestSumOfWeight);
return currentBestPosition;
}
例として使用した入力をセットアップするには、次を使用できます。
SquareSidePositions positions = new SquareSidePositions(12);
positions.add(1, new Monster(3));
positions.add(3, new Monster(1));
positions.add(10, new Monster(1));
positions.add(11, new Monster(2));
予備テストでは、Windows 7 を実行している Intel Core i5-2400 で、100,000 のモンスターと 200,000,000 の可能な位置に対して、このメソッドの実行に 771 ミリ秒かかりました。
この入力を生成するために、次のコードを使用しました。
// I used numberOfMosters == 100000 and numberOfPositions == 200000000
public static SquareSidePositions initializeMonstersOnPositions(int numberOfMonsters, int numberOfPositions) {
Random rand = new Random();
SquareSidePositions positions = new SquareSidePositions(numberOfPositions);
for (int i = 0; i < numberOfMonsters; ++i) {
Monster monster = new Monster(rand.nextInt(10000)+1);
positions.add(rand.nextInt(numberOfPositions), monster);
}
return positions;
}
お役に立てば幸いです。