ABC140 F - Many Slimes用multisetっぽいもの

追記

次の方の実装の方がちゃんとしてて使いやすそう
Submission #7399290 - AtCoder Beginner Contest 140

昨日作った平衡二分探索木っぽいものを改造したらmultisetっぽいものができたっぽい。ABC140のFで確認したっぽい。

追記

これ'T'が複数の情報を持ってるものだったらダメやん･･･ウカツ･･･

解答についてはkmjpさんのブログを参照 kmjp.hatenablog.jp

差分

nodeに要素数countを追加

class node
{
    public int count = 1;
}

挿入時に既存であればcountを+1

void _insert(node z)
{
    //略
    while (x != null)
    {
        y = x;
        if (z.key.CompareTo(x.key) == 0)
        {
            ++x.count;
            change = false;
            return;
        }
        if (z.key.CompareTo(x.key) < 0)
            x = x.left;
        else
            x = x.right;
    }
    //略
}

削除時はcountを-1、0になったら消去

public void delete(T v)
{
    var n = _find(v);
    if (n == null) return;
    --n.count;
    if (n.count <= 0)
    {
        change = true;
        _delete(_find(v));
    }
}

keyを入れ替えているところでcountも入れ替えるのを忘れずに

void _delete(node n)
{
    //略
    if (n == root)
    {
        //略
        else
        {
            var next = n.right;
            while (next.left != null)
                next = next.left;
            n.key = next.key;
            n.count = next.count;
            change = true;
            _delete(next);
        }
        return;
    }
    //略
    else
    {
        var next = n.right;
        while (next.left != null)
            next = next.left;
        n.key = next.key;
        n.count = next.count;
        _delete(next);
    }
    //略
}

背景

艦これイベントE3で浪費される資源。散りゆく頭髪。佐世保への思い(羨ましい･･･)。戦果乏しくトボトボと鎮守府へ戻るクソ提督。疲れからか、不幸にも黒塗りの高級車に追突してしまう･･･。

Eができたし次はFだということで解説記事漁ってたらわかりやすい&multisetを使った解答があったので丁度いいやと。

変な混ぜ方してるので違法建築めいてきた･･･。

おまけ

static void Main(string[] args)
{
    var N = Sarray()[0];
    var S = Slist();
    S.Sort();
    var T = new BinarySearchTree<long>();
    for (var i = 0; i < S.Count - 1; ++i)
        T.insert(S[i]);
    var V = new List<long>();
    V.Add( S.Last());
    for (var i = 0; i < N; ++i)
    {
        var W = new List<long>(V);
        foreach (var v in V)
        {
            long t = v;
            long p = 0;
            if (!T.rower_bound(v, ref t))
                T.max(ref p);
            else if (!T.prev(t, ref p))
            {
                WriteLine("No");
                return;
            }
            W.Add(p);
            T.delete(p);
        }
        W.Sort();
        W.Reverse();
        V = W;
    }
    WriteLine("Yes");
}

BinarySearchTreeにrower_boundとmaxを追加してます。

public bool rower_bound(T v, ref T r)
{
    if (null == root)
        return false;
    var x = root;
    var f = false;
    while (x != null)
    {
        if (x.key.CompareTo(v) == 0)
        {
            r = x.key;
            return true;
        }
        if (x.key.CompareTo(v) < 0)
            x = x.right;
        else
        {
            f = true;
            r = x.key;
            x = x.left;
        }
    }
    return f;
}
public bool max(ref T r)
{
    if (root == null)
        return false;
    var x = root;
    while (x != null)
    {
        r = x.key;
        x = x.right;
    }
    return true;
}