Submission #1678290


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 = 9600 * 1;
    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 bool[] MaxP;
    private Random R;
    private Stopwatch Time;
    private int MaxScore = 0;
    private int TScore = 0;


    private void Init()
    {
        Time = new Stopwatch();
        Time.Start();
        R = new Random();
        P = new bool[N * N];
        MaxP = 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)//どれだけ変えるか
    {
        if (N < 10000) return 3;
        else if (N < 20000) return 2;
        else return 1;
    }
    private int GetS(int i)
    {
        return 1;
    }
    private bool DoChange(int n, int score)
    {
        var sa = MaxScore - score;
        if (sa > 15) return false;
        return 0 >= R.Next(n / 10 + 500);
    }
    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 (TScore < score || DoChange(i, score))
            {
                TScore = score;
                P = next;
            }
            if (MaxScore < score)
            {
                MaxScore = score;
                MaxP = next;
            }
            if (MaxScore * 95 > TScore * 100)
            {
                TScore = MaxScore;
                P = MaxP;
            }
            if (i % 1000 == 0)
            {
                //Console.WriteLine($"{i} {TScore}");
                if (GetTime() > TimeLimit)
                {
                    break;
                }
            }

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

    }
}

Submission Info

Submission Time
Task A - ○×ブロック
User mban
Language C# (Mono 4.6.2.0)
Score 5111
Code Size 7189 Byte
Status AC
Exec Time 9777 ms
Memory 17668 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 489 / 2500 507 / 2500 537 / 2500 449 / 2500 603 / 2500 444 / 2500 543 / 2500 459 / 2500 520 / 2500 560 / 2500
Status
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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9759 ms 17644 KB
subtask_01_02.txt AC 9720 ms 13524 KB
subtask_01_03.txt AC 9658 ms 15576 KB
subtask_01_04.txt AC 9777 ms 15448 KB
subtask_01_05.txt AC 9767 ms 17668 KB
subtask_01_06.txt AC 9751 ms 13452 KB
subtask_01_07.txt AC 9730 ms 15540 KB
subtask_01_08.txt AC 9664 ms 15496 KB
subtask_01_09.txt AC 9654 ms 15568 KB
subtask_01_10.txt AC 9637 ms 15520 KB