Submission #1176491


Source Code Expand

// TODO: 時間いっぱい回して、一番良かったところをだす。
// TODO: ターンで、確率の変動
// TODO: 盤面で、スコアの評価

#include <iostream>
#include <bitset>
#include <cstdlib>
#include <vector>
#include <memory>
#include <unistd.h>
#include <chrono>
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 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() {
    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<50; ++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<10; ++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<35; ++i) m.push_back({t, d});
                    }
                    else {
                        for (int i=0; i<5; ++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());
        double t = getScore(i);
        if (bestScore < getScore(i)) {
            bestAnswer = answer;
            bestScore = t;
        }
        if (timer.get_clock() >= 3800LL) break;
    }
    bestAnswer.res();
}

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

    input();
    action();
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User dsytk7
Language C++14 (GCC 5.4.1)
Score 52883
Code Size 4608 Byte
Status AC
Exec Time 3805 ms
Memory 2048 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 1876 / 50000 1852 / 50000 1994 / 50000 1777 / 50000 1518 / 50000 1891 / 50000 1496 / 50000 1877 / 50000 1513 / 50000 1805 / 50000 1932 / 50000 1739 / 50000 1803 / 50000 1646 / 50000 1884 / 50000 1948 / 50000 1721 / 50000 1818 / 50000 1515 / 50000 1902 / 50000 1496 / 50000 1724 / 50000 1596 / 50000 1524 / 50000 1898 / 50000 1869 / 50000 1843 / 50000 1739 / 50000 1537 / 50000 2150 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 3804 ms 1792 KB
subtask_01_02.txt AC 3804 ms 1792 KB
subtask_01_03.txt AC 3804 ms 1792 KB
subtask_01_04.txt AC 3804 ms 1792 KB
subtask_01_05.txt AC 3804 ms 1920 KB
subtask_01_06.txt AC 3805 ms 1792 KB
subtask_01_07.txt AC 3804 ms 2048 KB
subtask_01_08.txt AC 3804 ms 1792 KB
subtask_01_09.txt AC 3804 ms 2048 KB
subtask_01_10.txt AC 3804 ms 1792 KB
subtask_01_11.txt AC 3804 ms 1792 KB
subtask_01_12.txt AC 3804 ms 1920 KB
subtask_01_13.txt AC 3804 ms 1920 KB
subtask_01_14.txt AC 3804 ms 1920 KB
subtask_01_15.txt AC 3805 ms 1792 KB
subtask_01_16.txt AC 3803 ms 1792 KB
subtask_01_17.txt AC 3804 ms 1920 KB
subtask_01_18.txt AC 3805 ms 1792 KB
subtask_01_19.txt AC 3805 ms 2048 KB
subtask_01_20.txt AC 3804 ms 1792 KB
subtask_01_21.txt AC 3804 ms 1920 KB
subtask_01_22.txt AC 3804 ms 1920 KB
subtask_01_23.txt AC 3804 ms 1920 KB
subtask_01_24.txt AC 3805 ms 1920 KB
subtask_01_25.txt AC 3805 ms 1792 KB
subtask_01_26.txt AC 3804 ms 1920 KB
subtask_01_27.txt AC 3805 ms 1792 KB
subtask_01_28.txt AC 3803 ms 1792 KB
subtask_01_29.txt AC 3805 ms 1920 KB
subtask_01_30.txt AC 3804 ms 1792 KB