本当は難しい貪欲法選択肢を多く残す蟻本読書会

ひとりで勝手にはじめた蟻本読書会猪突猛進！貪欲法区間スケジューリング問題辞書順最小など蟻本読書会の続きです。

貪欲法とは「問題を部分問題に分割して，各部分問題に対する局所最適解を求めることを繰り返すという手法」ですが、適切な方法で部分問題に分割しないと正しい答えを得ることはできません。そのため解法らしきものが思い浮かんだとしても、それが正しいと確信できる程度の証明ができないなら本物とは言えないのかもしれません。実は難しい方法かもしれません。

ただ典型パターンというものは存在するので、それを考えていくことにします。

Contents

1 より近い、または遠いところを選択し続ける
2 あとの選択肢を多く残せるところから選択し続ける
3 優先度付きキューを使った実装

より近い、または遠いところを選択し続ける

選択できるもののなかからより近い、または遠いところをとっていくという考え方でできる問題があります。これも貪欲法のひとつです。

Saruman’s Army (POJ No.3069)

これは直線上に配置された人のうち最小何人選べば、すべての人が選ばれた人の一定距離内におさまるかを求める問題です。一番左にいる人から一定距離以内でもっとも右側にいる人を選び続けるという問題です。

似たような問題

C – Multiple Gift

高橋君は、日頃の感謝を込めて、お母さんに数列をプレゼントすることにしました。お母さんにプレゼントする数列 A は、以下の条件を満たす必要があります。

A は X 以上 Y 以下の整数からなる
A [i+1] は A [i] の倍数であり、かつ A [i+1] ＞ A [i]

高橋君がお母さんにプレゼントできる数列の長さの最大値を求めてください。

入力されるデータ
X Y
1 ≦ X, Y ≦ 10^18

数列をプレゼントされて嬉しい人っているのでしょうか？というツッコミは置くとして、これは「数列の最初の項は X。以降は前項の2倍になるようにする。Y を超えずにこれを何回繰り返すことができるか？」という問題です。

入力例のところに “3 20” であれば数列 3, 6, 18 が条件を満たすので出力は “3” とありますが、3, 6, 「18」は煙幕ですね。貪欲法で考えるなら 3, 6, 12 です。

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

