Submission #1174376


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;

    int H, W, K, T;
    int[] A, B, C, D;

    int[] mode;

    const int FIRST = 0;
    const int UP = 1;
    const int DOWN = 2;
    const int SUPERRIGHT = 3;
    const int SUPERLEFT = 4;
    const int RIGHT = 5;
    const int LEFT = 6;
    const int STAY = 7;
    const int WANTRIGHT = 8;
    const int WANTLEFT = 9;
    // 0: first
    // 1: up
    // 2: down
    // 3: superright
    // 4: superleft
    // 5: right
    // 6: left
    // 7: OK

    XRand rnd;
    
    int[,] usedNum;
    int[,] move;
    int[,,] newMove;


    int[] FA, FB;

    int bestTurn;
    int bestAddTurn;
    double bestScore;
    string bestString;
    int[,] bestMove;

    string moveS = "DRUL-";

    int[] vy = { 1, 0, -1, 0, 0 };
    int[] vx = { 0, 1, 0, -1, 0 };

    const int VUP = 2;
    const int VDOWN = 0;
    const int VRIGHT = 1;
    const int VLEFT = 3;
    const int VSTAY = 4;

    const int LIMIT = 3;

    int[,] wantTurn;
    int[,] wantID;

    int[] ar;

    int bestTT = 800;

    //B問題
    public void calc()
    {
        Stopwatch sw = new Stopwatch();
        cin = new Scanner();
        rnd = new XRand();
        H = cin.nextInt();
        W = cin.nextInt();
        K = cin.nextInt();
        T = cin.nextInt();
        sw.Start();
        A = new int[K];
        B = new int[K];
        C = new int[K];
        D = new int[K];
        for (int i = 0; i < K; i++)
        {
            A[i] = cin.nextInt() - 1;
            B[i] = cin.nextInt() - 1;
            C[i] = cin.nextInt() - 1;
            D[i] = cin.nextInt() - 1;
        }
        FA = (int[])A.Clone();
        FB = (int[])B.Clone();
        usedNum = new int[H, W];
        for (int i = 0; i < K; i++)
        {
            usedNum[A[i], B[i]]++;
        }
        
        ar = new int[K];
        for (int i = 0; i < K; i++)
        {
            ar[i] = i;
        }

        bestScore = 0;
        bestTurn = 0;
        bestAddTurn = 0;

        for (int i = 0; sw.ElapsedMilliseconds < 3500; i++)
        {
            go();
            //break;
        }

        // bestTurn = TT;
        Console.WriteLine(bestTurn + bestAddTurn);
        for (int i = 0; i < bestTurn; i++)
        {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < K; j++)
            {
                sb.Append(moveS[bestMove[i, j]]);
            }
            Console.WriteLine(sb.ToString());
        }
    }

    void go()
    {
        A = (int[])FA.Clone();
        B = (int[])FB.Clone();

        int TT = bestTT; //(int)(bestTT * (1.1 - rnd.nextDouble() * 0.2));

        double MyBestScore = 0;
        int MyBestTurn = 0;
        move = new int[TT * 7 / 5, K];

        for (int t = 0; t < TT * 1.2; t++)
        {
            turn = t;
            addturn = -1;
            
            usedNum = new int[H, W];
            for (int i = 0; i < K; i++)
            {
                usedNum[A[i], B[i]]++;
            }


            randomshuffle(ar);
            for (int pi = 0; pi < K; pi++)
            {
                int i = ar[pi];
                move[t, i] = -1;


                double rate = Math.Pow(Math.Min(1, (double)t / TT), 0.5);
                int TD = D[i];
                if (TD < H / 2) TD = (int)(TD * rate);
                else TD = (int)((TD * rate) + (1 - rate) * (H - 1));
                int TC = C[i];

                if (TC < H / 2) TC = (int)(TC * rate);
                else TC = (int)(TC * rate + (1 - rate) * (H - 1));

                int Rdiff = TD - B[i];
                int Udiff = TC - A[i];
                int[] check = makeMove(Udiff, Rdiff, t, TT);
                foreach (var next in check)
                {
                    if(checkMove(i, next))
                    {
                        break;
                    }
                }
                if (move[t, i] == -1) move[t, i] = VSTAY;
            }

            double score = calcScore(t);
            if (MyBestScore < score)
            {
                MyBestScore = score;
                MyBestTurn = t + 1;
                //Console.Error.WriteLine("NEWSCORE: " + bestTurn + " " + score);
            }
        }
        

        if (MyBestScore > bestScore)
        {
            bestScore = MyBestScore;
            bestTurn = MyBestTurn;
            bestTT = TT;
            bestMove = (int[,])move.Clone();
            Console.Error.WriteLine("NEWSCORE: " + bestTurn + " " + TT + " " + bestScore);
        }
    }

    int[] makeMove(int U, int R, int t, int TT)
    {
        List<int> L = new List<int>();
        bool[] used = new bool[5];
        double[] Rate = DicideRate(U, R, t, TT);
        for (int i = 0; i < 10; i++)
        {
            double d = rnd.nextDouble();
            for (int j = 0; j < 5; j++)
            {
                d -= Rate[j];
                if(d < 0)
                {
                    if (used[j]) break;
                    used[j] = true;
                    L.Add(j);
                    break;
                }
            }
        }
        if (!used[4]) L.Add(4);
        return L.ToArray();
    }

    double[] DicideRate(int U, int R, int t, int TT)
    {
        double fuwa = Math.Pow((TT - t) / (double)TT, 1.25);
        if (t > TT) fuwa = 0;
        if (U == 0 && R == 0)
        {
            double moveRate = 0.25 * fuwa / TT;
            return new double[] { moveRate, moveRate, moveRate, moveRate, 1 - moveRate - 4 };
        }

        double tRate = t / TT;
        double UR = Math.Abs(U) + Math.Abs(R) + 2;
        double UD = (Math.Abs(U) + 1) / UR;
        double RL = 1 - UD;
        double[] ans = new double[5];
        if (U > 0) ans[0] = UD;
        else if (U < 0) ans[2] = UD;
        else ans[0] = ans[2] = UD / 2;
        if (R > 0) ans[1] = RL;
        else if (R < 0) ans[3] = RL;
        else ans[1] = ans[3] = RL / 2;
        for (int i = 0; i < 4; i++)
        {
            ans[i] *= (1 - fuwa);
            ans[i] += fuwa / 4;
        }
        //Console.Error.WriteLine(string.Join(" ", ans));
        return ans;
    }

    //配列のランダム並び替え
    void randomshuffle<T>(T[] a)
    {
        int len = a.Length;
        for (int i = 0; i < len - 1; i++)
        {
            swap(ref a[i], ref a[i + rnd.nextInt(len - i)]);
        }
    }

    //swap
    void swap<T>(ref T a, ref T b)
    {
        T c = a;
        a = b;
        b = c;
    } 

    int getDist(int a, int b, int c, int d)
    {
        return Math.Abs(a - c) + Math.Abs(b - d);
    }

    int turn;
    int addturn;

    bool forceMove(int p, int k)
    {

        return checkMove(p, k);

        /*
        usedNum[A[p], B[p]]--;
        A[p] += vy[k];
        B[p] += vy[k];
        move[turn, p] = k;
        return true;
        */
    }


    bool checkMove(int p, int k)
    {
        if (addturn == -1 && move[turn, p] != -1) return false;
        if (addturn != -1 && newMove[turn, p, addturn] != -1) return false;
        int ny = A[p] + vy[k];
        int nx = B[p] + vx[k];
        if (!inside(ny, nx)) return false;
        if (usedNum[ny, nx] >= 1) return false; 
        //usedNum[A[p], B[p]]--;
        A[p] = ny;
        B[p] = nx;
        usedNum[A[p], B[p]]++;
        if (addturn == -1) move[turn, p] = k;
        else newMove[turn, p, addturn] = k;
        //Console.Error.WriteLine("MOVE: " + turn + " " + p + " " + k);
        return true;
        
    }
    int modeChange(int p)
    {
        if (mode[p] == STAY) return STAY;
        if (B[p] == 0 && A[p] != H - 1) return UP;
        if (B[p] == W - 1 && A[p] != H - 1) return DOWN;
        if (A[p] == 0) return SUPERRIGHT;
        if (A[p] == H - 2) return SUPERLEFT;
        if (A[p] % 2 == 0)
        {
            if (A[p] % 4 == 0) return RIGHT;
            else return LEFT;
        }
        int dist = Math.Abs(A[p] - C[p]) + Math.Abs(B[p] - D[p]);
        if (dist <= LIMIT) return STAY;

        return FIRST;
    }

    bool inside(int y, int x)
    {
        return y >= 0 && x >= 0 && y < H && x < W;
    } 

    double calcScore(int turn)
    {
        double PD = 20;
        for (int i = 0; i < K; i++)
        {
            PD += Math.Abs(A[i] - C[i]);
            PD += Math.Abs(B[i] - D[i]);
        }
        double PT = 10 + 0.01 * turn;
        //Console.Error.WriteLine(PD + " " + PT);
        return 1000000 / (PD * PT);
    }
    
    
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

