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

 | 

2013-02-08

SRM569

09:21

Medium解けた。


Easy

各ビットでと書いてるので、各ビットで考えてMaxを取る。

Xor,And,Orはどれも可換で、

特にXorが可換だから、(0,0),(0,1),(1,1)の組を考えればよい。

どの演算をしても(0,0)→0なので、これは判別に役立たない。

これ以外の演算で、残り2つを飛ばすと、


(0,1) (1,1)

And 0 1

Or 1 1

Xor 1 0

と、演算結果の組が異なり判別できる。

これから、0が1つ1が2つあればよさげ。

1だけ、0だけ、1一つ0一つでは無理なので、

これは判別可能なもののうち最小でもある。



    public int minimumAdditional(string[] plates)
    {
        int res = 0;
        for (int j = 0; j < plates[0].Length; j++)
        {
            int[] cnt = new int[2];
            for (int i = 0; i < plates.Length; i++)
                cnt[plates[i][j] - '0']++;
            int tmp = Math.Max(0, 1 - cnt[0]) + Math.Max(0, 2 - cnt[1]);
            res = Math.Max(res, tmp);
        }//for j
        return res;
    }

配列用意して、

cnt[plates[i][j] - '0']++;

とやるの賢いと思う。


Medium

2と5が似てるせいで、制約を50と思ってたけど、

よく見ると20か。

というわけで、全探索。


基本的に、%Kの部分だけを考えればよい。

(最初に全部%Kとかすると、危ない)

あまりを丁度Kや0になるように、

他の階から持ってきたり、持っていったりすればいい。

嬉しくないあまりが出てくるときは、なるべくまとめてあげる。


一番下の階から見ていく。

0階では、上に上げる、そのまま、上から下げるの3通り。

1階では、0階からの影響で変化した3通りに対して、

上に上げる、そのまま、上から下げるの3通り。

なのだが、そのままの場合は、上の階に影響を与えないので、

そのままの3通りの中から、それまでで一番答えが少ないやつだけを選べばいい。

ので、状態数が3^nに見えて、3*2^n + 1 とかになる。


あとは、ちゃんと動ける生徒の数とかに注意する。


public int minimumSupervisors(int[] students, int K) 
    { 
        int res = int.MaxValue; 
        List<Pair<int, int>> list = new List<Pair<int, int>>(); 
        list.Add(new Pair<int, int>(students[0], 0)); 
        for (int i = 0; i < students.Length; i++) 
        { 
            List<Pair<int, int>> next = new List<Pair<int, int>>(); 
            foreach (Pair<int, int> current in list) 
            { 
                if (i != students.Length - 1) 
                { 
                    Add(students[i + 1], K, next, current); 
                    Minus(students[i + 1], K, next, current, students[i]); 
                    Same(students[i + 1], K, next, current); 
                } 
                else 
                { 
                    res = Math.Min(res, current.second + (current.first + K - 1) / K); 
                }//else 
            }//foreach current 
            next = Erase(next); 
            list = next; 
        }//for i 
        return res; 
    } 

    private List<Pair<int, int>> Erase(List<Pair<int, int>> next) 
    { 
        List<Pair<int, int>> res = new List<Pair<int, int>>(); 
        next.Sort(); 
        for (int i = 0; i < next.Count; i++) 
        { 
            res.Add(next[i]); 
            while (i + 1 < next.Count && next[i].first == next[i + 1].first) 
                i++; 
        }//for i 
        return res; 
    } 

    private void Same(int student, int K, List<Pair<int, int>> next, Pair<int, int> current) 
    { 
        next.Add(new Pair<int, int>(student, current.second + (current.first + K - 1) / K)); 
    } 

    private void Minus(int student, int K, List<Pair<int, int>> next, Pair<int, int> current, int canMove) 
    { 
        int want = current.first / K * K; 
        int need = current.first - want; 
        int move = Math.Min(canMove, need); 
        int now = current.first - move; 
        next.Add(new Pair<int, int>(student + move, current.second + (now + K - 1) / K)); 
    } 

    private void Add(int student, int K, List<Pair<int, int>> next, Pair<int, int> current) 
    { 
        int want = ((current.first - 1) / K + 1) * K; 
        int need = want - current.first; 
        int move = Math.Min(student, need); 
        int now = current.first + move; 
        next.Add(new Pair<int, int>(student - move, current.second + (now + K - 1) / K)); 
    }



よくよく考えると、なるべく上の階に持ち越す。

上の階に持ち越せないなら、上の階から下ろしてくる、

というgreedyで解ける。

正当性の証明も難しくない。

というか、上の全探索が正しいなら、greedyも正しくなってる。


    public int minimumSupervisors(int[] students, int K)
    {
        int res = 0;
        int move = 0;
        for (int i = 0; i < students.Length; i++)
        {
            int remainder = students[i] + move;
            res += remainder / K;
            remainder %= K;
            if (remainder > 0 && i + 1 < students.Length && remainder > students[i])
            {
                int come = Math.Min(K - remainder, students[i + 1]);
                remainder += come;
                students[i + 1] -= come;
                res++;
                remainder = 0;
            }
            move = remainder;
        }//for i
        if (move > 0)
            res++;
        return res;
    }
 |