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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |