Zgodnie z prośbą Luke'a i dodatkiem Petera Taylora do tego wyzwania.

Wprowadzenie

Wszyscy znają grę w kółko i krzyżyk, ale w tym wyzwaniu wprowadzimy mały zwrot akcji. Będziemy używać tylko krzyży . Pierwsza osoba, która stawia trzy krzyże z rzędu, przegrywa. Ciekawym faktem jest to, że maksymalna liczba krzyży, zanim ktoś straci, wynosi 6 :

X X -
X - X
- X X

Oznacza to, że dla planszy 3 x 3 maksymalna kwota wynosi 6 . Więc dla N = 3 musimy wyprowadzić 6.

Kolejny przykład, dla N = 4 lub płyty 4 x 4:

X X - X
X X - X
- - - -
X X - X

To optymalne rozwiązanie, widać, że maksymalna liczba krzyży wynosi 9 . Optymalne rozwiązanie dla płyty 12 x 12 to:

X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X

Daje to 74 .

Zadanie

Twoim zadaniem jest jak najszybsze obliczenie wyników. Uruchomię twój kod na przypadku testowym 13. Zostanie to wykonane 5 razy, a następnie zostanie pobrana średnia z czasów pracy. To twój końcowy wynik. Im niższy, tym lepiej.

Przypadki testowe

N     Output
1       1
2       4
3       6
4       9
5       16
6       20
7       26
8       36
9       42
10      52
11      64
12      74
13      86
14      100
15      114

Więcej informacji można znaleźć na https://oeis.org/A181018 .

Zasady

• Jest to najszybszy kod , więc najszybsze zgłoszenie wygrywa!
• Musisz podać pełny program .
• Podaj także, jak mam uruchomić program. Nie znam wszystkich języków programowania i sposobu ich działania, dlatego potrzebuję tutaj trochę pomocy.
• Oczywiście Twój kod musi obliczyć poprawny wynik dla każdego przypadku testowego.

Zgłoszenia:

• feersum (C ++ 11): 28s
• Peter Taylor (Java): 14m 31s

C ++ 11, 28s

Wykorzystuje to także dynamiczne podejście programistyczne oparte na wierszach. Uruchomienie argumentu 13 zajęło mi 28 sekund. Moją ulubioną sztuczką jest nextfunkcja, która używa nieco bashowania w celu znalezienia leksykograficznie uporządkowanego następnego wiersza spełniającego maskę i reguły „3 w jednym rzędzie”.

Instrukcje

1. Zainstaluj najnowszą wersję MinGW-w64 z gwintami SEH i Posix
2. Skompiluj program za pomocą g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
3. Biegnij z <executable name> <n>

#include <vector>
#include <stddef.h>
#include <iostream>
#include <string>

#ifdef _MSC_VER
#include <intrin.h>
#define popcount32 _mm_popcnt_u32
#else
#define popcount32 __builtin_popcount
#endif


using std::vector;

using row = uint32_t;
using xcount = uint8_t;

uint16_t rev16(uint16_t x) { // slow
    static const uint8_t revbyte[] {0,128,64,192,32,160,96,224,16,144,80,208,48,176,112,240,8,136,72,200,40,168,104,232,24,152,88,216,56,184,120,248,4,132,68,196,36,164,100,228,20,148,84,212,52,180,116,244,12,140,76,204,44,172,108,236,28,156,92,220,60,188,124,252,2,130,66,194,34,162,98,226,18,146,82,210,50,178,114,242,10,138,74,202,42,170,106,234,26,154,90,218,58,186,122,250,6,134,70,198,38,166,102,230,22,150,86,214,54,182,118,246,14,142,78,206,46,174,110,238,30,158,94,222,62,190,126,254,1,129,65,193,33,161,97,225,17,145,81,209,49,177,113,241,9,137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,5,133,69,197,37,165,101,229,21,149,85,213,53,181,117,245,13,141,77,205,45,173,109,237,29,157,93,221,61,189,125,253,3,131,67,195,35,163,99,227,19,147,83,211,51,179,115,243,11,139,75,203,43,171,107,235,27,155,91,219,59,187,123,251,7,135,71,199,39,167,103,231,23,151,87,215,55,183,119,247,15,143,79,207,47,175,111,239,31,159,95,223,63,191,127,255};
    return uint16_t(revbyte[x >> 8]) | uint16_t(revbyte[x & 0xFF]) << 8;
}

// returns the next number after r that does not overlap the mask or have three 1's in a row
row next(row r, uint32_t m) {
    m |= r >> 1 & r >> 2;
    uint32_t x = (r | m) + 1;
    uint32_t carry = x & -x;
    return (r | carry) & -carry;
}

template<typename T, typename U> void maxequals(T& m, U v) {
    if (v > m)
        m = v;
}

struct tictac {
    const int n;
    vector<row> rows;
    size_t nonpal, nrows_c;
    vector<int> irow;
    vector<row> revrows;

    tictac(int n) : n(n) { }

    row reverse(row r) {
        return rev16(r) >> (16 - n);
    }

    vector<int> sols_1row() {
        vector<int> v(1 << n);
        for (uint32_t m = 0; !(m >> n); m++) {
            auto m2 = m;
            int n0 = 0;
            int score = 0;
            for (int i = n; i--; m2 >>= 1) {
                if (m2 & 1) {
                    n0 = 0;
                } else {
                    if (++n0 % 3)
                        score++;
                }
            }
            v[m] = score;
        }
        return v;
    }

