Marathon Match 66: DigitsPattern

ひどい問題だった。

参加記のようなものも書いたけど3日目でほぼ最適解の出せる解法が出たので先に解法を書いておく。
最終日に確実に最適解が出るようにしたのでそれも追加した。

解法

そのまま考えるのは面倒なので、グラフの問題だと思って考えてみる。

• 問題

隣接するノードを1方向のエッジで繋げてDAGを作る。このとき各ノードの入次数(別に出次数でもいいけど)を指定された値に近づける。

DAGが作れたら後はトポロジカルソートすればそれが元の問題の答えになる。

DAGを作るとき、入次数=0または出次数=0のノードは有向閉路の形成に寄与しないことを利用する。
また、そのようなノードに対して辺をどちら向きに張るかは貪欲に決定できる。Aが損してBが得するのと、Aが得してBが損するのは、全体のスコアに影響しないし、どちらを選んでも有向閉路が生じない。
自分では実装してないけど、橋の向きも貪欲に決定できる。

以上のことから、

• 指標 >= 入次数 + 接続次数 のノードがあれば、そのノードに接続している向きが未確定な辺は全てそのノードに向かうようにする。
• 指標　<= 入次数　のノードがあれば、そのノードに接続している向きが未確定な辺は全てそのノードから出ていくようにする。

これを繰り返せば良い。
この場合処理できないグラフが残る場合もあるが、その様なグラフは非常に特殊なケースに限られる。

22
22

とか

.222
.2.2
2233
2222

とか(指標は各セルの値-1、辺の向きはいずれも未確定)。
残ったクラスタはどれもそれなりに小さいし、一つ決まれば残りも自動的に決まっていくような構造をしていることが多い。
なので全てのノードに対して全探索を掛ける。すなわち、一つのノードを固定して、それに接続する向きが未確定な辺の向きを全て外向きと仮定し、再帰的に残りのグラフに全探索を掛ける。そして一番良いスコアを出したものを採用する。
この全探索を愚直に書くとごく稀にTLEする(30秒くらいかかったケースがあった)のでメモ化を入れるとおよそ1秒以内に最適解を返す。

1日目(木曜)：

• 問題に目を通す。得点制度は相対評価なので相変わらずどのケースでも手を抜くことはできない。
• とりあえず値の大きい順に出力させてpositive scoreを出してみる。
• うまいことDPっぽく探索空間を狭めたりするかもしれないけど、基本は焼き鈍しとかになるんだろうなと考える。
• そうなったら速度勝負になるかもしれない。SSEの勉強もする必要が出てくるかな…。
• 焼き鈍しは組んだことがないので温度の決め方とか分からない。なので最初は負の遷移を許可しないようにした。
• 要するに山登り法。
• 近傍の決め方は、2点選んで順序を入れ替え。ローカルな変化しかしないので定数時間で評価できる。
• クラスタの分割は必須。
• スコアの変動が無いとき遷移するかどうかで随分差が出た(遷移する方が良い)。
• ローカルでそこそこのスコアが出たのでfirst submit。そこそこのスコアが出た。
• 遷移する処理のバグを取り除く。いくつかのケースでは最適解も出た。

2日目(金曜):

• visualizerの一部をC++に移植する(主にテストケース生成の難しいケースの方だけ)。
• 今回は可視化する意味あまりなさげだし。
• 前回使ったスクリプトを流用して作業の一部(過去最高スコアとの比較など)を自動化する。
• 焼き鈍しの温度を色々いじってみる。あれ、山登り法より良くならない…。
• 今回はご縁が無かったということで…。
• 探索時間を増やしても減らしてもスコアが良くならないので、局所解からの脱出を考える。
• タブーサーチを実装しようとしてみた。
• タブーリストに載せる基準が分からないし、一回の更新に必要な処理が重すぎて止めた。
• 小さいケースでは山登り法でもほぼ最適解が出ているので、分割統治法で処理してみる。
• 極端に悪いわけではないけど、山登り法より良くならない。
• 周囲4近傍に対する相対的な順序を貪欲に入れ替える、などを試すもやっぱり山登り法に勝てない。
• 順位表を眺めていると、1位が複数人並んでいて、その下も並んでいる。
• 1位の人のアルゴリズムのレーティングは高めだし、過去に提出したマラソンのコード見ても埋め込みはやっていない。
• 最適解が出てるんじゃなかろうか?

3日目(土曜):