class Program
{
    static void Main()
    {
        long X, Y;
        {
            long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
            X = vs[0];
            Y = vs[1];
        }

        // 実際にループを回さず計算で求めてもよいがここでは愚直にループを回す
        // X が小さく Y が巨大な値のとき制限時間内に終わるか心配になるが問題ない
        // X = 1, Y = 1000000000000000000 であってもループは60回しか回らない
        long cur = X;
        long ans = 1;
        while (true)
        {
            cur *= 2;
            if(cur > Y)
                break;
            ans++;
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

long X, Y;

{

long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

X = vs[0];

Y = vs[1];

}

// 実際にループを回さず計算で求めてもよいがここでは愚直にループを回す

// X が小さく Y が巨大な値のとき制限時間内に終わるか心配になるが問題ない

// X = 1, Y = 1000000000000000000 であってもループは60回しか回らない

long cur = X;

long ans = 1;

while (true)

{

cur *= 2;

if(cur > Y)

break;

ans++;

}

Console.WriteLine(ans);

}

あとの選択肢を多く残せるところから選択し続ける

C – 積み重ね

トラックから引越し先の部屋へと荷物のダンボールを運びたいのですが、部屋の床がダンボールで埋まってしまうと、今日高橋君が寝るための布団がひけません。

そこで、1 箱ずつ広げて置くのではなく、箱を積み重ねた山を作ることにしました。しかし箱には重さが決まっており、下にある箱よりも重い箱を上に積み重ねると下の箱が潰れてしまいます。

トラックから運ぶ順に箱の重さが与えられるので、箱を潰さないような積み重ね方を考えなさい。そして、その積み重ねた山の個数が最小となる場合の山の個数を求めなさい。

入力されるデータ
N
w_1
w_2
…
w_N
（ただし、1 ≦ N ≦50, 1 ≦ w_i ≦ 100,000）

箱がつぶれてしまうのはその上にある箱の重さの総和ではなく、直上のものだけを考えればよいという非日常的な問題です。

新しい箱が運ばれてきたときすでに置かれている箱のどの上にもおけない場合は新しい山をつくるしかありません。すでに置かれている箱の上に置くことができる場合で複数の選択肢がある場合はどうすればよいでしょうか？

方針は「山の一番上にある箱の重さが運ばれてきた箱の重さ以上で一番軽いものを探してそのうえに置く」です。山の数は N を超えることはないので最初に山の数だけ要素をつくっておき、int.MaxValue で初期化しておきます。ここから要素が w 以上で最小のものを探して w で置き換えることを繰り返します。最後に要素の値がint.MaxValueよりも小さいものの数を数えます。これができる山の数です。

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

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        List<int> mins = new List<int>();
        for (int i = 0; i < N; i++)
            mins.Add(int.MaxValue);

        // 山の頂上にある箱の重さが w 以上で一番軽いものを探してそのうえに置く
        for (int i = 0; i < N; i++)
        {
            int w = int.Parse(Console.ReadLine());
            int min = mins.Where(_ => _ >= w).Min();
            int index = mins.IndexOf(min);
            mins[index] = w;
        }
        int ans = mins.Count(_ => _ < int.MaxValue);
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

List<int> mins = new List<int>();

for (int i = 0; i < N; i++)

mins.Add(int.MaxValue);

// 山の頂上にある箱の重さが w 以上で一番軽いものを探してそのうえに置く

for (int i = 0; i < N; i++)

{

int w = int.Parse(Console.ReadLine());

int min = mins.Where(_ => _ >= w).Min();

int index = mins.IndexOf(min);

mins[index] = w;

}

int ans = mins.Count(_ => _ < int.MaxValue);

Console.WriteLine(ans);

}

おいしいたこ焼きの売り方

高橋君は、たこ焼きをどの順番で売るか悩んでいました。作り置きされたたこ焼きは美味しくない、かといってできたてばかり売ってしまうと売れるたこ焼きの数が減ってしまいます。また、お客さんを待たせてばかりだと、次第にお客さんが離れてしまうだろうと高橋君は考えています。

そこで、彼は T 秒以内に作成されたたこ焼きを売り続けることで、お客さんを捌ききれるかどうかを調べることにしました。

たこ焼きは A_1、A_2 … A_N 秒後に焼き上がります。お客さんは B_1、B_2 … B_M 秒後にやってきます。1 人のお客さんに対して、たこ焼きを 1 つ売るとします。すべてのお客さんにたこ焼きを売れるなら yes、売れないなら no を出力して下さい。

入力されるデータ
T
N
A_1 A_2 … A_N
M
B_1 B_2 … B_M
（ただし 1 ≦ T, M ≦ 100
1 ≦ A_1 ≦ A_2 ≦ … ≦ A_N ≦ 100
1 ≦ B_1 ≦ B_2 ≦ … ≦ B_M ≦ 100）

お客さんが来たら売れるたこ焼き（お客さんが来たときと同時またはそれよりも前にできたものでT秒前以内にできたもの）で一番最初につくったものを売ります。そのようなたこ焼きが見つからない場合は処理を終了して no を出力します。B_1 B_2 … B_Mのすべてにおいてこの処理を継続することができた場合は yes を出力します。

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

class Program
{
    static void Main()
    {
        int T = int.Parse(Console.ReadLine());

        // たこ焼き
        int N = int.Parse(Console.ReadLine());
        List<int> takoyakis = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();

        // お客さん
        int M = int.Parse(Console.ReadLine());
        List<int> customers = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();

        foreach(int customer in customers)
        {
            // お客さんが来たときと同時またはそれよりも前にできたものでT秒前以内にできたものを探す
            int first = takoyakis.FirstOrDefault(_ => _ <= customer && _ + T >= customer);

            // そのようなものがない場合は no を出力して終了
            if (first == 0)
            {
                Console.WriteLine("no");
                return;
            }

            // 見つかった場合はそれを売る。売ればなくなるのでリストからは削除
            takoyakis.Remove(first);
        }
        Console.WriteLine("yes");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int T = int.Parse(Console.ReadLine());

// たこ焼き

int N = int.Parse(Console.ReadLine());

List<int> takoyakis = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();

// お客さん

int M = int.Parse(Console.ReadLine());

List<int> customers = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();

foreach(int customer in customers)

{

// お客さんが来たときと同時またはそれよりも前にできたものでT秒前以内にできたものを探す

int first = takoyakis.FirstOrDefault(_ => _ <= customer && _ + T >= customer);

// そのようなものがない場合は no を出力して終了

if (first == 0)

{

Console.WriteLine("no");

return;

}

// 見つかった場合はそれを売る。売ればなくなるのでリストからは削除

takoyakis.Remove(first);

}

Console.WriteLine("yes");

}

C – 2D Plane 2N Points

二次元平面に，赤い点と青い点が N 個ずつあります。i 個目の赤い点の座標は (a_i, b_i) で i 個目の青い点の座標は (c_i, d_i) です。合計 N × 2 個の点はすべて異なる座標にあります。またX座標であったりY座標が同じ点はありません。

赤い点と青い点は、赤い点の x 座標が青い点の x 座標より小さく、赤い点の y 座標も青い点の y 座標より小さいときに仲良しペアになれます。

最大で何個の仲良しペアを作ることができますか？ただし 1 つの点が複数のペアに所属することはできません。

入力されるデータ
N
a_1 b_1
a_2 b_2
…
a_N b_N
c_1 d_1
c_2 d_2
…
c_N d_N

（ただし 1 ≦ N ≦ 100, 0 ≦ a_i, b_i, c_i, d_i ＜ 2N）

同一直線上に並んでいるのであれば「赤い点を座標が大きい順にならべる ⇒ 青い点を座標が大きいものから取っていく」でよいのですが、この場合、座標が X と Y の2つがあります。

優先したい要素がふたつあるからわかりにくいのであるから、まずは「赤い点の側からペアになる点を探す」、「赤い点は X 座標が大きい順に処理する」と決めてしまいましょう。

つぎに問題になるのは、ペアになれそうな青い点が複数みつかったときにどれとペアになるかですが、後々の選択肢を多くするためには「Y 座標が小さい順」です。今度は Y 座標に注目するわけです。

そのため以下のようなコードになります。

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

class Point
{
    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }
    public int X { get; }
    public int Y { get; }
}

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        List<Point> Rs = new List<Point>();
        for (int i = 0; i < N; i++)
        {
            List<int> vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();
            Rs.Add(new Point(vs[0], vs[1]));
        }
        List<Point> Bs = new List<Point>();
        for (int i = 0; i < N; i++)
        {
            List<int> vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();
            Bs.Add(new Point(vs[0], vs[1]));
        }

