SuperCon予選

やったこと

  • 眺めているとすごく難しそう

  • まあ考えていると(0, 0)からDFSではいができることに気づく

  • 実装する

  • 自明に「今までの距離 + 現在地から原点までの最短距離 > n」が成り立つ時はアなので枝刈り

  • DFSはstackを使ったほうが速いらしい

  • これは罠で実装が出来なかった

  • inlineをつけると1.5倍ぐらい早くなった

  • 原点の4近傍の点が障害物もしくはもう通った点で埋まっていれば戻ってこれないので枝刈り

  • ここらへんで高速化のアイデアが尽きる

  • 少し考えると答えがm<= 2ぐらいまでなら埋め込めることに気づく

  • さらに考えると原点からの距離がn / 2以上の障害物は関係ないのでmの値を減らせる

  • 答えを埋め込む

  • ここでバグりまくる

  • 最終的に添え字の"[]"の位置が間違っていることに気づく

  • とりあえず m = 0, 1(0というのは答えに関係のある障害物が無い時)の答えを埋め込む

  • m = 2の時を埋め込む

  • 死ぬほどつらいのでn = 20, m= 2の時に絞る

  • i7-6700が頑張る

  • 3,40分で答えが出る

  • 埋め込む

  • 応募用紙を書く

  • 提出する

テストケースの実行結果

Ans= 133662, time=19

ソースコード

#include "sc1.h"
#include "stdio.h"
#include <iostream>

using namespace std;

int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};

int ans = 0, cnt = 0, cnt1;
int index2[20];
bool mas[100][100], flag[100][100];
const int offset = 50;

int index[21][21] = // 2*10^6 以上あるので省略

inline void dfs(int x, int y, int l){
    if(mas[51][50] && mas[49][50] && mas[50][49] && mas[50][51]) return;
    if(scN - l < abs(offset - x) + abs(offset - y)) return;
    mas[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!mas[nx][ny]) dfs(nx, ny, l + 1);
        if(l + 1 == scN && nx == 0 + offset && ny == 0 + offset) ++ans;
    }
    mas[x][y] = false;
}

int main(){
    scInput();
    for(int i = 0; i < 100; ++i) for(int j = 0; j < 100; ++j){
        mas[i][j] = false;
    }
    for(int i = 0; i < scM; ++i){
        if(abs(scB[0][i]) + abs(scB[1][i]) > scN / 2) continue;
        mas[scB[0][i] + offset][scB[1][i] + offset] = true;
        cnt1 = i;
        index2[cnt] = i;
        ++cnt;
    }
    if(cnt == 0){
        scOutput(ans0[scN / 2 - 7]);
        return 0;
    }
    if(cnt == 1){
        scOutput(ans1[scN / 2 - 7][index[scB[0][cnt1] + 10][scB[1][cnt1] + 10]]);
        return 0;
    }
    if(cnt == 2 && scN == 20){
        int ax = scB[0][index2[0]], ay = scB[1][index2[0]];
        int bx = scB[0][index2[1]], by = scB[1][index2[1]];
        int a = index[ax + 10][ay + 10], b = index[bx + 10][by + 10];
        if(a > b) swap(a, b);
        scOutput(ans20_2[a][b - a - 1]);
        return 0;
    }
    mas[offset][offset] = true;
    dfs(0 + offset, 0 + offset, 0);
    scOutput(ans);
}

感想

正直定数倍高速化コンテスト感が強かった

チーム名はaldas(リパライン語で雷雲の意)です　かっこいいね(@sashimiwiki さんに付けて頂きました ありがとうございます！)