public class XRand
{
    uint x, y, z, w;


    public XRand()
    {
        init();
    }

    public XRand(uint s)
    {
        init();
        init_xor128(s);
    }

    void init()
    {
        x = 314159265; y = 358979323; z = 846264338; w = 327950288;

    }

    public void init_xor128(uint s)
    {
        z ^= s;
        z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
        z *= 736338717;
    }

    uint next()
    {
        uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
    }

    public long nextLong(long m)
    {
        return (long)((((ulong)next() << 32) + next()) % (ulong)m);
    }

    public int nextInt(int m)
    {
        return (int)(next() % m);
    }

    public int nextInt(int min, int max)
    {
        return min + nextInt(max - min + 1);
    }

    public int nextIntP(int a)
    {
        return (int)Math.Pow(a, nextDouble());
    }

    public int nextIntP(int min, int max)
    {
        int diff = max - min;
        return min + nextIntP(diff + 2) - 1;
    }

    public double nextDouble()
    {
        return (double)next() / uint.MaxValue;
    }

    public double nextDoubleP(double a)
    {
        return Math.Pow(a, nextDouble());
    }
}

Submission Info

Submission Time
Task A - 石油王Xの憂鬱
User chokudai
Language C# (Mono 4.6.2.0)
Score 0
Code Size 11007 Byte
Status WA
Exec Time 2103 ms
Memory 31492 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 test_31 test_32 test_33 test_34 test_35 test_36 test_37 test_38 test_39 test_40 test_41 test_42 test_43 test_44 test_45 test_46 test_47 test_48 test_49 test_50
Score / Max Score 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500 0 / 417500
Status
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
WA × 1
WA × 1
TLE × 1
TLE × 1
WA × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
WA × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
WA × 1
TLE × 1
TLE × 1
WA × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
WA × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 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
test_31 subtask_01_31.txt
test_32 subtask_01_32.txt
test_33 subtask_01_33.txt
test_34 subtask_01_34.txt
test_35 subtask_01_35.txt
test_36 subtask_01_36.txt
test_37 subtask_01_37.txt
test_38 subtask_01_38.txt
test_39 subtask_01_39.txt
test_40 subtask_01_40.txt
test_41 subtask_01_41.txt
test_42 subtask_01_42.txt
test_43 subtask_01_43.txt
test_44 subtask_01_44.txt
test_45 subtask_01_45.txt
test_46 subtask_01_46.txt
test_47 subtask_01_47.txt
test_48 subtask_01_48.txt
test_49 subtask_01_49.txt
test_50 subtask_01_50.txt
Case Name Status Exec Time Memory
subtask_01_01.txt TLE 2103 ms 8756 KB
subtask_01_02.txt TLE 2103 ms 8752 KB
subtask_01_03.txt TLE 2103 ms 8756 KB
subtask_01_04.txt TLE 2103 ms 10800 KB
subtask_01_05.txt TLE 2103 ms 10804 KB
subtask_01_06.txt TLE 2103 ms 10804 KB
subtask_01_07.txt TLE 2103 ms 10804 KB
subtask_01_08.txt TLE 2103 ms 8756 KB
subtask_01_09.txt TLE 2103 ms 10800 KB
subtask_01_10.txt TLE 2103 ms 8752 KB
subtask_01_11.txt WA 31 ms 11060 KB
subtask_01_12.txt WA 24 ms 10932 KB
subtask_01_13.txt TLE 2103 ms 8756 KB
subtask_01_14.txt TLE 2103 ms 10800 KB
subtask_01_15.txt WA 25 ms 11060 KB
subtask_01_16.txt TLE 2103 ms 8756 KB
subtask_01_17.txt TLE 2103 ms 10800 KB
subtask_01_18.txt TLE 2103 ms 10804 KB
subtask_01_19.txt TLE 2103 ms 8752 KB
subtask_01_20.txt WA 35 ms 11056 KB
subtask_01_21.txt TLE 2103 ms 29656 KB
subtask_01_22.txt TLE 2103 ms 10796 KB
subtask_01_23.txt TLE 2103 ms 10804 KB
subtask_01_24.txt TLE 2103 ms 15328 KB
subtask_01_25.txt TLE 2103 ms 8756 KB
subtask_01_26.txt TLE 2103 ms 18276 KB
subtask_01_27.txt TLE 2103 ms 10800 KB
subtask_01_28.txt WA 31 ms 11056 KB
subtask_01_29.txt TLE 2103 ms 10804 KB
subtask_01_30.txt TLE 2103 ms 8756 KB
subtask_01_31.txt WA 25 ms 11060 KB
subtask_01_32.txt TLE 2103 ms 29900 KB
subtask_01_33.txt TLE 2103 ms 10804 KB
subtask_01_34.txt TLE 2103 ms 18216 KB
subtask_01_35.txt TLE 2103 ms 19084 KB
subtask_01_36.txt TLE 2103 ms 8748 KB
subtask_01_37.txt TLE 2103 ms 30456 KB
subtask_01_38.txt TLE 2103 ms 10804 KB
subtask_01_39.txt TLE 2103 ms 10804 KB
subtask_01_40.txt TLE 2103 ms 14968 KB
subtask_01_41.txt TLE 2103 ms 10800 KB
subtask_01_42.txt WA 25 ms 13108 KB
subtask_01_43.txt TLE 2103 ms 8756 KB
subtask_01_44.txt TLE 2103 ms 10804 KB
subtask_01_45.txt TLE 2103 ms 8756 KB
subtask_01_46.txt TLE 2103 ms 8756 KB
subtask_01_47.txt TLE 2103 ms 8756 KB
subtask_01_48.txt TLE 2103 ms 31492 KB
subtask_01_49.txt TLE 2103 ms 8756 KB
subtask_01_50.txt TLE 2103 ms 8752 KB