    void gen_rows() {
        vector<row> pals;
        for (row r = 0; !(r >> n); r = next(r, 0)) {
            row rrev = reverse(r);
            if (r < rrev) {
                rows.push_back(r);
            } else if (r == rrev) {
                pals.push_back(r);
            }
        }
        nonpal = rows.size();
        for (row r : pals) {
            rows.push_back(r);
        }
        nrows_c = rows.size();
        for (int i = 0; i < nonpal; i++) {
            rows.push_back(reverse(rows[i]));
        }
        irow.resize(1 << n);
        for (int i = 0; i < rows.size(); i++) {
            irow[rows[i]] = i;
        }
        revrows.resize(1 << n);
        for (row r = 0; !(r >> n); r++) {
            revrows[r] = reverse(r);
        }
    }

    // find banned locations for 1's given 2 above rows
    uint32_t mask(row a, row b) {
        return ((a & b) | (a >> 1 & b) >> 1 | (a << 1 & b) << 1) /*& ((1 << n) - 1)*/;
    }

    int calc() {
        if (n < 3) {
            return n * n;
        }
        gen_rows();
        int tdim = n < 5 ? n : (n + 3) / 2;
        size_t nrows = rows.size();
        xcount* t = new xcount[2 * nrows * nrows_c]{};
#define tb(nr, i, j) t[nrows * (nrows_c * ((nr) & 1) + (i)) + (j)]

        // find optimal solutions given 2 rows for n x k grids where 3 <= k <= ceil(n/2) + 1

        {
            auto s1 = sols_1row();
            for (int i = 0; i < nrows_c; i++) {
                row a = rows[i];
                for (int j = 0; j < nrows; j++) {
                    row b = rows[j];
                    uint32_t m = mask(b, a) & ~(1 << n);
                    tb(3, i, j) = s1[m] + popcount32(a << 16 | b);
                }
            }
        }
        for (int r = 4; r <= tdim; r++) {
            for (int i = 0; i < nrows_c; i++) {
                row a = rows[i];
                for (int j = 0; j < nrows; j++) {
                    row b = rows[j];
                    bool rev = j >= nrows_c;
                    auto cj = rev ? j - nrows_c : j;
                    uint32_t m = mask(a, b);
                    for (row c = 0; !(c >> n); c = next(c, m)) {
                        row cc = rev ? revrows[c] : c;
                        int count = tb(r - 1, i, j) + popcount32(c);
                        maxequals(tb(r, cj, irow[cc]), count);
                    }
                }
            }
        }
        int ans = 0;
        if (tdim == n) { // small sizes
            for (int i = 0; i < nrows_c; i++) {
                for (int j = 0; j < nrows; j++) {
                    maxequals(ans, tb(n, i, j));
                }
            }
        } else {
            int tdim2 = n + 2 - tdim;
            // get final answer by joining two halves' solutions down the middle
            for (int i = 0; i < nrows_c; i++) {
                int apc = popcount32(rows[i]);
                for (int j = 0; j < nrows; j++) {
                    row b = rows[j];
                    int top = tb(tdim2, i, j);
                    int bottom = j < nrows_c ? tb(tdim, j, i) : tb(tdim, j - nrows_c, i < nonpal ? i + nrows_c : i);
                    maxequals(ans, top + bottom - apc - popcount32(b));
                }
            }
        }
        delete[] t;
        return ans;
    }
};


int main(int argc, char** argv) {
    int n;
    if (argc < 2 || (n = std::stoi(argv[1])) < 0 || n > 16) {
        return 1;
    }
    std::cout << tictac{ n }.calc() << '\n';
    return 0;
}

Java, 14m 31s

Jest to zasadniczo program, który wysłałem do OEIS po użyciu go do przedłużenia sekwencji, więc jest to dobre odniesienie dla innych osób do pokonania. Poprawiłem go tak, aby przyjmował rozmiar tablicy jako pierwszy argument wiersza poleceń.

public class A181018 {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.println(calc(n));
    }

    private static int calc(int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        if (n < 3) return n * n;

        // Dynamic programming approach: given two rows, we can enumerate the possible third row.
        // sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
        int[] rows = buildRows(n);
        byte[] sc = new byte[rows.length * rows.length];
        for (int j = 0, k = 0; j < rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i < rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

        int max = 0;
        for (int h = 2; h < n; h++) {
            byte[] nsc = new byte[rows.length * rows.length];
            for (int i = 0; i < rows.length; i++) {
                int p = rows[i];
                for (int j = 0; j < rows.length; j++) {
                    int q = rows[j];
                    // The rows which follow p,q cannot intersect with a certain mask.
                    int mask = (p & q) | ((p << 2) & (q << 1)) | ((p >> 2) & (q >> 1));
                    for (int k = 0; k < rows.length; k++) {
                        int r = rows[k];
                        if ((r & mask) != 0) continue;

                        int pqrsc = (sc[i + rows.length * j] & 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc > nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc > max) max = pqrsc;
                    }
                }
            }

            sc = nsc;
        }

        return max;
    }

    private static int[] buildRows(int n) {
        // Array length is a tribonacci number.
        int c = 1;
        for (int a = 0, b = 1, i = 0; i < n; i++) c = a + (a = b) + (b = c);

        int[] rows = new int[c];
        int i = 0, j = 1, val;
        while ((val = rows[i]) < (1 << (n - 1))) {
            if (val > 0) rows[j++] = val * 2;
            if ((val & 3) != 3) rows[j++] = val * 2 + 1;
            i++;
        }

        return rows;
    }
}

Zapisz do A181018.java; skompiluj jako javac A181018.java; uruchomić jako java A181018 13. Na moim komputerze wykonanie tego wejścia zajmuje około 20 minut. Prawdopodobnie warto by to zrównoważyć.