ARC153-B Grid Rotations

問題へのリンク

C#のソース(ベクトルから配列を復元する方法)

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5");
            WillReturn.Add("abcde");
            WillReturn.Add("fghij");
            WillReturn.Add("klmno");
            WillReturn.Add("pqrst");
            WillReturn.Add("1");
            WillReturn.Add("3 3");
            //mlkon
            //hgfji
            //cbaed
            //rqpts
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 7");
            WillReturn.Add("atcoder");
            WillReturn.Add("regular");
            WillReturn.Add("contest");
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            WillReturn.Add("2 5");
            //testcon
            //oderatc
            //ularreg
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 2");
            WillReturn.Add("ac");
            WillReturn.Add("wa");
            WillReturn.Add("3");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            //ac
            //wa
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal int A;
        internal int B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int H = wkArr[0];
        int W = wkArr[1];
        int UB_X = W - 1;
        int UB_Y = H - 1;

        char[,] BanArr = CreateBanArr(InputList.Skip(1).Take(H));

        foreach (string EachStr in InputList.Skip(1 + H + 1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        // 横方向だけで考える
        int XInd0 = 0; // 0のInd
        int XInd1 = 1; // 1のInd
        foreach (ABInfoDef EachABInfo in mABInfoList) {
            int Range1Sta = 0;
            int Range1End = EachABInfo.B - 1;

            int Range2Sta = Range1End + 1;
            int Range2End = UB_X;

            XInd0 = ChangeInd(Range1Sta, Range1End, XInd0);
            XInd0 = ChangeInd(Range2Sta, Range2End, XInd0);
            XInd1 = ChangeInd(Range1Sta, Range1End, XInd1);
            XInd1 = ChangeInd(Range2Sta, Range2End, XInd1);
        }

        // 縦方向だけで考える
        int YInd0 = 0; // 0のInd
        int YInd1 = 1; // 0のInd
        foreach (ABInfoDef EachABInfo in mABInfoList) {
            int Range1Sta = 0;
            int Range1End = EachABInfo.A - 1;

            int Range2Sta = Range1End + 1;
            int Range2End = UB_Y;

            YInd0 = ChangeInd(Range1Sta, Range1End, YInd0);
            YInd0 = ChangeInd(Range2Sta, Range2End, YInd0);
            YInd1 = ChangeInd(Range1Sta, Range1End, YInd1);
            YInd1 = ChangeInd(Range2Sta, Range2End, YInd1);
        }
        int?[] XIndArr = CreateArr(XInd0, XInd1, UB_X);
        int?[] YIndArr = CreateArr(YInd0, YInd1, UB_Y);

        var sb = new System.Text.StringBuilder();
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                int XInd = XIndArr[LoopX].Value;
                int YInd = YIndArr[LoopY].Value;
                sb.Append(BanArr[XInd, YInd]);
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    // 反転する添字の区間を引数として、反転後の添字を返す
    static int ChangeInd(int pRangeSta, int pRangeEnd, int pCurrInd)
    {
        if ((pRangeSta <= pCurrInd && pCurrInd <= pRangeEnd) == false) {
            return pCurrInd;
        }
        int SumInd = pRangeSta + pRangeEnd;
        return SumInd - pCurrInd;
    }

    // Ind1とInd2を要素数として、配列を返す
    static int?[] CreateArr(int pInd0, int pInd1, int pUB)
    {
        int?[] WillReturn = new int?[pUB + 1];
        WillReturn[pInd0] = 0;
        WillReturn[pInd1] = 1;

        // ベクトルを求める
        int Vect = pInd1 - pInd0;

        // 配列の端同士の場合
        if (pInd0 == 0 && pInd1 == pUB) {
            Vect = -1;
        }
        if (pInd0 == pUB && pInd1 == 0) {
            Vect = 1;
        }

        int CurrInd = pInd1 + Vect;
        int CurrVal = 2;

        Action ChangeCurrInd = () =>
        {
            if (pUB < CurrInd) CurrInd = 0;
            if (CurrInd < 0) CurrInd = pUB;
        };
        ChangeCurrInd();

        while (true) {
            if (WillReturn[CurrInd].HasValue) break;
            WillReturn[CurrInd] = CurrVal++;

            CurrInd += Vect;
            ChangeCurrInd();
        }
        return WillReturn;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

C#のソース(ImplicitTreapを使う方法)

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

class Program
{
    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal int A;
        internal int B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int H = wkArr[0];
        int W = wkArr[1];
        int UB_X = W - 1;
        int UB_Y = H - 1;

        char[,] BanArr = CreateBanArr(InputList.Skip(1).Take(H));

        foreach (string EachStr in InputList.Skip(1 + H + 1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        var InsImplicitTreapX = new ImplicitTreap();
        for (int I = 0; I <= UB_X; I++) {
            InsImplicitTreapX.internal_insert(I, I);
        }

        var InsImplicitTreapY = new ImplicitTreap();
        for (int I = 0; I <= UB_Y; I++) {
            InsImplicitTreapY.internal_insert(I, I);
        }

        // 横方向だけで考える
        foreach (ABInfoDef EachABInfo in mABInfoList) {
            int Range1Sta = 0;
            int Range1End = EachABInfo.B - 1;

            int Range2Sta = Range1End + 1;
            int Range2End = UB_X;

            InsImplicitTreapX.internal_reverse(Range1Sta, Range1End);
            InsImplicitTreapX.internal_reverse(Range2Sta, Range2End);
        }

        // 縦方向だけで考える
        foreach (ABInfoDef EachABInfo in mABInfoList) {
            int Range1Sta = 0;
            int Range1End = EachABInfo.A - 1;

            int Range2Sta = Range1End + 1;
            int Range2End = UB_Y;

            InsImplicitTreapY.internal_reverse(Range1Sta, Range1End);
            InsImplicitTreapY.internal_reverse(Range2Sta, Range2End);
        }

        var XValList = InsImplicitTreapX.internal_GetValList();
        var YValList = InsImplicitTreapY.internal_GetValList();

        var sb = new System.Text.StringBuilder();
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                long XInd = XValList[LoopX];
                long YInd = YValList[LoopY];
                sb.Append(BanArr[XInd, YInd]);
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

#region ImplicitTreap
internal class ImplicitTreap
{
    const long INF = long.MaxValue;
    static private Random rnd = new Random();
    private class Node
    {
        internal long value;
        internal long min;
        internal long lazy;
        internal long priority;
        internal long cnt;
        internal bool rev;
        internal Node l;
        internal Node r;

        // コンストラクタ
        internal Node(long value, long priority)
        {
            this.value = value;
            this.min = INF;
            this.lazy = 0;
            this.priority = priority;
            this.cnt = 1;
            this.rev = false;
            this.l = null;
            this.r = null;
        }
    }
    Node root = null;

    private long private_cnt(Node t)
    {
        return (t != null) ? t.cnt : 0;
    }

    private long private_get_min(Node t)
    {
        return (t != null) ? t.min : INF;
    }

    private void private_update_cnt(Node t)
    {
        if ((t != null)) {
            t.cnt = 1 + private_cnt(t.l) + private_cnt(t.r);
        }
    }

    private void private_update_min(Node t)
    {
        if ((t != null)) {
            t.min = Math.Min(t.value, Math.Min(private_get_min(t.l), private_get_min(t.r)));
        }
    }

    private void private_pushup(Node t)
    {
        private_update_cnt(t); private_update_min(t);
    }

    private void private_pushdown(Node t)
    {
        if ((t != null) && (t.rev)) {
            t.rev = false;
            private_swap(ref (t.l), ref (t.r));
            if ((t.l) != null) t.l.rev = (t.l.rev == false);
            if ((t.r) != null) t.r.rev = (t.r.rev == false);
        }
        if ((t != null) && (t.lazy != 0)) {
            if ((t.l) != null) {
                t.l.lazy += t.lazy;
                t.l.min += t.lazy;
            }
            if ((t.r) != null) {
                t.r.lazy += t.lazy;
                t.r.min += t.lazy;
            }
            t.value += t.lazy;
            t.lazy = 0;
        }
        private_pushup(t);
    }

    private void private_split(Node t, long key, ref Node l, ref Node r)
    {
        if (t == null) {
            l = r = null;
            return;
        }
        private_pushdown(t);
        long implicit_key = private_cnt(t.l) + 1;
        if (key < implicit_key) {
            private_split(t.l, key, ref l, ref t.l); r = t;
        }
        else {
            private_split(t.r, key - implicit_key, ref t.r, ref r); l = t;
        }
        private_pushup(t);
    }

    private void private_insert(ref Node t, long key, Node item)
    {
        Node t1 = null;
        Node t2 = null;
        private_split(t, key, ref t1, ref t2);
        private_merge(ref t1, t1, item);
        private_merge(ref t, t1, t2);
    }

    private void private_merge(ref Node t, Node l, Node r)
    {
        private_pushdown(l);
        private_pushdown(r);
        if (l == null || r == null) {
            t = ((l != null) ? l : r);
        }
        else if (l.priority > r.priority) {
            private_merge(ref l.r, l.r, r); t = l;
        }
        else {
            private_merge(ref r.l, l, r.l); t = r;
        }
        private_pushup(t);
    }

    private void private_erase(ref Node t, long key)
    {
        Node t1 = null, t2 = null, t3 = null;
        private_split(t, key + 1, ref t1, ref t2);
        private_split(t1, key, ref t1, ref t3);
        private_merge(ref t, t1, t2);
    }

    private void private_add(Node t, long l, long r, long x)
    {
        Node t1 = null, t2 = null, t3 = null;
        private_split(t, l, ref t1, ref t2);
        private_split(t2, r - l, ref t2, ref t3);
        t2.lazy += x;
        t2.min += x;
        private_merge(ref t2, t2, t3);
        private_merge(ref t, t1, t2);
    }

    private long private_findmin(Node t, long l, long r)
    {
        Node t1 = null, t2 = null, t3 = null;
        private_split(t, l, ref t1, ref t2);
        private_split(t2, r - l, ref t2, ref t3);
        long ret = t2.min;
        private_merge(ref t2, t2, t3);
        private_merge(ref t, t1, t2);
        return ret;
    }

    private void private_reverse(Node t, long l, long r)
    {
        if (l > r) return;
        Node t1 = null, t2 = null, t3 = null;
        private_split(t, l, ref t1, ref t2);
        private_split(t2, r - l, ref t2, ref t3);
        t2.rev = (t2.rev == false);
        private_merge(ref t2, t2, t3);
        private_merge(ref t, t1, t2);
    }

    // [l, r)の先頭がmになるように左シフトさせる。std::rotateと同じ仕様
    private void private_rotate(Node t, long l, long m, long r)
    {
        private_reverse(t, l, r);
        private_reverse(t, l, l + r - m);
        private_reverse(t, l + r - m, r);
    }

    private void private_dump(Node t)
    {
        if (t == null) return;
        private_pushdown(t);
        private_dump(t.l);
        Console.Write("{0} ", t.value);
        private_dump(t.r);
    }

    private void private_GetValList(Node t)
    {
        if (t == null) return;
        private_pushdown(t);
        private_GetValList(t.l);
        mValList.Add(t.value);
        private_GetValList(t.r);
    }

    private void private_swap(ref Node p1, ref Node p2)
    {
        Node tmp = p1;
        p1 = p2;
        p2 = tmp;
    }

    // 指定Indに値を追加
    internal void internal_insert(long pos, long x)
    {
        private_insert(ref root, pos, new Node(x, rnd.Next()));
    }

    // 閉区間[l,r]に値を加算
    internal void internal_add(long l, long r, long x)
    {
        r++; // 閉区間に変更
        private_add(root, l, r, x);
    }

    // 閉区間[l,r]の最小値を取得
    internal long internal_findmin(long l, long r)
    {
        r++; // 閉区間に変更
        return private_findmin(root, l, r);
    }

    // 指定Indを消す
    internal void internal_erase(long pos)
    {
        private_erase(ref root, pos);
    }

    // 閉区間[l,r]を反転
    internal void internal_reverse(long l, long r)
    {
        r++; // 閉区間に変更
        private_reverse(root, l, r);
    }

    // [l, r]の先頭がmになるように左シフト。std::rotateと同じ仕様
    internal void internal_rotate(long l, long m, long r)
    {
        r++; // 閉区間に変更
        private_rotate(root, l, m, r);
    }

    // デバッグ表示
    internal void internal_dump()
    {
        private_dump(root);
        Console.WriteLine();
    }

    // 値のListを返す
    private List<long> mValList = new List<long>();
    internal List<long> internal_GetValList()
    {
        mValList.Clear();
        private_GetValList(root);
        return mValList;
    }
}
#endregion

解説

縦方向と横方向は、分けて考えることができます。

考察すると、
配列で最初の何列目を見ているかを管理するようにして、
回転をシュミレーションすると、
最初の0列目と1列目さえ分かれば、後は、ベクトルから配列を復元できると分かります。

0 1 2 3 4 5 6 7 8 9
回転すると
5 4 3 2 1 0 9 8 7 6
回転すると
3 4 5 6 7 8 9 0 1 2
回転すると
4 3 2 1 0 9 8 7 6 5

0と1が配列の端同士のケースがコーナケースとしてあるので
配列の復元時に、注意する必要があります。