HackerRank Week of Code - 24 参加日記

C# プログラミングコンテスト

392位/9177人。難易度Hardの「XOR Matrix」が解けそうで解けなく3日ほど苦しんだ(結果は部分正解)。Easy問題は省略する。


Simplified Chess Engine

盤の大きさが4x4、かつクイーン・ルーク・ナイト・ビショップだけが存在するミニチェスを考える。勝利条件は相手のクイーンを取ることとする。盤面g個が与えられたとき、ｍ手以内に先手が必勝かどうかをそれぞれ答えよ。
先手後手それぞれ、クイーンが１個、ルークが０~2個、ナイトとビショップが合計0~２個ある
1 <= g <= 200
1 <= m <= 6

十分に小さいゲーム木なので、MinMax法で簡単に求められる。ただし実装が少し重い。ちなみに、所定の手数までの勝敗なので、Zobrist Hashなどで同一局面を排除するとWAになる。

class Program
{
    enum PIECES { EMPTY, Q, N, B, R, q, n, b, r };

    static void Main(string[] args)
    {
        var g = Int32.Parse(Console.ReadLine());

        while( g > 0 )
        {
            var str = Console.ReadLine().Split();
            var w = Int32.Parse(str[0]);
            var b = Int32.Parse(str[1]);
            var m = Int32.Parse(str[2]);
            var board = GetInitBoard();

            while ( w > 0 ) 
            {
                SetPiece_Init(true, board, Console.ReadLine().Split());
                w--;
            }

            while ( b > 0 ) 
            {
                SetPiece_Init(false, board, Console.ReadLine().Split());
                b--;
            }

            if (MinMax('W', board, m)) Console.WriteLine("YES");
            else Console.WriteLine("NO");

            g--;
        }
    }