• 1位が7人くらい並んでるし、その中にはpythonで提出されたコードもある。
• これは最適解が出ているし、ヒューリスティックでないまともな解法があるんだろうね。
• こんな状況になったらヒューリスティックな解法はあまり役にたたない。System Testで1000個のケースに対して1個でも最適解が出せないと終了するから。
• 問題を真面目に考察してみる。
• O((H*W)^2)以下の解法を考えてみる。または5!*(H*W)とか。
• DPでできないか考える。
• 最適な手順を直接出すのではなく、最適な結果(盤面)が出せればそこからは山登り方で十分な確率で最適解が出せそう。
• 最適な結果を具体例で考えて、4近傍の順序を不等号で表したのを眺めてみる。
• 有向グラフですね。はい…。
• 有向グラフつくれば最適な結果だけじゃなく手順も出せるじゃないか、と思って実装するも悪化。
• 冷静に考えると有向閉路あったら駄目だよね。
• これで問題を完全に読み替えることができた。随分と見通しが良くなった。
• 簡単に決定できない部分は山登り法で出す。
• それまでの最高記録をかなり更新できたのでsubmit。1位ゲット。
• まだ処理の一部をヒューリスティックに頼っているが、流石にあれはテストケース１０００個くらいではボロが出ないだろう。
• ローカルで探索時間を1/10にしても2000個のテストケースに対して最適解出すし。

4日目(日曜):

• これを書いている。
• 気が向いたらコードを綺麗に書き直そうかな。
• 一応残り期間もヒューリスティックな部分を消せるように色々考えておこう。時間があれば。
• 今の時点で1位は１１人いる。これはレーティング+1点コースかな…。残念。
• 順位表がヒント過ぎた。
• レーティング高い人が今回のに参加する意味は殆ど無いと思われる。
• まあwinを稼いでおけるので良としよう。volatilityは失うだろうけどね…。それはつまり赤が遠のくということでもあって。
• これだけ書いといて1位じゃなかったら恥ずかしすぎる。

最終日(水曜):

• ずっと放置していたが1位多すぎでヒューリスティックが不安になり、ローカルで10000ケースを対象にして色々試す。
• 探索時間半分にしたら答えが変わるのが10個くらいあった。これは危険信号。焦る。
• 一番危ないヤツをピックアップする。こんなの

..222
223.2
24233
23222

• 関節があればそのノードは貪欲に決定できるけど、これには関節がないのでどうしようもない。
• 近傍を辺の向きのフリップで定義して山登りしようと思ったけどどう考えても局所解から抜けだせない気がする。
• いろいろ都合のいい仮定を置いて嘘解法をでっち上げたけど出てくる答も嘘。当然だと言わざるをえない。
• 間に合うとは思えないけど取りあえず全探索書いてみる。
• 時間はかかるだろうけど、これなら確実に最適解を出せる。
• 動かしてみたら余裕で間に合った。
• 再び10000ケース試す。4つのケースで最大を更新したけど、2つのケースで30秒くらいかかってた。
• 片方は関節を持たないケースなので、何か別の工夫を入れないと。
• メモ化を入れて解決。
• 速度がかなり安定した。1秒越えるのは皆無。
• 流石にこれからTLE奪うテストケースは無いだろう…。よほど作為的でないかぎり。
• 関節だったら貪欲に決められると思ってたけどよく考えたら嘘だった。決められるのは橋だ。
• 余計な変数とか全部消して提出した。もうちょっとコード削れるけどもういいや。
• ローカルでどこまでならTLEせずにいけるか実験する。こんなケースでぎりぎりTLEした。

2332232
2343423
2233433
3433433
3442433
2332322

これはサイズ6*7だけど6*6だと殆ど大丈夫っぽかった(ちなみにこの入力に対する最適解は12+1)。
ランダムに作ってこんなケースが出たらごめんなさいするしかない。

• 最終的に提出したプログラムは10000ケースに対して約500秒で最適解を出した。テストケース1つあたり平均0.05秒。もっとも、重要なのは平均ではなく最大値なんだけど。

感想、反省

• 最終的に提出したプログラムはなんだかんだ言って結構自信作。
• 最適解は多分確実に出せるけどTLEしない保証は無い。なのでSystem Testまでちょっと怖い。
• 最終日に色々いじったけど、実はいじらなくても大丈夫だったのではないかと密かに思っている。
• テストケース1000か2000しかなくてそのうち半分は簡単なやつだし。
• でも何人かは1位から落ちると思う。
• 1位をどうしても取らなければというプレッシャーがあって、10000個のうち1個出るかどうかのレアケースの処理をいちいち考えなければならなかった。これは実にストレスフルな作業だった。
• 今回はVisualizerをC++に移植しといてよかった。肝心の可視化をしてないけど。
• 各種スクリプトも用意しといてよかった。
• 3日目にこの問題をグラフの問題と読み替えたときはちょっと怖かった。グラフとか苦手だし。

#ifndef SOLVER_H
#define SOLVER_H

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <numeric>
#include <string.h>
#include <sys/time.h>
using namespace std;

#define ANALYZE 1

