Submission #1177094

---

Source Code Expand

// 目的地が端に近いのを最初に橋に近づける
// 目的地が中心の方のやつを止めておく
// 橋に近づける

// マスに評価値つけて、評価値が高い方を動かす。

#include <iostream>
#include <bitset>
#include <cstdlib>
#include <vector>
#include <memory>
#include <chrono>
#include <unistd.h>
using namespace std;
using namespace chrono;
typedef long long ll;

class Timer {
private:
    high_resolution_clock::time_point start;
public:
    void begin() { start = high_resolution_clock::now(); }
    ll get_clock() { return duration_cast<milliseconds>(high_resolution_clock::now()-start).count(); }
};

unsigned long xorshift() {
    shared_ptr<Timer> ptimer(new Timer());
    ptimer->begin();
    static unsigned long x=ptimer->get_clock(), y=getpid(), z=521388629, w=88675123;
    unsigned long t=(x^(x<<11));
    x=y; y=z; z=w; w=(w^(w>>19))^(t^(t>>8));
    return w;
}

const int evalMap[30][30] = {
    { 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15 },
    { 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15 },
    { 15, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 15 },
    { 15, 14, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  4,  4,  4,  4,  4,  4,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  3,  3,  3,  3,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  2,  2,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  1,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  1,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  2,  2,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  3,  3,  3,  3,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  4,  4,  4,  4,  4,  4,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 13, 14, 15 },
    { 15, 14, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 14, 15 },
    { 15, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 15 },
    { 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15 },
    { 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15 }
};

const int dx[] = { 0, 1, 0, -1, 0 };
const int dy[] = { 1, 0, -1, 0, 0 };
const string dir = "DRUL-";

struct P {
    int y,x;
    P(int y=0, int x=0):y(y), x(x) {}
    bool operator==(const P& o) const {
        return y==o.y&&x==o.x;
    }
    bool operator<(const P& o) const {
        return y==o.y?x<o.x:y<o.y;
    }
    void add(int d) {
        y+=dy[d];
        x+=dx[d];
    }
};

struct F {
    bitset<30> f[30];
    bitset<30>& get(int y) { return f[y]; }
    void set(P p) { f[p.y][p.x]=1; }
    void set(int y, int x) { set(P(y, x)); }
    void reset(P p) { f[p.y][p.x]=0; }
    void reset(int y, int x) { reset(P(y, x)); }
    int getR(P p) { return f[p.y].count(); }
    int getR(int y) { return f[y].count(); }
    bool get(P p) { return f[p.y][p.x]; }
    bool get(int y, int x) { return f[y][x]; }
};

struct Answer {
    vector<string> ans;
    void add(string s) { ans.push_back(s); }
    void res() {
        int n=ans.size();
        cout << n << endl;
        for (int i=0; i<n; ++i) cout << ans[i] << endl;
    }
};

int H, W, K, T;
P S[451], E[451];
F board;
Answer answer;

inline int dist(P& S, int i) {
    return abs(S.y-E[i].y)+abs(S.x-E[i].x);
}

inline bool isMove(P& p) {
    return (0 <= p.y && p.y < H && 0 <= p.x && p.x < W);
}

inline double getScore(const int& L) {
    double Pd = 20;
    for (int i=0; i<K; ++i) { Pd += dist(S[i], i); }
    double Pr = 10 + 0.01*L;
    return 1e7/(Pd*Pr);
}

void input() {
    cin >> H >> W >> K >> T;
    for (int i=0; i<K; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c-- ,d--;
        S[i] = P(a, b);
        E[i] = P(c, d);
        board.set(S[i]);
    }
}

// 1ターンの動き
string move(const int L) {
    string res="";
    bitset<450> flag;
    for (int i=0; i<K; ++i){ flag[i]=1; res += "-"; }
    F next;

    while (flag.count()) {
        int rd = xorshift()%K;
        if (!flag[rd]) continue;
        flag[rd]=0;
        vector<pair<P, int>> m;
        if (dist(S[rd], rd) == 0) {
            for (int i=0; i<40; ++i) m.push_back({S[rd], 4});
            for (int d=0; d<4; ++d) {
                P t = S[rd]; t.add(d);
                if (isMove(t) && !board.get(t) && !next.get(t)) {
                    for (int i=0; i<4; ++i) m.push_back({t, d});
                }
            }
        }
        else {
            for (int i=0; i<1; ++i) m.push_back({S[rd], 4});
            for (int d=0; d<4; ++d) {
                P t = S[rd]; t.add(d);
                if (isMove(t) && !board.get(t) && !next.get(t)) {
                    if (dist(t, rd) < dist(S[rd], rd)) {
                        for (int i=0; i<25; ++i) m.push_back({t, d});
                    }
                    else {
                        for (int i=0; i<1; ++i) m.push_back({t, d});
                    }
                }
            }
        }

        pair<P, int> move = m[xorshift()%(m.size())];
        next.set(move.first);
        S[rd] = move.first;
        res[rd] = dir[move.second];
    }

    F t;
    for (int i=0; i<K; ++i) { t.set(S[i]); }
    board = t;

    return res;
}

void action() {
    Timer timer; timer.begin();
    double bestScore = 0;
    Answer bestAnswer;
    for (int i=1; i<=T; ++i) {
        answer.add(move(i));
        double t = getScore(i);
        if (bestScore < getScore(i)) {
            bestAnswer = answer;
            bestScore = t;
        }
        if (timer.get_clock() >= 3800LL) break;
    }
    bestAnswer.res();
    cerr << bestScore << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    input();
    action();
}

Submission Info

Judge Result