    static PIECES[,] GetInitBoard()
    {
        var ret = new PIECES[4, 4];
        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                ret[row, col] = PIECES.EMPTY;
            }
        }
        return ret;
    }

    static void SetPiece_Init(bool isWhite, PIECES[,] board, string[] inStrs)
    {
        var piece = GetPiece(!isWhite ? inStrs[0].ToLower()[0] : inStrs[0][0]);
        var col = inStrs[1][0] - 'A';
        var row = inStrs[2][0] - '1';
        MovePiece(board, -1, -1, row, col, piece).Item2;
    }

    static PIECES GetPiece(char p)
    {
        switch (p) {
            case 'Q':
                return PIECES.Q;
            case 'N':
                return PIECES.N;
            case 'B':
                return PIECES.B;
            case 'R':
                return PIECES.R;
            case 'q':
                return PIECES.q;
            case 'n':
                return PIECES.n;
            case 'b':
                return PIECES.b;
            case 'r':
                return PIECES.r;
        }
        return PIECES.EMPTY;
    }

    //return IsTerminalState
    static bool MovePiece(PIECES[,] board, int prevRow, int prevCol, int row, int col, PIECES piece)
    {
        var isTerminal = false;

        if (prevRow != -1) board[prevRow, prevCol] = PIECES.EMPTY;

        if (board[row, col] != PIECES.EMPTY)
        {
            if (board[row, col] == PIECES.Q || board[row, col] == PIECES.q) isTerminal = true;
        }

        board[row, col] = piece;
        return isTerminal;
    }

    static char GetNextTurn(char turn)
    {
        return turn == 'W' ? 'B' : 'W';
    }

    static bool IsHisPiece(char turn, PIECES piece)
    {
        if(piece == PIECES.EMPTY) return false;

        if (turn == 'W')
            return piece == PIECES.Q || piece == PIECES.N || piece == PIECES.B || piece == PIECES.R;

        if (turn == 'B')
            return piece == PIECES.q || piece == PIECES.n || piece == PIECES.b || piece == PIECES.r;

        return false;
    }

    static bool Win(PIECES[,] board, char turn)
    {
        bool Q_exist = false;
        bool q_exist = false;

        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                if(board[row, col] == PIECES.Q) Q_exist = true;
                if(board[row, col] == PIECES.q) q_exist = true;
            }
        }

        if(turn == 'W' && !q_exist) return true;
        if(turn == 'B' && !Q_exist) return true;
        return false;
    }

    static PIECES[,] CopyBoard(PIECES[,] org)
    {
        var ret = new PIECES[4, 4];
        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                ret[row, col] = org[row, col];
            }
        }
        return ret;
    }

    static bool IsInRange(int row, int col)
    {
        return IsInRange(row) && IsInRange(col);
    }

    static bool IsInRange(int pos)
    {
        return pos >= 0 && pos < 4;
    }

    static int[,] Moves_N = new int[,]
    {
        { 2, 1}, { 1, 2}, { -1, 2}, { -2, 1}, { -2, -1}, { -1, -2}, { 1, -2}, { 2, -1},
    };

    static bool IsEnemy(PIECES p, PIECES p2)
    {
        if (p == PIECES.Q || p == PIECES.R || p == PIECES.B || p == PIECES.N)
            return p2 == PIECES.q || p2 == PIECES.r || p2 == PIECES.b || p2 == PIECES.n;

        if (p == PIECES.q || p == PIECES.r || p == PIECES.b || p == PIECES.n)
            return p2 == PIECES.Q || p2 == PIECES.R || p2 == PIECES.B || p2 == PIECES.N;

        return false;
    }

    static void TryMove(ref List<Tuple<int, int>> moves, PIECES[,] board, int row, int col, PIECES piece, int rowDiff, int colDiff)
    {
        row += rowDiff;
        col += colDiff;

        while (IsInRange(row, col))
        {
            if (board[row, col] == PIECES.EMPTY)
            {
                moves.Add(new Tuple<int, int>(row, col));
            }
            else if(IsEnemy(piece, board[row, col]))
            {
                moves.Add(new Tuple<int, int>(row, col));
                break;
            }
            else
            {
                break;
            }
            row += rowDiff;
            col += colDiff;
        }
    }

    static List<Tuple<int, int>> GetNextPositions(int row, int col, PIECES piece, PIECES[,] board)
    {
        var ret = new List<Tuple<int, int>>();

        if (piece == PIECES.N || piece == PIECES.n)
        {
            for (int i = 0; i < Moves_N.GetLength(0); i++)
            {
                var nextRow = row + Moves_N[i, 0];
                var nextCol = col + Moves_N[i, 1];
                if (IsInRange(nextRow, nextCol))
                {
                    if(board[nextRow, nextCol] == PIECES.EMPTY || IsEnemy(piece, board[nextRow, nextCol]))
                        ret.Add(new Tuple<int, int>(nextRow, nextCol));
                }
            }
        }
        else
        {
            switch (piece)
            {
                case PIECES.Q:
                case PIECES.q:
                    TryMove(ref ret, board, row, col, piece, 1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, -1);
                    TryMove(ref ret, board, row, col, piece, 1, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 1);
                    TryMove(ref ret, board, row, col, piece, 1, -1);
                    TryMove(ref ret, board, row, col, piece, -1, -1);
                    break;
                case PIECES.R:
                case PIECES.r:
                    TryMove(ref ret, board, row, col, piece, 1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, -1);
                    break;
                case PIECES.B:
                case PIECES.b:
                    TryMove(ref ret, board, row, col, piece, 1, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 1);
                    TryMove(ref ret, board, row, col, piece, 1, -1);
                    TryMove(ref ret, board, row, col, piece, -1, -1);
                    break;
            }
        }

        return ret;
    }

    //turn: 'W' or 'B'
    //return true if the player won
    static bool MinMax(char turn, PIECES[,] board, int depth)
    {
        //White could not capture black's Qween within m moves
        if (depth == 0) return turn == 'W' ? false : true;

        var nextTurn = GetNextTurn(turn);

        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                if (IsHisPiece(turn, board[row, col]))
                {
                    foreach (var nextPos in GetNextPositions(row, col, board[row, col], board))
                    {
                        var nextBoard = CopyBoard(board);
                        var nextIsTerm = MovePiece(nextBoard, row, col, nextPos.Item1, nextPos.Item2, board[row, col]);

                        if (nextIsTerm)
                        {
                            if (Win(nextBoard, turn)) return true;
                        }
                        else
                        {
                            if (!MinMax(nextTurn, nextBoard, depth - 1)) return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}


XOR Matrix

数列a[0], a[1]... a[n]が与えられる。次の操作をm-1回行ったときの最終的な値を出力せよ。

  • i < n-1 ならa[i]へ XOR(a[i], a[i+1])を代入
  • i = n-1 ならa[i]へ XOR(a[i], a[0])を代入

1 <= n <= 10^5
0 <= m <= 10^18 - 1
0 <= a[j] <= 10^9

たとえば要素0にXOR加算する要素は、
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
のようにパスカルのフラクタルと同じ形になる。
(最上段は初期状態、その後は上から、操作１終了後、操作２終了後・・・の順)
パスカルのフラクタルがすべて1になるのは2^k回目のときで、その次の状態が該当要素と最終要素のXORになる。よって、現在の状態から2^kだけ飛ばして計算することが可能。
要素0以外も、シフトするだけで同じパターンとなる。

static void Main(string[] args)
{
    var str = Console.ReadLine().Split();
    var n = Int32.Parse(str[0]);
    var m = long.Parse(str[1]);
    var a = ReadLine().Split().Select(s => long.Parse(s)).ToArray();

    m--;
    while (m > 0)
    {
        long cnt = 1;
        while (cnt << 1 <= m)
        {
            cnt <<= 1;
        }

        var tmp = new long[a.Length];
        for (long i = 0; i < a.Length; i++)
        {
            tmp[i] = a[i] ^ a[(i + cnt) % a.Length];
        }
        a = tmp;
        m -= cnt;
    }

    foreach (var v in a)
    {
        Console.Write(v.ToString() + " ");
    }
    Console.WriteLine();
}


Shashank and the Palindromic Strings

文字列のリスト { a = [a_0, a_1, ..., a_{n-1} ] }がq個与えられる。それぞれについて次の条件を満たすパターン数を答えよ。

  • { s_{i} } を {a_{i}} の空文字以外のサブシーケンスとしたとき、 {s_0 + s_1+ ...+ s_{n-1}} が回文になる

1 <= q <= 50
1 <= n <= 50

全文字列を連結した文字列sを考える。DPを次のように定義する。
{ dp[r, c, was1, was2] } ：セグメント[r, c]で回文になるサブシーケンスのパターン数。
　was1: s[r]の元文字列にある文字を含むかどうか
　was2: s[c]の元文字列にある文字を含むかどうか
更新条件は２通りある。
１. s[r]とs[c]の元文字列が同じとき

// ｒ・ｃの元文字列を使わないのは空文字のパターンのみ
dp[r, c, 0, 0] = 1;

// s[r]とs[l]を回文として使わないパターン
dp[r, c, 1, 1] = dp[r, c - 1, 1, 1] + dp[r + 1, c, 1, 1];
dp[r, c, 1, 1] -= dp[r + 1, c - 1, 1, 1]; // 重複を排除

// s[r]とs[l]を回文として使うパターン
if (s[r] == s[c])
{
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 0];
}

２. s[r]とs[c]の元文字列が違うとき
２-１. s[r+1]とs[r]の元文字列が違い、さらにs[c-1]とs[c]の元文字列が違う場合

// rが元文字列の右端で、cが元文字列の左端のとき

// どちらの文字列も使わない場合は、その内側の結果と同じ
dp[r, c, 0, 0] = (r + 1 == c ? 1 : dp[r + 1, c - 1, 1, 1]);

// どちらかの文字列を使う場合は、使わない側をはぶいたパターン数に一致
dp[r, c, 1, 0] = dp[r, c - 1, 1, 1];
dp[r, c, 0, 1] = dp[r + 1, c, 1, 1];

// どちらも使うとき。s[r]とs[c]が一致しないと0になる
dp[r, c, 1, 1] = (s[r] == s[c] ? dp[r, c, 0, 0] : 0);

２-２. s[r+1]とs[r]の元文字列が違うが、s[c-1]とs[c]の元文字列は同じ場合

// s[r]が元文字列の右端だがs[c]は元文字列の左端ではないとき

dp[r, c, 0, 0] = dp[r, c - 1, 0, 0];    //s[r]、s[c]いずれの元文字列も使わない
                                        //dp[r + 1, c - 1, 0, 0]のような気がするが・・・？
dp[r, c, 1, 0] = dp[r, c - 1, 1, 0];    //s[r]の元文字列を使う
dp[r, c, 0, 1] = dp[r + 1, c, 1, 1];    //s[r]の元文字列を使わない
dp[r, c, 1, 1] = dp[r, c - 1, 1, 1];    //どっちも使う->s[r]を使うしかない

if (s[r] == s[c])
{
    //s[r]とs[c]が同じなら、この２つを回文に使うパターンが追加される
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 0];

    //元文字列が隣り合っていた場合！
    if (A[r] + 1 == A[c])
    {
        dp[r, c, 1, 1]++; // 1増えるのみ
    }
}

２-３. s[r+1]とs[r]の元文字列が同じだが、s[c-1]とs[c]の元文字列は違う場合
　（２-２と同様）
２-４. s[r+1]とs[r]の元文字列も、s[c-1]とs[c]の元文字列も違う場合

// s[r]が元文字列の右端ではなく、s[c]が元文字列の左端ではないとき

// どちらの元文字列も使わないときは1つ内側の結果と同じ
dp[r, c, 0, 0] = dp[r + 1, c - 1, 0, 0];

// 片方の元文字列を使わないときは、使わない側を１つ内側にした結果と同じ
dp[r, c, 0, 1] = dp[r + 1, c, 0, 1];
dp[r, c, 1, 0] = dp[r, c - 1, 1, 0];

// どちらの元文字列も使うとき
dp[r, c, 1, 1] = dp[r + 1, c, 1, 1] + dp[r, c - 1, 1, 1];
dp[r, c, 1, 1] -= dp[r + 1, c - 1, 1, 1];   // 重複を排除

if (s[r] == s[c])
{
    // s[r]とs[c]が同じ文字なら、両方の元文字列を使うパターンに
    // 内側の結果すべてが加算される
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 0];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 0];
}

最終的な実装は省略。