AtCoder Beginner Contest 025

Submission #434480

Source codeソースコード

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Myon
{

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

    Scanner cin;

    List<int> pos = new List<int>();
    List<int> num = new List<int>();
    int[] posrev;
    int N = 5;
    int[,] board;
    
    void calc()
    {
        cin = new Scanner();
        board = new int[N, N];
        posrev = new int[N * N];
        for (int i = 0; i < posrev.Length; i++)
        {
            posrev[i] = -1;
        }

        for (int i = 0; i < 25; i++)
        {
            num.Add(i);
        }

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                board[i, j] = cin.nextInt() - 1;
                if (board[i, j] == -1)
                {
                    int num = i * 5 + j;
                    posrev[num] = pos.Count; 
                    pos.Add(num);
                }
                else
                {
                    num.Remove(board[i, j]);
                }
            }
        }

        long[] dp = new long[1 << pos.Count];
        dp[0] = 1;

        long mod = 1000000007;

        for (int i = 0; i < (1 << pos.Count) - 1; i++)
        {
            int count = bitCount(i);
            int nownumber = num[count];
            bool[,] used = new bool[N, N];
            bool flag2 = true;
            for (int j = 0; j < posrev.Length; j++)
            {
                int y = j / 5;
                int x = j % 5;
                if (posrev[j] == -1)
                {
                    if (board[y, x] < nownumber)
                    {
                        used[y, x] = true;
                        int prenumber = -1;
                        if (count != 0) prenumber = num[count - 1];
                        if (prenumber < board[y, x])
                        {
                            if (y != 0 && y != 4)
                            {
                                int up = board[y + 1, x];
                                int down = board[y - 1, x];
                                if (up == -1)
                                {
                                    int p = posrev[(y + 1) * 5 + (x)];
                                    if ((i >> p) % 2 == 1) up = prenumber;
                                    else up = nownumber;
                                }
                                if (down == -1)
                                {
                                    int p = posrev[(y - 1) * 5 + (x)];
                                    if ((i >> p) % 2 == 1) down = prenumber;
                                    else down = nownumber;
                                }

                                if ((up > board[y, x]) != (down > board[y, x]))
                                {
                                    flag2 = false;
                                    break;
                                }
                            }
                            if (x != 0 && x != 4)
                            {
                                int up = board[y, x + 1];
                                int down = board[y, x - 1];
                                if (up == -1)
                                {
                                    int p = posrev[(y) * 5 + (x + 1)];
                                    if ((i >> p) % 2 == 1) up = prenumber;
                                    else up = nownumber;
                                }
                                if (down == -1)
                                {
                                    int p = posrev[(y) * 5 + (x - 1)];
                                    if ((i >> p) % 2 == 1) down = prenumber;
                                    else down = nownumber;
                                }

                                if ((up > board[y, x]) != (down > board[y, x]))
                                {
                                    flag2 = false;
                                    break;
                                }
                            }
                        }
                    }
                }
                else
                {
                    if ((i >> posrev[j]) % 2 == 1)
                    {
                        used[y, x] = true;
                    }
                }
            }
            if (!flag2) continue;

            for (int j = 0; j < pos.Count; j++)
            {
                if ((i >> j) % 2 == 1) continue;
                int y = pos[j] / 5;
                int x = pos[j] % 5;
                bool flag = true;
                if (y != 0 && y != 4)
                {
                    if (used[y + 1, x] != used[y - 1, x])
                    {
                        flag = false;
                        break;
                    }
                }
                if (x != 0 && x != 4)
                {
                    if (used[y, x + 1] != used[y, x - 1])
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                {
                    dp[i | (1 << j)] += dp[i];
                    dp[i | (1 << j)] %= mod;
                }
            }
        }

        Console.WriteLine(dp[(1 << pos.Count) - 1]);
    }

    int bitCount(long x)
    {
        x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
        x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
        x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
        x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
        x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
        return (int)((x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff));
    }

}





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 next();
    }

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

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

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

}

Submission

Task問題 D - 25個の整数
User nameユーザ名 chokudai
Created time投稿日時
Language言語 C# (Mono 3.2.1.0)
Status状態 WA
Score得点 0
Source lengthソースコード長 6790 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt
Subtask1 0 / 30 sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt,test-1-01.txt,test-1-02.txt,test-1-03.txt,test-1-04.txt,test-1-05.txt,test-1-06.txt,test-1-07.txt,test-1-08.txt,test-1-09.txt,test-1-10.txt,test-1-11.txt,test-1-12.txt,test-1-13.txt,test-1-14.txt,test-1-15.txt
Subtask2 0 / 70 sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt,test-1-01.txt,test-1-02.txt,test-1-03.txt,test-1-04.txt,test-1-05.txt,test-1-06.txt,test-1-07.txt,test-1-08.txt,test-1-09.txt,test-1-10.txt,test-1-11.txt,test-1-12.txt,test-1-13.txt,test-1-14.txt,test-1-15.txt,test-2-01.txt,test-2-02.txt,test-2-03.txt,test-2-04.txt,test-2-05.txt,test-2-06.txt,test-2-07.txt,test-2-08.txt,test-2-09.txt,test-2-10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample-01.txt AC 156 ms 8840 KB
sample-02.txt AC 137 ms 8996 KB
sample-03.txt AC 146 ms 8964 KB
sample-04.txt AC 140 ms 8992 KB
test-1-01.txt AC 136 ms 8968 KB
test-1-02.txt AC 130 ms 8912 KB
test-1-03.txt WA
test-1-04.txt WA
test-1-05.txt WA
test-1-06.txt WA
test-1-07.txt AC 133 ms 8960 KB
test-1-08.txt WA
test-1-09.txt WA
test-1-10.txt AC 135 ms 8964 KB
test-1-11.txt AC 129 ms 8996 KB
test-1-12.txt WA
test-1-13.txt AC 131 ms 8992 KB
test-1-14.txt WA
test-1-15.txt WA
test-2-01.txt WA
test-2-02.txt WA
test-2-03.txt WA
test-2-04.txt WA
test-2-05.txt WA
test-2-06.txt WA
test-2-07.txt WA
test-2-08.txt WA
test-2-09.txt WA
test-2-10.txt WA