class DigitsPattern{
public: 
int totalScore, score;
int W, H, N;
int curTime;
vector<int> timeStamp;
vector< vector<int> > best;
string board, tmpBoard;
vector<int> graph;
vector< set< int > > degs;
vector<int> getDegs;
vector<int> dp;
map<vector< pair<int, char> >, int> dict;

inline void init(vector<string>& target){
    curTime = 0;
    H = target.size();
    W = target[0].size();

    board = string(W+2,'.');
    for(int i=0; i<H; i++){
        board += '.'+target[i]+'.';
    }
    board += string(W+2,'.');
    W += 2; H += 2;
    tmpBoard = board;
    dp = vector<int>(4);
    dp[0] = 1;
    dp[1] = -W;
    dp[2] = -1;
    dp[3] = W;

    timeStamp = vector<int>(H*W,0);
    graph = vector<int>(W*H,0);

    dagSolve();

    for(int p=0; p<W*H; p++){
        if('1'<=board[p] && board[p]<='5'){
            best.push_back(vector<int>());
            floodFill(p);
        }
    }
    for(int p=0; p<W*H; p++){
        if(board[p] != '.') board[p] = ~board[p];
    }
}

inline void floodFill(int p){
    board[p] = ~board[p];
    best.back().push_back(p);
    for(int k=0; k<4; k++){
        int np = p + dp[k];
        if('1' <= board[np] && board[np] <= '5'){
            floodFill(np);
        }
    }
    return ;
}

vector<int> recreate(vector<string> target){
    init(target);

    int pnt = 0;
    for(int i=0; i<best.size(); i++){
        sort(best[i].begin(), best[i].end());
        dict.clear();
        hogeSolve(best[i]);
    }

    board = tmpBoard;
    curTime = 1;
    for(int p=0; p<W*H; p++)if(board[p]!='.'){
        tpSort(p);
    }
    board = tmpBoard;

    vector< pair<int,int> > Q;
    for(int p=0; p<W*H; p++)if(board[p]!='.'){
        Q.push_back( make_pair(timeStamp[p],p) );
    }
    sort(Q.begin(),Q.end());

    vector<int> ret;
    ret.reserve(2*N+1);
    for(int i=0; i<Q.size(); i++){
        ret.push_back((Q[i].second/W)-1);
        ret.push_back((Q[i].second%W)-1);
    }


if(ANALYZE){
    totalScore = 0;
    for(int p=0; p<W*H; p++)if(board[p]!='.'){
        char cnt = '1';
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(timeStamp[np] > timeStamp[p]) cnt++;
        }
        totalScore += abs(board[p] - cnt);
    }
    if(curTime != Q.size()+1) cerr << "checked: "<< curTime << endl;
    cerr << "totalScore: " << totalScore << endl;
}
    return  ret;
}

void hogeSolve(vector<int> bs){
    int n = bs.size();
    if(!n) return ;
    vector< pair<int, char> > keyVec;
    keyVec.reserve(n);
    for(int i=0; i<n; i++){
        keyVec.push_back( make_pair(bs[i], board[bs[i]]) );
    }
    int mi = 1<<29, key=-1;
    if(dict.find(keyVec) == dict.end()){
        vector<int> tmpGraph, tmpDegs;
        vector<char> tmpNums;
        vector< set<int> > tmpD;
        for(int i=0; i<5; i++) degs[i].clear();
        for(int i=0; i<n; i++) degs[getDegs[bs[i]]].insert(bs[i]);
        tmpD = degs;
        for(int i=0; i<n; i++) tmpGraph.push_back(graph[bs[i]]);
        for(int i=0; i<n; i++) tmpDegs.push_back(getDegs[bs[i]]);
        for(int i=0; i<n; i++) tmpNums.push_back(board[bs[i]]);
        for(int i=0; i<n; i++){
            int p = bs[i];
            for(int k=0; k<4; k++){
                int np = p + dp[k];
                if(board[np] != '.'){
                    if(board[np] > '1') board[np]--;
                    degs[getDegs[np]].erase(np);
                    getDegs[np]--;
                    degs[getDegs[np]].insert(np);
                    graph[p] |= 1<<k;
                }
            }
            degs[getDegs[p]].erase(p);
            getDegs[p] = 0;
            board[p] = '.';
            while(handleAll());

            vector<int> bbs;
            for(int i=0; i<n; i++)if(board[bs[i]] != '.')
                bbs.push_back(bs[i]);
            hogeSolve(bbs);
            int ts = evalScore(bs);
            if(ts < mi){
                mi = ts;
                key = p;
            }

            for(int i=0; i<n; i++) graph[bs[i]] = tmpGraph[i];
            for(int i=0; i<n; i++) getDegs[bs[i]] = tmpDegs[i];
            for(int i=0; i<n; i++) board[bs[i]] = tmpNums[i];
            degs = tmpD;
        }
        dict[keyVec] = key;
    }
    else{
        key = dict[keyVec];
    }
    int p = key;
    for(int k=0; k<4; k++){
        int np = p + dp[k];
        if(board[np] != '.'){
            if(board[np] > '1') board[np]--;
            degs[getDegs[np]].erase(np);
            getDegs[np]--;
            degs[getDegs[np]].insert(np);
            graph[p] |= 1<<k;
        }
    }
    degs[getDegs[p]].erase(p);
    getDegs[p] = 0;
    board[p] = '.';
    while(handleAll());
    vector<int> bbs;
    for(int i=0; i<n; i++)if(board[bs[i]] != '.')
        bbs.push_back(bs[i]);
    hogeSolve(bbs);
    return ;
}

