Submission #1678140


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;
using System.Diagnostics;

class Magatro
{
    private readonly int N = 50;
    private readonly int TimeLimit = 9900;
    private readonly int[] NextY = new int[] { 1, -1, 0, 0 };
    private readonly int[] NextX = new int[] { 0, 0, 1, -1 };
    private char[] S;
    private bool[] P;
    private Random R;
    private Stopwatch Time;

    private int MaxScore = 0;


    private void Init()
    {
        Time = new Stopwatch();
        Time.Start();
        R = new Random();
        P = new bool[N * N];
    }
    private long GetTime()
    {
        Time.Stop();
        var ret = Time.ElapsedMilliseconds;
        Time.Start();
        return ret;
    }
    private void RandomSet()
    {
        for (int i = 0; i < N * N; i++)
        {
            var r = R.Next(125);
            if (r == 0)
            {
                P[i] = !P[i];
            }
        }
    }
    private int GetPoint(int i, int j)
    {
        if (i < 0 || j < 0 || i >= N || j >= N)
        {
            throw new IndexOutOfRangeException();
        }
        return i * N + j;
    }
    private void Scan()
    {
        S = new char[N * N];
        for (int i = 0; i < N; i++)
        {
            var l = Console.ReadLine();
            for (int j = 0; j < N; j++)
            {
                S[GetPoint(i, j)] = l[j];
            }
        }
    }
    private void Write(bool[] ans)
    {
        var sb = new StringBuilder();
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                var p = GetPoint(i, j);
                if (S[p] != '.')
                {
                    sb.Append(S[p]);
                }
                else if (ans[p])
                {
                    sb.Append('+');
                }
                else
                {
                    sb.Append('.');
                }
            }
            sb.Append('\n');
        }
        Console.Write(sb.ToString());
    }
    private char[] Fall(bool[] b)
    {
        var f = new char[N * N];
        for (int j = 0; j < N; j++)
        {
            int h = N - 1;
            for (int i = N - 1; i >= 0; i--)
            {
                var p = GetPoint(i, j);
                if (S[p] != '.' || b[p])
                {
                    f[GetPoint(h, j)] = S[p];
                    h--;
                }
            }
        }
        return f;
    }
    private int Score(char[] c)
    {
        var check = new bool[N * N];
        int maru = 0;
        int batsu = 0;
        for (int j = 0; j < N; j++)
        {
            for (int i = N - 1; i >= 0; i--)
            {
                var gp = GetPoint(i, j);
                var p = c[gp];
                if (p == '\0')
                {
                    break;
                }
                if (p == '.')
                {
                    continue;
                }
                if (check[gp])
                {
                    continue;
                }
                var q = new Queue<int>();
                q.Enqueue(gp);
                check[gp] = true;
                int ss = 1;
                while (q.Count > 0)
                {
                    var pp = q.Dequeue();
                    int ii = pp / N;
                    int jj = pp % N;
                    for (int k = 0; k < 4; k++)
                    {
                        var nexti = ii + NextY[k];
                        var nextj = jj + NextX[k];
                        if (nexti < 0 || nextj < 0 || nexti >= N || nextj >= N)
                        {
                            continue;
                        }
                        var np = GetPoint(nexti, nextj);
                        if (check[np] || c[np] != p)
                        {
                            continue;
                        }
                        ss++;
                        q.Enqueue(np);
                        check[np] = true;
                    }
                }
                switch (p)
                {
                    case 'o':
                        maru = Math.Max(maru, ss);
                        break;
                    case 'x':
                        batsu = Math.Max(batsu, ss);
                        break;
                }
            }
        }
        return maru + batsu;
    }
    private int GetScore(bool[] b)
    {
        var f = Fall(b);
        return Score(f);
    }
    private void DebugWrite(char[] c)
    {
        var sb = new StringBuilder();
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                sb.Append(c[GetPoint(i, j)]);
            }
            sb.Append('\n');
        }
        Console.Write(sb.ToString());
    }
    private int Henkou(int n)//どれだけ変えるか
    {
        return 1;
    }
    private int GetS(int i)
    {
        return 1;
    }
    private bool DoChange(int n, int score)
    {
        return false;
    }
    private bool[] NextRandom(int n)
    {
        var res = P.ToArray();
        int h = Henkou(n);
        while (h > 0)
        {
            var p = R.Next(N * N);
            if (S[p] == '.')
            {
                res[p] = !res[p];
                h -= GetS(p / 50);
            }
        }
        return res;
    }
    private void Calc()
    {
        MaxScore = GetScore(P);
        for (int i = 0; true; i++)
        {
            //Console.WriteLine(i);
            var next = NextRandom(i);
            var score = GetScore(next);

            if (MaxScore < score || DoChange(i, score))
            {
                MaxScore = score;
                P = next;
            }
            if (i % 1000 == 0)
            {
                //Console.WriteLine($"{i} {score}");
                if (GetTime() > TimeLimit)
                {
                    break;
                }
            }

        }
    }
    public void Solve()
    {
        Scan();
        Init();
        //RandomSet();
        Calc();
        Write(P);
        //Console.WriteLine(GetTime());
        //Console.WriteLine(GetScore(P));
        //DebugWrite(Fall(P));
    }
    static public void Main()
    {
        new Magatro().Solve();

    }
}

Submission Info

Submission Time
Task A - ○×ブロック
User mban
Language C# (Mono 4.6.2.0)
Score 3590
Code Size 6690 Byte
Status TLE
Exec Time 10008 ms
Memory 17580 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
Score / Max Score 334 / 2500 0 / 2500 521 / 2500 378 / 2500 440 / 2500 386 / 2500 419 / 2500 292 / 2500 366 / 2500 454 / 2500
Status
AC × 1
TLE × 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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9939 ms 17580 KB
subtask_01_02.txt TLE 10008 ms 17548 KB
subtask_01_03.txt AC 9942 ms 15464 KB
subtask_01_04.txt AC 9991 ms 15424 KB
subtask_01_05.txt AC 9968 ms 15484 KB
subtask_01_06.txt AC 9945 ms 15424 KB
subtask_01_07.txt AC 9940 ms 17520 KB
subtask_01_08.txt AC 9932 ms 15464 KB
subtask_01_09.txt AC 10000 ms 15452 KB
subtask_01_10.txt AC 9961 ms 15420 KB