ACM ICPCファイナルの1つからの問題の1つを解決する方法を見つけようとしています(2012年からなので、最新だと思います)。これはフィボナッチ ワードと呼ばれ、問題 Dで説明されています。
最後のテストケースを除くすべてのテストケースが正しい答えを出しているので、私は非常に近いと思います。しかし、最後に、6440026026380244497 を得ています。これは正しい大きさの桁ですが、それでもかなりずれています。大きさの桁が大きいためです。:)
これが私のJavaコードで、多くのコメントがあります(多すぎると思いますか?リファクタリングできますか?):
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class FibonacciWords {
public static StringBuilder[] updateChars(StringBuilder lastOneBack, StringBuilder firstTwoBack, StringBuilder lastTwoBack, StringBuilder firstThreeBack) {
int pattLen = lastOneBack.length();
StringBuilder[] newChars = new StringBuilder[2];
newChars[0] = new StringBuilder(pattLen); // will become the new lastOneBack!
newChars[1] = new StringBuilder(pattLen); // will become the new firstTwoBack!
if(lastOneBack.charAt(0) == 'E') { // lastOneBack not full yet
int shiftCharsBy = 0; // holds amount to shift lastOneBack by
for(int i = 0; i < pattLen; i++) {
if(firstTwoBack.charAt(i) != 'E') {
shiftCharsBy++; // need to move whatever is at beginning of firstTwoBack to end of lastOneBack
} else {
break; // when first 'E' is reached in firstTwoBack, the rest are 'E' also
}
}
for(int i = 0; i < pattLen-shiftCharsBy; i++) {
newChars[0].append(lastOneBack.charAt(i+shiftCharsBy)); // shift lastOneBack by shiftCharsBy characters
}
for(int i = 0; i < shiftCharsBy; i++) {
newChars[0].append(firstTwoBack.charAt(i)); // fill remainder of new lastOneBack with what's in firstTwoBack
}
} else { // lastOneBack already full
newChars[0] = lastTwoBack; // make lastOneBack lastTwoBack (following pattern)
}
if(firstTwoBack.charAt(pattLen-1) == 'E') { // firstTwoBack not full yet
if(lastOneBack.charAt(0) == 'E') {
for(int i = 1; i < pattLen; i++) {
if(lastOneBack.charAt(i) != 'E') {
newChars[1].append(lastOneBack.substring(i)); // move last characters of lastOneBack to front of new firstTwoBack
break;
}
}
int charsAdded = newChars[1].length();
for(int i = 0; i < pattLen-charsAdded; i++) {
newChars[1].append('E'); // fill whatever might remain with 'E'
}
} else {
//newChars[1] = lastOneBack;
for(int i = 0; i < pattLen; i++) {
if(firstTwoBack.charAt(i) != 'E') {
newChars[1].append(firstTwoBack.charAt(i));
} else {
break;
}
}
int charsAdded = newChars[1].length();
// now take from firstThreeBack--which also isn't full if firstTwoBack isn't--until pattLen is reached
for(int i = 0; i < pattLen-charsAdded; i++) {
newChars[1].append(firstThreeBack.charAt(i));
}
}
} else {
newChars[1] = firstTwoBack; // firstTwoBack doesn't change when already full
}
return newChars;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String pattern = br.readLine();
long numPattTwoPrior = 0; // number of times pattern occurred in F(n-2)
if(pattern.equals("0")) {
numPattTwoPrior++; // since n starts at 2 below, increment this if pattern is F(0), or "0"
}
long numPattOnePrior = 0; // number of times pattern occurred in F(n-1)
if(pattern.equals("1")) {
numPattOnePrior++; // since n starts at 2 below, increment this if pattern is F(1), or "1"
}
int pattLen = pattern.length();
StringBuilder lastCharsInOnePrior = new StringBuilder(pattLen); // keeps track of last pattLen characters in F(n-1)
for(int i = 0; i < pattLen; i++) {
lastCharsInOnePrior.append('E'); // 'E' stands for empty
}
lastCharsInOnePrior.setCharAt(pattLen-1, '1'); // since F(1) = "1"
StringBuilder firstCharsInTwoPrior = new StringBuilder(pattLen);
for(int i = 0; i < pattLen; i++) {
firstCharsInTwoPrior.append('E');
}
firstCharsInTwoPrior.setCharAt(0, '0'); // since F(0) = "0"
StringBuilder lastCharsInTwoPrior = null; // last characters always the same as 2 back, so keep track of this
StringBuilder firstCharsInThreePrior = null; // used for special case in updateChars
// number of times pattern occurs in F(n)
long numPattCurr = (n == 0) ? numPattTwoPrior : (n == 1) ? numPattOnePrior : 0;
for(int i = 2; i <= n; i++) { // finding F(n) up to the n given by the input
numPattCurr = numPattTwoPrior + numPattOnePrior; // at least this many times in F(n)
// adding to above all patterns found as part of concatenating F(n-1) and F(n-2), but not either on its own
middle:
for(int j = 1; j < pattLen; j++) { // starting at pos. 1 b/c [0, pattLen) is all F(n-1)
if(lastCharsInOnePrior.charAt(j) == 'E') {
continue;
}
StringBuilder compareWith = new StringBuilder(pattLen); // to compare with pattern
for(int k = 0; k < pattLen; k++) {
if(j + k >= pattLen) { // reached end of characters in F(n-1), start checking F(n-2)
int posInFirstChars = (j + k) % pattLen;
if(firstCharsInTwoPrior.charAt(posInFirstChars) == 'E') {
break middle; // none of the remaining overlap between F(n-1) and F(n-2) is as long as pattern, so can stop here
} else {
compareWith.append(firstCharsInTwoPrior.charAt(posInFirstChars));
}
} else {
compareWith.append(lastCharsInOnePrior.charAt(j + k));
}
}
if(pattern.equals(compareWith.toString())) {
numPattCurr++; // this overlap matched pattern
}
}
// changing characters of F(n-1) and F(n-2), as needed, for next iteration
StringBuilder[] updatedChars = updateChars(lastCharsInOnePrior, firstCharsInTwoPrior, lastCharsInTwoPrior, firstCharsInThreePrior);
lastCharsInTwoPrior = lastCharsInOnePrior;
firstCharsInThreePrior = firstCharsInTwoPrior;
lastCharsInOnePrior = updatedChars[0];
firstCharsInTwoPrior = updatedChars[1];
// changing number of times pattern found for F(n-1) and F(n-2) for next iteration
numPattTwoPrior = numPattOnePrior;
numPattOnePrior = numPattCurr;
}
System.out.println(numPattCurr);
System.exit(0);
}
}
コメント付きのコードを 1 行だけ残したと思いますが、else ブロック内の唯一の行である場合、すべてのテスト ケースでまったく同じ回答が得られましたが、それを置き換えた方がより正確です。
不足しているものや、最後のテスト ケースをデバッグする方法について何か提案はありますか? または、コンテストの準備中またはアルゴリズムの学習に取り組んでいるため、誰かと話し合うことに興味がありますか? 私にお知らせください。