Submission #1678359


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;

struct S
{
    public int Score;
    public bool[] B;
    public S(int score, bool[] b)
    {
        B = b;
        Score = score;
    }
}

class Magatro
{
    private readonly int N = 50;
    private readonly int TimeLimit = 9600 * 1;
    private readonly int BeamWidth = 5;
    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[] MaxP;
    private Random R;
    private Stopwatch Time;


    private void Init()
    {
        Time = new Stopwatch();
        Time.Start();
        R = new Random();
    }
    private long GetTime()
    {
        Time.Stop();
        var ret = Time.ElapsedMilliseconds;
        Time.Start();
        return ret;
    }
    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 bool[] NextRandom(bool[] before)
    {
        var res = before.ToArray();
        var p = R.Next(N * N);
        if (S[p] == '.')
        {
            res[p] = !res[p];
        }
        return res;
    }
    private void Calc()
    {
        var ans = new S[BeamWidth];
        for (int i = 0; i < BeamWidth; i++)
        {
            ans[i] = new S(-1, new bool[2500]);
        }
        for (int ii = 0; true; ii++)
        {
            var w = new S[BeamWidth * 10 + 5];
            for (int i = 0; i < BeamWidth; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    var nr = NextRandom(ans[i].B);
                    var nscore = GetScore(nr);
                    w[i * 10 + j] = new S(nscore, nr);
                }
            }
            for (int i = 0; i < BeamWidth; i++)
            {
                w[BeamWidth * 10 + i] = ans[i];
            }
            Array.Sort(w, (a, b) => -a.Score.CompareTo(b.Score));
            for (int i = 0; i < BeamWidth; i++)
            {
                ans[i] = w[i];
            }
            if (ii % 20 == 0)
            {
                if (GetTime() > TimeLimit)
                {
                    break;
                }
            }
        }
        MaxP = ans[0].B;

    }
    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 4691
Code Size 6384 Byte
Status AC
Exec Time 9776 ms
Memory 33824 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 475 / 2500 495 / 2500 537 / 2500 449 / 2500 492 / 2500 505 / 2500 523 / 2500 336 / 2500 417 / 2500 462 / 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 9750 ms 31916 KB
subtask_01_02.txt AC 9700 ms 31992 KB
subtask_01_03.txt AC 9691 ms 31920 KB
subtask_01_04.txt AC 9712 ms 31944 KB
subtask_01_05.txt AC 9776 ms 33744 KB
subtask_01_06.txt AC 9673 ms 31900 KB
subtask_01_07.txt AC 9722 ms 29848 KB
subtask_01_08.txt AC 9655 ms 31892 KB
subtask_01_09.txt AC 9735 ms 33824 KB
subtask_01_10.txt AC 9684 ms 29844 KB