SuperCon 2022 予選参加記

はじめに

3 回目のSuperConです． 今回の問題はここにあります．

https://www.gsic.titech.ac.jp/supercon/main/attwiki/index.php?plugin=attach&refer=SupercomputingContest2022&openfile=SuperCon2022Yosen20220606B2033.pdf

問題概要

のマス目それぞれに から までの数字が書き込まれており，座標 の数字は である．

時刻 には座標 にロボットがあって，あなたは時刻が 進むことに上下左右隣接するマスにロボットを進めることができる．(時刻 でのロボットの位置を とする．)

各時刻においての目標の色のパターン が与えられるので，ロボットの進路を好きに決め，コスト関数 を最小化せよ．

書いたアルゴリズム

DP をして復元する方針とダイクストラ (または 0-1BFS っぽいもの) をする方針があると思いますが，DPの方針を取りました． 単純に時刻とその時のロボットの場所をキーにしてそこまでのコスト関数を持てばよいです．

ただこのままだとおもしろくなかったので，SIMD 化して，各行の処理を並列して実行するようにしました． 問題文の実行環境の欄にある「2.8 GHz Intel Core i5」という情報だけだとどの世代かがわからなかったので，sse4.2 相当対応の CPU で動くようにしています．

また， のように座標をいい感じに変換することで，やや計算量が下がります．(各行 の回数が 回減る．)

座標変換のイメージ

実行時間

手元で ケースあたり平均 秒でした．(標準偏差 秒) 愚直な DP 解が ケースあたり 秒だったのでかなり高速だと思います．

提出コード

#include <immintrin.h>

#include <algorithm>

#include "sc1.h"

inline int to_index(int x, int y) { return (x * SC_L + y); }

inline __m128i get_rotate_perm(int n, int r, int l) {
    alignas(32) unsigned char a[l];
    for (int i = 0; i < n; i++) {
        a[i] = (i + r + n) % n;
    }
    for (int i = n; i < l; i++) {
        a[i] = i;
    }
    return _mm_load_si128(reinterpret_cast<__m128i*>(a));
}

inline int mod_l(int x) {
    if (x >= SC_L) {
        return x - SC_L;
    } else {
        return x;
    }
}

__attribute__((target("sse4.2"), optimize("unroll-loops"))) int main() {
    SC_input();

    constexpr int SIMD_L = 16;

    __m128i rotate_right = get_rotate_perm(SC_L, -1, SIMD_L), rotate_left = get_rotate_perm(SC_L, 1, SIMD_L);

    alignas(32) unsigned char dp[SC_Nt + 1][SC_L][SIMD_L];
    std::fill(dp[0][0], dp[0][SC_L], 127);

    constexpr int center = (SC_L - 1) / 2;
    dp[0][0][center] = 0;

    __m128i C[SC_L];
    for (int i = 0; i < SC_L; ++i) {
        alignas(32) unsigned char tmp[SIMD_L];
        for (int j = 0; j < SC_L; j++) {
            tmp[j] = SC_C[to_index(mod_l(i + j), j)];
        }

        C[i] = _mm_load_si128(reinterpret_cast<__m128i*>(tmp));
    }

    for (int i = 0; i < SC_Nt; i++) {
        __m128i min[SC_L];
        for (int j = 0; j < SC_L; j++) {
            min[j] = _mm_load_si128(reinterpret_cast<__m128i*>(dp[i][j]));
        }

        for (int j = 0; j < SC_L; j++) {
            min[j] = _mm_min_epu8(min[j], _mm_shuffle_epi8(min[j], rotate_left));
        }

        for (int j = 0; j < SC_L; j++) {
            __m128i abs = _mm_abs_epi8(_mm_sub_epi8(C[j], _mm_set1_epi8(SC_Cr[i + 1])));
            __m128i dist = _mm_min_epu8(abs, _mm_sub_epi8(_mm_set1_epi8(SC_Nq), abs));
            __m128i res = _mm_min_epu8(min[mod_l(j - 1 + SC_L)], _mm_shuffle_epi8(min[mod_l(j + 1)], rotate_right));
            res = _mm_add_epi8(res, dist);
            _mm_store_si128(reinterpret_cast<__m128i*>(dp[i + 1][j]), res);
        }
    }

    int min_x = 0, min_y = 0, min = 255;
    for (int i = 0; i < SC_L; i++) {
        for (int j = 0; j < SC_L; j++) {
            if (dp[SC_Nt][i][j] < min) {
                min_x = i;
                min_y = j;
                min = dp[SC_Nt][i][j];
            }
        }
    }

    unsigned char next_min = 255;
    for (int i = SC_Nt - 1; i >= 0; i--) {
        SC_ans[i + 1] = to_index(mod_l(min_x + min_y), min_y);

        int next_x, next_y;

        for (int s = 0; s < 2; s++) {
            int x = mod_l(min_x + (s == 0 ? SC_L - 1 : 1));
            for (int j = 0; j < 2; j++) {
                int y = mod_l(min_y + (s == 0 ? j : SC_L - j));
                if (next_min >= dp[i][x][y]) {
                    next_x = x;
                    next_y = y;
                    next_min = dp[i][x][y];
                }
            }
        }

        min_x = next_x;
        min_y = next_y;
    }

    SC_output();
}