おにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎり日記

TCOR1A

16:29

最初手が震えてたｗ

Easy

全探索

高さ２つ決めて（高さの差の絶対値は１以下）、点数数える。

高さ１つ決めて、もう１個はその決めたやつ＋１としたら、タイピング量減る。

整数なのにaverageとか変なことは止めよう。

    public int getMinimum(string[] area)
    {
        int res = int.MaxValue;
        int row = area.Length;
        int col = area[0].Length;
        for (int k = 0; k < 10; k++)
        {
            for (int y = 0; y < 10; y++)
            {
                if (Math.Abs(k - y) > 1)    //すぐに枝狩するので、計算量は大して増えない（増えても問題ないけど）。
                    continue;
                int tmp = 0;
                for (int i = 0; i < row; i++)
                {
                    for (int j = 0; j < col; j++)
                    {
                        tmp += Math.Min(Math.Abs(area[i][j] - '0' - y), Math.Abs(area[i][j] - '0' - k));
                    }//for k
                }//for j
                res = Math.Min(res, tmp);
            }
        }//for i
        return res;
    }

Medium

Max(L[i]-R[i])のジャンプが必要なことはすぐに分かる。

そこから増やしていく。

今のジャンプでどこかの区間とぶつかるなら、

その区間までに(まだ必要なジャンプの距離)/(そこに行くまでにジャンプした回数)を加える。

これでその区間についてはぶつからなくなる。

これを繰り返しまくる。

本番中はこのアルゴリズムが本当に停止するのかを証明できなかった。

どこかの区間とぶつかってジャンプ距離を伸ばすと、

その区間に着くまでに必要なジャンプの回数が１減る。

最大で必要なジャンプの回数はD=30,000回なので、

この更新は高々N*D=1,500,000回。

確かに終了する。

あとジャンプの距離を加えるのを、eps足したりしてないのも不安やった。

もとが整数だし大丈夫だろとか適当に思った。

結果通ったけど、なんかあんま。。。。

    const double eps = 1e-9;
    public double getMinimum(int D, int[] L, int[] R)
    {
        int len = L.Length;
        double res = 0;
        for (int i = 0; i < len; i++)
        {
            res = Math.Max(res, R[i] - L[i]);
        }//for i
        while (true)
        {
            bool flg = true;
            for (int i = 0; i < len; i++)
            {
                int tmp = (int)(L[i] / res + eps) + 1;
                if (L[i] < tmp * res && tmp * res < R[i])
                {
                    double rem = R[i] - tmp * res;
                    res += rem / tmp;
                    flg = false;
                }
            }//for i
            if (flg)
                break;
        }//while
        return res;
    }

hard

最近graphでcycle decompositionとかを勉強してるせいか、

degree sequanceとかを考え始めて抜け出せなくなった。

ただ単にMinCostFlowすればいいだけ。

これは高得点で提出しておきたかった。

  const int dir = 4;
    int[] dx = new int[dir] { 1, 0, -1, 0 };
    int[] dy = new int[dir] { 0, 1, 0, -1 };
    const string direction = "DRUL";
    public int getMinimum(string[] board)
    {
        int row = board.Length;
        int col = board[0].Length;
        int n = row * col;
        int V = 2 * n;
        int start = V++;
        int goal = V++;
        MinCostFlow mcf = new MinCostFlow(V);
        for (int i = 0; i < n; i++)
        {
            mcf.AddEdge(start, i, 1, 0);
            mcf.AddEdge(i + n, goal, 1, 0);
        }//for i
        for (int i = 0; i < n; i++)
        {
            for (int arround = 0; arround < dir; arround++)
            {
                int x = i / col;
                int y = i % col;
                int nx = (x + dx[arround] + row) % row;
                int ny = (y + dy[arround] + col) % col;
                mcf.AddEdge(i, nx * col + ny + n, 1, board[x][y] == direction[arround] ? 0 : 1);
            }//for arround
        }//for i
        return mcf.CalcMinCostFlow(start, goal, n, false);
    }