int evalScore(vector<int>& bs){
    int n = bs.size();
    int ret = 0;
    for(int i=0; i<n; i++){
        int p = bs[i], cnt=0;
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(tmpBoard[np] != '.' && !(graph[p]&(1<<k))) cnt++;
        }
        ret += abs((int)tmpBoard[p] - '1' - cnt);
    }
    return ret;
}

void tpSort(int p){
    board[p] = '.';
    for(int k=0; k<4; k++)if(graph[p] & (1<<k)){
        int np = p + dp[k];
        if(board[np] != '.'){
            tpSort(np);
        }
    }
    timeStamp[p] = curTime++;
    return ;
}

void dagSolve(){
    degs = vector< set<int> >(5);
    getDegs = vector<int>(W*H, 0);
    for(int p=0; p<W*H; p++){
        if(board[p]!='.'){
            int cnt = 0;
            for(int k=0; k<4; k++){
                int np = p + dp[k];
                if(board[np]!='.'){
                    cnt++;
                }
            }
            degs[cnt].insert(p);
            getDegs[p] = cnt;
        }
    }

    graph = vector<int>(W*H, 0);

    while(handleAll());
    return ;
}

int handleAll(){
    if(handleZero()) return 1;
    if(handleFour()) return 1;
    if(handleThree()) return 1;
    if(handleTwo()) return 1;
    if(handleOne()) return 1;
    return 0;
}

int handleZero(){
    if(degs[0].empty()) return 0;
    int p = *degs[0].begin();
    degs[0].erase(p);
    board[p] = '.';
    return 1;
}

int handleOne(){
    if(degs[1].empty()) return 0;
    int p = *degs[1].begin();
    degs[1].erase(p);
    if(board[p] == '1'){
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                if(board[np] > '1'){
                    board[np]--;
                    graph[p] |= 1<<k;
                }
                else{
                    graph[np] |= 1<<(k^2);
                }
                break;
            }
        }
    }
    else{
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[np] |= 1<<(k^2);
                break;
            }
        }
    }
    getDegs[p] = 0;
    board[p] = '.';
    return 1;
}

int handleTwo(){
    if(degs[2].empty()) return 0;
    int p = 0;
    for(set<int>::iterator it = degs[2].begin(); it != degs[2].end(); it++){
        if(board[*it] != '2'){
            p = *it;
            break;
        }
    }
    if(!p) return 0;
    degs[2].erase(p);
    if(board[p] == '1'){
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                if(board[np] > '1') board[np]--;
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[p] |= 1<<k;
            }
        }
    }
    else{
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[np] |= 1<<(k^2);
            }
        }
    }

    board[p] = '.';
    getDegs[p] = 0;

    return 1;
}

int handleThree(){
    if(degs[3].empty()) return 0;
    int p = 0;
    for(set<int>::iterator it = degs[3].begin(); it != degs[3].end(); it++){
        if(board[*it] == '1' || board[*it] > '3'){
            p = *it;
            break;
        }
    }
    if(!p) return 0;
    degs[3].erase(p);
    if(board[p] == '1'){
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                if(board[np] > '1') board[np]--;
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[p] |= 1<<k;
            }
        }
    }
    else{
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[np] |= 1<<(k^2);
            }
        }
    }

    board[p] = '.';
    getDegs[p] = 0;

    return 1;
}

int handleFour(){
    if(degs[4].empty()) return 0;
    int p = 0;
    for(set<int>::iterator it = degs[4].begin(); it != degs[4].end(); it++){
        if(board[*it] == '1' || board[*it] > '4'){
            p = *it;
            break;
        }
    }
    if(!p) return 0;
    degs[4].erase(p);
    if(board[p] == '1'){
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                if(board[np] > '1') board[np]--;
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[p] |= 1<<k;
            }
        }
    }
    else{
        for(int k=0; k<4; k++){
            int np = p + dp[k];
            if(board[np] != '.'){
                degs[getDegs[np]].erase(np);
                getDegs[np]--;
                degs[getDegs[np]].insert(np);
                graph[np] |= 1<<(k^2);
            }
        }
    }

    board[p] = '.';
    getDegs[p] = 0;

    return 1;
}

};

#endif