        // 赤い点は X 座標が大きい順に
        Rs = Rs.OrderByDescending(_ => _.X).ToList();

        int ans = 0;
        foreach (Point r in Rs)
        {
            // ペアの候補がみつかったら Y 座標が小さい順に選ぶ
            List<Point> pts = Bs.Where(_ => r.X < _.X && r.Y < _.Y).OrderBy(_ => _.Y).ToList();
            if (pts.Count > 0)
            {
                Bs.Remove(pts[0]);
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Point

{

public Point(int x, int y)

{

X = x;

Y = y;

}

public int X { get; }

public int Y { get; }

}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

List<Point> Rs = new List<Point>();

for (int i = 0; i < N; i++)

{

List<int> vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();

Rs.Add(new Point(vs[0], vs[1]));

}

List<Point> Bs = new List<Point>();

for (int i = 0; i < N; i++)

{

List<int> vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList();

Bs.Add(new Point(vs[0], vs[1]));

}

// 赤い点は X 座標が大きい順に

Rs = Rs.OrderByDescending(_ => _.X).ToList();

int ans = 0;

foreach (Point r in Rs)

{

// ペアの候補がみつかったら Y 座標が小さい順に選ぶ

List<Point> pts = Bs.Where(_ => r.X < _.X && r.Y < _.Y).OrderBy(_ => _.Y).ToList();

if (pts.Count > 0)

{

Bs.Remove(pts[0]);

ans++;

}

Console.WriteLine(ans);

}

優先度付きキューを使った実装

Fence Repair (POJ No.3253)

農夫ジョンは、フェンスを修理するため、とても長い板から個の板を切り出そうとしています。切り出そうとしている板の長さは L_1, L_2, L_3 … L_N であり、元の板の長さはちょうどこれの合計になっています。板を切断する際には、その板の長さの分だけのコストがかかります。

例えば、長さ 21 の板から 5, 8, 8 の 3 つの板を切り出したいとします。長さ 21 の板を長さ 13 と 8 の板に切断すると、コストが 21 かかります。その 13 の板をさらに 5 と 8 の板に切断すると、コストが 13 かかります。この場合は合計で 34 のコストがかかります。

ではコストを最小にすることができるなら、そのコストはどうなるでしょうか？

ここは単純にこう考えます。

切断された板が先にあり、そのなかから2つ選ぶ。両者を結合させて長くする。そのとき両者の長さの合計がコストとなる。ではコストを最小にするにはどうすればよいか？

切断された板のなかから一番短いものと二番目に短いものを選んで結合させることを繰り返せばよい。

F – Bread

長さ L のパンが 1 つあり、これを N 人の子供たちに切り分けます。 i 番目 (1 ≦ i ≦ N) の子供は長さ A_i のパンを欲しがっています。

そこで、高橋君は長さ A_1, A_2, …, A_N のパンを切り出して配ることにしました。長さ k のパンを 2 つに切り分けるときは 2 つのパンの長さに関係なく k のコストがかかります。

それぞれの子供に配るパンは長さがちょうど A_i のパン 1 つである必要がありますが、誰にも配られずに余るパンがいくつあっても構いません。

このときすべての子供たちにパンを配るために必要な最小のコストを求めてください。

入力されるデータ
N L
A_1 A_2 A_3 … A_N

（ただし 2 ≦ N ≦ 2×10^5, 1 ≦ A_i ≦ 10^9
L ≦ 10^15 かつ A_i の合計を超えない）

小さい方から 2 つ取り出しコストを払って結合させるという処理を要素が2以上であるかぎり繰り返すのですが、値が小さいものをその都度探していては制限時間に間に合いません。そこで優先度付きキューなどを使います。これなら O(NlogN) で解くことができます。

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

class Program
{
    static void Main()
    {
        long N, L;
        {
            long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
            N = vs[0];
            L = vs[1];
        }

        PriorityQueue<long, long> pq = new PriorityQueue<long, long>();
        {
            long[] values = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
            for (int i = 0; i < values.Length; i++)
                pq.Enqueue(values[i], values[i]);

            // 子供に配るパンは長さがちょうどその長さでなければならない
            // L - values.Sum() > 0 の場合はあまりが生じる
            // この部分は N + 1 人目の子供に分配するものとして考える
            if (L - values.Sum() > 0)
                pq.Enqueue(L - values.Sum(), L - values.Sum());
        }

        // 小さい方から 2 つ取り出し コストを払って結合させる
        // 要素が2以上であるかぎりこれを繰り返す
        long ans = 0;
        while (pq.Count > 1)
        {
            long min1 = pq.Dequeue();
            long min2 = pq.Dequeue();
            long cost = min1 + min2;
            pq.Enqueue(cost, cost);
            ans += cost;
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

long N, L;

{

long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

N = vs[0];

L = vs[1];

}

PriorityQueue<long, long> pq = new PriorityQueue<long, long>();

{

long[] values = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

for (int i = 0; i < values.Length; i++)

pq.Enqueue(values[i], values[i]);

// 子供に配るパンは長さがちょうどその長さでなければならない

// L - values.Sum() > 0 の場合はあまりが生じる

// この部分は N + 1 人目の子供に分配するものとして考える

if (L - values.Sum() > 0)

pq.Enqueue(L - values.Sum(), L - values.Sum());

}

// 小さい方から 2 つ取り出しコストを払って結合させる

// 要素が2以上であるかぎりこれを繰り返す

long ans = 0;

while (pq.Count > 1)

{

long min1 = pq.Dequeue();

long min2 = pq.Dequeue();

long cost = min1 + min2;

pq.Enqueue(cost, cost);

ans += cost;

}

Console.WriteLine(ans);

}

本当は難しい貪欲法選択肢を多く残す蟻本読書会

より近い、または遠いところを選択し続ける

あとの選択肢を多く残せるところから選択し続ける

優先度付きキューを使った実装

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