AtCoder NoviStepsを埋めてみる(2) 貪欲法 2Q問題

AtCoder NoviStepsを埋めてみる(1) 貪欲法 3Q以下の続きです。ちょっと難しめの問題を考えます。

082 – Interval Scheduling Problem

問題の概要は以下のとおりです。

N 本の映画が上映されます。i 番目の映画は時刻 L[i] に始まり R[i] に終わります。
最大いくつの映画を最初から最後まで見ることができるか？

これは区間スケジューリング問題の典型問題です。

どうしても映画の開始時刻に目がいってしまいますが、ここは終了時刻に着目します。現在時刻からみてもっとも早く終わる映画を選択します。映画が終わったらその時刻からあとに始まる映画でもっとも終了時刻が早いものを選択するという処理を繰り返します。

class Program
{
    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

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

        PriorityQueue<(int, int), int> pq = new PriorityQueue<(int, int), int>();
        for (int i = 0; i < N; i++)
        {
            (int l, int r) = ReadInt2();
            pq.Enqueue((l, r), r);
        }

        int ans = 0;

        int cur_time = 0;
        while (pq.Count > 0)
        {
            while(pq.Count > 0)
            {
                if (cur_time > pq.Peek().Item1)
                    pq.Dequeue();
                else
                    break;
            }
            if (pq.Count > 0)
            {
                var lr = pq.Dequeue();
                cur_time = lr.Item2;
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

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

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

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

{

(int l, int r) = ReadInt2();

pq.Enqueue((l, r), r);

}

int ans = 0;

int cur_time = 0;

while (pq.Count > 0)

{

while(pq.Count > 0)

{

if (cur_time > pq.Peek().Item1)

pq.Dequeue();

else

break;

}

if (pq.Count > 0)

{

var lr = pq.Dequeue();

cur_time = lr.Item2;

ans++;

}

Console.WriteLine(ans);

}

079 – Two by Two（★3）

問題の概要は以下のとおりです。

H×W の二次元配列 A が与えられる。
A[x, y], A[x + 1, y], A[x, y + 1], A[x + 1, y + 1]の値を 1 増やすか減らすかの処理を繰り返すことで、A を B に一致させることは可能か？可能ならば最小の操作回数は？

A[0, 0]からみていきA[x, y]とB[x, y]に違いがあれば同じになるようにA[x, y], A[x + 1, y], A[x, y + 1], A[x + 1, y + 1]の値を同時に更新します。この方法で B と一致するならその回数を出力します。この方法で一致させることができないならどうやっても一致させることはできないので”No”を出力します。オーバーフローに注意。

class Program
{
    static void Main()
    {
        string[] vs1 = Console.ReadLine().Split();
        int H = int.Parse(vs1[0]);
        int W = int.Parse(vs1[1]);

        long[,] A = new long[H, W];
        for (int r = 0; r < H; r++)
        {
            int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            for (int c = 0; c < W; c++)
                A[r, c] = vs2[c];
        }

        long[,] B = new long[H, W];
        for (int r = 0; r < H; r++)
        {
            int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            for (int c = 0; c < W; c++)
                B[r, c] = vs2[c];
        }

        long ans = 0;
        for (int r = 0; r < H - 1; r++)
        {
            for (int c = 0; c < W - 1; c++)
            {
                if (A[r, c] != B[r, c])
                {
                    long diff = B[r, c] - A[r, c];
                    A[r, c] += diff;
                    A[r, c + 1] += diff;
                    A[r + 1, c] += diff;
                    A[r + 1, c + 1] += diff;
                    ans += Math.Abs(diff);
                }
            }
        }

        // 処理がすべて終わったら本当に A と B が一致しているかチェックする
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
            {
                if (A[r, c] != B[r, c])
                {
                    Console.WriteLine("No");
                    return;
                }
            }
        }
        Console.WriteLine("Yes");
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

string[] vs1 = Console.ReadLine().Split();

int H = int.Parse(vs1[0]);

int W = int.Parse(vs1[1]);

long[,] A = new long[H, W];

for (int r = 0; r < H; r++)

{

int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

for (int c = 0; c < W; c++)

A[r, c] = vs2[c];

}

long[,] B = new long[H, W];

for (int r = 0; r < H; r++)

{

int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

for (int c = 0; c < W; c++)

B[r, c] = vs2[c];

}

long ans = 0;

for (int r = 0; r < H - 1; r++)

{

for (int c = 0; c < W - 1; c++)

{

if (A[r, c] != B[r, c])

{

long diff = B[r, c] - A[r, c];

A[r, c] += diff;

A[r, c + 1] += diff;

A[r + 1, c] += diff;

A[r + 1, c + 1] += diff;

ans += Math.Abs(diff);

}

// 処理がすべて終わったら本当に A と B が一致しているかチェックする

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

{

if (A[r, c] != B[r, c])

{

Console.WriteLine("No");

return;

}

Console.WriteLine("Yes");

Console.WriteLine(ans);

}

D – Take ABC 2

問題の概要

A, B, C の 3 種類の文字のみからなる文字列 S が与えられる。
S[i] = A, S[j] = B, S[k] = C（ただし i ＜ j ＜ k）を満たす(i, j, k) の組を選び、この文字を取り除く。
残った文字を元の順序を保ったまま左に詰める。
この処理は最大何回繰り返すことができるだろうか？

(i, j, k) の組は大小関係のみを満たしていればよく、連続している必要はありません。なので、最初に見つけた’A’、そのあとにある最初に見つけた’B’、さらにそのあとにある最初に見つけた’C’を削除するという処理を繰り返せばよいです。

問題はどうやってこの処理をおこなうかです。まず文字 ‘A’,’B’,’C’のインデックスをQueueに格納します（qA, qB, qC）。そして’B’のインデックス（idx_b）を取り出します。もしqAに格納されている最小値が idx_b よりも大きければこの idx_b は使いようがありません。なのでこれは捨ててしまって次の idx_b について調べます。

また qC に格納されている idx のなかで idx_b より小さいものも使えません。idx_b はループを繰り返すたびに大きくなっていくので置いておいても使い道はないので qC.Peek() < idx_b である限り qC に格納されている値は捨ててしまいます。

こうして捨てられずに残った qA と qC の先頭の要素と idx_b が S[i] = A, S[j] = B, S[k] = C を満たす(i, j, k) の組です。これを数えればよいです。途中で Queue が空になったら終了です。

class Program
{
    static void Main()
    {
        char[] S = Console.ReadLine().ToArray();

        Queue<int> qA = new Queue<int>();
        Queue<int> qB = new Queue<int>();
        Queue<int> qC = new Queue<int>();

        for (int i = 0; i < S.Length; i++)
        {
            char ch = S[i];
            if (ch == 'A')
                qA.Enqueue(i);
            if (ch == 'B')
                qB.Enqueue(i);
            if (ch == 'C')
                qC.Enqueue(i);
        }

        int ans = 0;
        foreach (var idx_b in qB)
        {
            // 使える idx_a が存在しない。終了
            if (qA.Count == 0)
                break;

            // idx_b より小さい idx_a が存在しない。この B は使えない
            if (qA.Peek() > idx_b)
                continue;

            // idx_b より小さい C は使えない
            while (qC.Count > 0 && qC.Peek() < idx_b)
                qC.Dequeue();

            // 使える C が存在しない。終了
            if (qC.Count == 0)
                break;

            // 使える idx_a, idx_c が見つかった
            int idx_a = qA.Dequeue();
            int idx_c = qC.Dequeue();
            ans++;
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

char[] S = Console.ReadLine().ToArray();

Queue<int> qA = new Queue<int>();

Queue<int> qB = new Queue<int>();

Queue<int> qC = new Queue<int>();

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

{

char ch = S[i];

if (ch == 'A')

qA.Enqueue(i);

if (ch == 'B')

qB.Enqueue(i);

if (ch == 'C')

qC.Enqueue(i);

}

int ans = 0;

foreach (var idx_b in qB)

{

// 使える idx_a が存在しない。終了

if (qA.Count == 0)

break;

// idx_b より小さい idx_a が存在しない。この B は使えない

if (qA.Peek() > idx_b)

continue;

// idx_b より小さい C は使えない

while (qC.Count > 0 && qC.Peek() < idx_b)

qC.Dequeue();

// 使える C が存在しない。終了

if (qC.Count == 0)

break;

// 使える idx_a, idx_c が見つかった

int idx_a = qA.Dequeue();

int idx_c = qC.Dequeue();

ans++;

}

Console.WriteLine(ans);

}

C – AtCoder Riko

問題の概要

長さ L の棒が何本かある。そのうちいくつか（0本や全部の場合もありうる）が２つに折れてしまった。
これによって棒は全部で N 本になり、i 本目の棒の長さは A[i]である。
L としてありうる長さをすべて求めよ（ただし必ず解がひとつ以上存在する入力しか与えられない）。

考えられるパターンとして、(1)棒はすべて折れてしまった。(2)折れずにそのままの棒が存在するのふたつがあります。

すべて折れてしまったのであれば棒の総数は偶数であり、一番長い棒と一番短い棒、二番目に長い棒と二番目に短い棒・・・の長さの合計が同じ値になるはずです。

折れずにそのままの棒が存在するのであれば、その棒はもっとも長い棒です。この棒を取り除いて(1)の場合と同じようなことをすれば長さの合計は一番長い棒の長さに一致するはずです。

(1)と(2)について矛盾しない値が存在するかを調べれば解が得られます。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        Array.Sort(A);

        // 長いものと短いものを組み合わせることで合計が target になるか調べる
        bool Check(int[] arr, int target)
        {
            int len = arr.Length;
            if (len % 2 == 0)
            {
                List<int> vs = new List<int>();
                for (int i = 0; i < len; i++)
                {
                    if (arr[i] + arr[len - 1 - i] != target)
                        return false;
                }
                return true;
            }
            return false;
        }

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

        int ans1 = A[0] + A[N - 1]; // (1)の場合の仮の答え
        if (Check(A, ans1))
            ans.Add(ans1);

        int max = A.Last(); // (2)の場合の仮の答え
        A = A.Where(_ => _ != max).ToArray();
        if (Check(A, max))
            ans.Add(max);

        ans = ans.OrderBy(_ => _).ToList();
        Console.WriteLine(string.Join(" ", ans));
    }
}

class Program

{

static void Main()

{

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

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

Array.Sort(A);

// 長いものと短いものを組み合わせることで合計が target になるか調べる

bool Check(int[] arr, int target)

{

int len = arr.Length;

if (len % 2 == 0)

{

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

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

{

if (arr[i] + arr[len - 1 - i] != target)

return false;

}

return true;

}

return false;

}

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

int ans1 = A[0] + A[N - 1]; // (1)の場合の仮の答え

if (Check(A, ans1))

ans.Add(ans1);

int max = A.Last(); // (2)の場合の仮の答え

A = A.Where(_ => _ != max).ToArray();

if (Check(A, max))

ans.Add(max);

ans = ans.OrderBy(_ => _).ToList();

Console.WriteLine(string.Join(" ", ans));

}

C – Alternated

問題の概要

文字 ‘A’, ‘B’ を N 個ずつ含む長さ 2N の文字列 S が与えられる。
S に対して隣り合う文字を入れ替える操作をおこなって同じ文字が隣り合う箇所がない状態にしたい。
操作回数の最小値を求めよ。

同じ文字が隣り合う箇所がない状態にするには “ABABAB…” とするか “BABABA…” とするしかありません。

‘A’の位置に着目して S のなかにある’A’の位置をリストに格納します。また “ABABAB…” としたときの’A’の位置と “BABABA…” としたときの’A’の位置も取得しておきます。あとは各要素の値の差の絶対値の総和を調べます。これが目標とする文字列に変えるために必要な隣り合う文字を入れ替える回数となります。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        char[] S = Console.ReadLine().ToArray();

        List<int> A = new List<int>();
        List<int> X = new List<int>();
        List<int> Y = new List<int>();
        for (int i = 0; i < N * 2; i++)
        {
            if(S[i] == 'A')
                A.Add(i);

            if(i % 2 == 0)
                X.Add(i);
            else
                Y.Add(i);
        }

        long x_sum = 0;
        long y_sum = 0;
        for (int i = 0; i < N; i++)
        {
            x_sum += Math.Abs(A[i] - X[i]);
            y_sum += Math.Abs(A[i] - Y[i]);
        }
        Console.WriteLine(Math.Min(x_sum, y_sum));
    }
}

class Program

{

static void Main()

{

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

char[] S = Console.ReadLine().ToArray();

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

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

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

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

{

if(S[i] == 'A')

A.Add(i);

if(i % 2 == 0)

X.Add(i);

else

Y.Add(i);

}

long x_sum = 0;

long y_sum = 0;

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

{

x_sum += Math.Abs(A[i] - X[i]);

y_sum += Math.Abs(A[i] - Y[i]);

}

Console.WriteLine(Math.Min(x_sum, y_sum));

}

D – Get Many Stickers

問題の概要は以下のとおり。

最初、中身が入ったコーラが N 本ある。
空き瓶を中身が入ったコーラに交換してくれる店が M 箇所にある。i 番目の店では A[i] 本の空き瓶と引き換えに B[i] 本のコーラと記念のシール 1 枚をもらうことができる。
シールをできるだけたくさん集めたい。最大で何枚集めることができるだろうか？

シールをたくさんもらいたいのであれば空き瓶を交換するときに所持する瓶の総数ができるだけ減らないようにすべきです。そこで交換する店は A[i] – B[i] が小さく、A[i]が現在所持する空き瓶以下のものを選び続けるべきです。

N が大きいので交換するたびに N から A[i] – B[i] を引き続けては実行制限時間以内に処理が終わりません。割り算をしてまとめて処理をしたいのですが、N から A[i] を引いた段階で N が負数にならないような交換方法を採用する必要があります。

そのために N から A[i]だけ引いたものを割り算してまとめて交換処理をしています。ただこの方法だと1本も交換できない場合があるのでその場合は普通に1回分ずつ交換の処理をしています。

class Program
{
    static void Main()
    {
        (long, long) ReadLong2()
        {
            string[] vs = Console.ReadLine().Split();
            long a = long.Parse(vs[0]);
            long b = long.Parse(vs[1]);
            return (a, b);
        }

        (long N, long M) = ReadLong2();

        PriorityQueue<(long, long), long> pq = new PriorityQueue<(long, long), long>();
        for (int i = 0; i < M; i++)
        {
            (long a, long b) = ReadLong2();
            pq.Enqueue((a, b), a - b);
        }

        long ans = 0;
        while (pq.Count > 0)
        {
            while (pq.Count > 0 && pq.Peek().Item1 > N)
                pq.Dequeue();

            if (pq.Count > 0)
            {
                var tp = pq.Peek();
                long diff = tp.Item1 - tp.Item2;

                // まとめて複数回分の交換ができるかもしれない
                // 割り算するまえに店にわたす瓶の数を引いて、交換途中でNが負数になるのを防ぐ
                long n = N - tp.Item1;
                long cnt = n / diff;
                ans += cnt;
                N -= tp.Item1 * cnt;
                N += tp.Item2 * cnt;

                // 普通に1回分の交換処理をする
                if (cnt == 0)
                {
                    N -= diff;
                    ans++;
                }
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

(long, long) ReadLong2()

{

string[] vs = Console.ReadLine().Split();

long a = long.Parse(vs[0]);

long b = long.Parse(vs[1]);

return (a, b);

}

(long N, long M) = ReadLong2();

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

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

{

(long a, long b) = ReadLong2();

pq.Enqueue((a, b), a - b);

}

long ans = 0;

while (pq.Count > 0)

{

while (pq.Count > 0 && pq.Peek().Item1 > N)

pq.Dequeue();

if (pq.Count > 0)

{

var tp = pq.Peek();

long diff = tp.Item1 - tp.Item2;

// まとめて複数回分の交換ができるかもしれない

// 割り算するまえに店にわたす瓶の数を引いて、交換途中でNが負数になるのを防ぐ

long n = N - tp.Item1;

long cnt = n / diff;

ans += cnt;

N -= tp.Item1 * cnt;

N += tp.Item2 * cnt;

// 普通に1回分の交換処理をする

if (cnt == 0)

{

N -= diff;

ans++;

}

Console.WriteLine(ans);

}

C – Giant Domino

問題の概要

1 から N までの番号がついた N 個のドミノがある。ドミノ i の大きさは S[i] である。
ドミノが右に向けて倒れる時、そのすぐ右に置かれているドミノの大きさがその 2倍以下であればそれも右に倒れる。
一番左に 1 番目のドミノ、一番右に N 番目のドミノを配置してすべてのドミノが倒れるようにしたい。
そのために必要なドミノの最小個数は何個だろうか？

左側においたドミノの2倍以下のもので、最大または N 番目のドミノを右に配置していけばよいです。

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

        for (int i = 0; i < T; i++)
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int ans = Solve(N, A);
            Console.WriteLine(ans);
        }

        int Solve(int N, int[] A)
        {
            // 中間のドミノをリストに格納してソートする
            // ただし A[0]以下のもの、A.Last 以上のもの、値が重複しているものは不要
            List<int> vs = new List<int>();
            for (int i = 1; i < N - 1; i++)
            {
                if(A[N - 1] > A[i] && A[0] < A[i])
                    vs.Add(A[i]);
            }

            vs = vs.Distinct().OrderBy(_ => _).ToList();

            // 二分探索法で vs のなかから target 以下の最大の数を探す
            int Search(int target)
            {
                int ok = -1;
                int ng = vs.Count;

                while (Math.Abs(ok - ng) > 1)
                {
                    var mid = (ok + ng) >> 1;
                    if (vs[mid] <= target)
                        ok = mid;
                    else
                        ng = mid;
                }
                if (ok >= 0)
                    return vs[ok];
                else
                    return -1;
            }

            int cur = A[0];
            int last = A[N - 1];

            int ans = 1;

            // 現在のドミノの2倍以下の大きさのドミノで最大のものを取得し、これでcurを更新していく。
            while (true)
            {
                // N 番ドミノをおくことができるなら置いて終了
                if (cur * 2 >= last)
                {
                    ans++;
                    break;
                }
                int target = cur * 2;
                int res = Search(target);

                // cur の値を大きな値で更新できないということは
                // これより大きなドミノで置くことができるものは存在しないことを意味する
                //（つまり不可能）
                if (cur == res)
                {
                    ans = -1;
                    break;
                }
                cur = res;
                ans++;
            }
            return ans;
        }
    }
}

class Program

{

static void Main()

{

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

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

{

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

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int ans = Solve(N, A);

Console.WriteLine(ans);

}

int Solve(int N, int[] A)

{

// 中間のドミノをリストに格納してソートする

// ただし A[0]以下のもの、A.Last 以上のもの、値が重複しているものは不要

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

for (int i = 1; i < N - 1; i++)

{

if(A[N - 1] > A[i] && A[0] < A[i])

vs.Add(A[i]);

}

vs = vs.Distinct().OrderBy(_ => _).ToList();

// 二分探索法で vs のなかから target 以下の最大の数を探す

int Search(int target)

{

int ok = -1;

int ng = vs.Count;

while (Math.Abs(ok - ng) > 1)

{

var mid = (ok + ng) >> 1;

if (vs[mid] <= target)

ok = mid;

else

ng = mid;

}

if (ok >= 0)

return vs[ok];

else

return -1;

}

int cur = A[0];

int last = A[N - 1];

int ans = 1;

// 現在のドミノの2倍以下の大きさのドミノで最大のものを取得し、これでcurを更新していく。

while (true)

{

// N 番ドミノをおくことができるなら置いて終了

if (cur * 2 >= last)

{

ans++;

break;

}

int target = cur * 2;

int res = Search(target);

// cur の値を大きな値で更新できないということは

// これより大きなドミノで置くことができるものは存在しないことを意味する

//（つまり不可能）

if (cur == res)

{

ans = -1;

break;

}

cur = res;

ans++;

}

return ans;

}

D – String Rotation

問題の概要

長さ N の英小文字からなる文字列 S が与えられる。
長さ 1 以上の連続部分文字列を選んで、左に 1 だけ巡回シフトする。
操作後の S としてありえる文字列のうち、辞書順最小のものを求めよ。

長さ 1 以上の連続部分文字列を選んで、左に 1 だけ巡回シフトする操作は、どこかから 1 文字抜き取ってそれをその位置より後ろのどこかに挿入するのと同じ操作です。

ではどの文字を抜き取ればよいでしょうか？先頭から順番にみていって i 番目よりも i + 1 番目の文字のほうが辞書順で小さいなら、その文字を選択すべきです。そのような文字が存在しない場合はなにもする必要はありません（長さ 1 の連続文字列を巡回シフトすると S は変化しないので題意は満たしている）。

挿入する位置ですが、その文字よりも後ろにあってもっとも先頭に近い位置にある辞書順が大きい文字の直前にするのが最適となります（そのような場所が見つからない場合は最後尾に追加する）。

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

        for (int i = 0; i < T; i++)
        {
            int N = int.Parse(Console.ReadLine());
            string S = ReadLine();
            string ans = Solve(N, S);
            Console.WriteLine(ans);
        }

        string Solve(int N, string S)
        {
            int left = -1;
            for (int i = 0; i < N - 1; i++)
            {
                if (S[i] > S[i + 1])
                {
                    left = i;
                    break;
                }
            }

            if (left == -1)
                return S;

            int right = -1;
            for (int i = left + 1; i < N; i++)
            {
                if (S[i] > S[left])
                {
                    right = i;
                    break;
                }
            }
            if (right == -1)
            {
                List<char> vs = S.ToList();
                vs.Add(S[left]);
                vs.RemoveAt(left);
                return new string(vs.ToArray());
            }
            else
            {
                List<char> vs = S.ToList();
                vs.Insert(right, S[left]);
                vs.RemoveAt(left);
                return new string(vs.ToArray());
            }
        }
    }
}

class Program

{

static void Main()

{

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

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

{

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

string S = ReadLine();

string ans = Solve(N, S);

Console.WriteLine(ans);

}

string Solve(int N, string S)

{

int left = -1;

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

{

if (S[i] > S[i + 1])

{

left = i;

break;

}

if (left == -1)

return S;

int right = -1;

for (int i = left + 1; i < N; i++)

{

if (S[i] > S[left])

{

right = i;

break;

}

if (right == -1)

{

List<char> vs = S.ToList();

vs.Add(S[left]);

vs.RemoveAt(left);

return new string(vs.ToArray());

}

else

{

List<char> vs = S.ToList();

vs.Insert(right, S[left]);

vs.RemoveAt(left);

return new string(vs.ToArray());

}

D – Merge Slimes

問題の概要

N 種類のサイズのスライム（サイズ S[i] のスライムが C[i] 匹）がいる。
同じサイズのスライムが2匹いる場合、合成できる。合成するとサイズが2倍のスライムが1匹出現し、もとの2匹のスライムは消滅する
合成を繰り返してスライムの引数を最小にしたい。何匹にすることができるか？

小さいものから合成していけばよい。同じサイズのものが1匹しかいない場合、それはこれ以上合成できないのでそれらを数え合わせればよいです。サイズが2倍2倍と大きくなり続けて long 型でも扱えない大きな数になってしまわないか気になりますが、S[i], C[i] の最大値である 10^9 だったとしてもオーバーフローはしません。

class Program
{
    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

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

        PriorityQueue<(long, long), long> pq = new PriorityQueue<(long, long), long>();
        for (int i = 0; i < N; i++)
        {
            (int s, int c) = ReadInt2();
            pq.Enqueue((s, c), s);
        }

        long ans = 0;

        // 小さいものから合成していくが、
        while (pq.Count > 0)
        {
            var pair = pq.Dequeue();
            long size = pair.Item1;
            long cnt = pair.Item2;

            // PriorityQueueのなかに同じサイズのものが複数あるかもしれないのでまとめる
            while (pq.Count > 0 && pq.Peek().Item1 == pair.Item1)
                cnt += pq.Dequeue().Item2;

            ans += cnt % 2; // 匹数が奇数なら合成できないものが 1匹 できるので数えあげる

            if(cnt / 2 > 0)
                pq.Enqueue((size * 2, cnt / 2), size * 2);
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

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

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

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

{

(int s, int c) = ReadInt2();

pq.Enqueue((s, c), s);

}

long ans = 0;

// 小さいものから合成していくが、

while (pq.Count > 0)

{

var pair = pq.Dequeue();

long size = pair.Item1;

long cnt = pair.Item2;

// PriorityQueueのなかに同じサイズのものが複数あるかもしれないのでまとめる

while (pq.Count > 0 && pq.Peek().Item1 == pair.Item1)

cnt += pq.Dequeue().Item2;

ans += cnt % 2; // 匹数が奇数なら合成できないものが 1匹できるので数えあげる

if(cnt / 2 > 0)

pq.Enqueue((size * 2, cnt / 2), size * 2);

}

Console.WriteLine(ans);

}

C – Approximate Equalization 2

問題の概要

整数列 A が与えられる。
「A[i] を 1 減らし、A[j] を 1 増やす」という操作を繰り返して A の最小値と最大値の差を 1 以下にしたい。
必要な最小の操作回数は？

A = {4, 7, 3, 7} の場合、どうなるかを考えてみます。

まずソートします。すると A = {3, 4, 7, 7} となります。また A[i] を 1 減らし、A[j] を 1 増やすのであれば総和はかわりません。

そこで A の最小値と最大値の差を 1 以下になったとき、どのような状態になっているかを考えます。総和は 21 であり、平均は 5 と 6 の間です。A のなかには 5 と 6 が混在することになります。

では、5 と 6 のみで作られた総和が 21 になるソートされた整数列は何でしょうか？ {5, 5, 5, 6} です。

{3, 4, 7, 7} を {5, 5, 5, 6} にするのであれば各要素の差の絶対値の総和を半分にすればよいです。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

        Array.Sort(A);

        // A から変形可能な最小値と最大値の差が 1 以下である配列 B を生成する
        long sum = A.Sum();
        long avr = sum / N;
        int m = (int)(sum % N);

        long[] B = new long[N];
        for (int i = 0; i < N - m; i++)
            B[i] = avr;
        for (int i = N - m; i < N; i++)
            B[i] = avr + 1;

        long ans = 0;
        for (int i = 0; i < N; i++)
            ans += Math.Abs(A[i] - B[i]);

        Console.WriteLine(ans / 2);
    }
}

class Program

{

static void Main()

{

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

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

Array.Sort(A);

// A から変形可能な最小値と最大値の差が 1 以下である配列 B を生成する

long sum = A.Sum();

long avr = sum / N;

int m = (int)(sum % N);

long[] B = new long[N];

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

B[i] = avr;

for (int i = N - m; i < N; i++)

B[i] = avr + 1;

long ans = 0;

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

ans += Math.Abs(A[i] - B[i]);

Console.WriteLine(ans / 2);

}

D – Destroyer Takahashi

問題の概要

N 枚の壁があり、i 番目の壁はL[i] 列目から R[i] 列目の範囲にある。
1 回のパンチで連続する D 列にまとめてダメージを与えることができ、一部でもダメージをうけた壁は全体が破壊される。
すべての壁を破壊するには、少なくとも何回のパンチが必要だろうか？

このような区間に関する問題は区間の開始点ではなく終了点に着目するとよいです。

まず残っている壁のなかから R が最小のもの (1) を探します。パンチはそこから幅 D の範囲に作用するので L が R + D – 1 以下の壁 (2) はすべて破壊することができます。

(1) と (2) は PriorityQueue を使えば高速で見つけることができます。

class Program
{
    class Wall
    {
        public Wall(int l, int r)
        {
            L = l;
            R = r;
        }
        public int L = 0;
        public int R = 0;
        public bool IsDestroyed = false;
    }

    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

        (int N, int D) = ReadInt2();

        PriorityQueue<Wall, int> pqL = new PriorityQueue<Wall, int>();
        PriorityQueue<Wall, int> pqR = new PriorityQueue<Wall, int>();
        for (int i = 0; i < N; i++)
        {
            (int l, int r) = ReadInt2();
            Wall wall = new Wall(l, r);
            pqL.Enqueue(wall, l);
            pqR.Enqueue(wall, r);
        }

        int ans = 0;
        while (pqR.Count > 0)
        {
            // R が最小のものを探すがすでに破壊された壁であれば無視
            while (pqR.Count > 0 && pqR.Peek().IsDestroyed)
                pqR.Dequeue();

            if (pqR.Count > 0)
            {
                // パンチが作用する壁を破壊する
                int left = pqR.Dequeue().R + D - 1;
                while (pqL.Count > 0 && pqL.Peek().L <= left)
                    pqL.Dequeue().IsDestroyed = true;

                ans++;

                if (pqL.Count == 0) // すべて破壊されたので終了
                    break;
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

class Wall

{

public Wall(int l, int r)

{

L = l;

R = r;

}

public int L = 0;

public int R = 0;

public bool IsDestroyed = false;

}

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

(int N, int D) = ReadInt2();

PriorityQueue<Wall, int> pqL = new PriorityQueue<Wall, int>();

PriorityQueue<Wall, int> pqR = new PriorityQueue<Wall, int>();

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

{

(int l, int r) = ReadInt2();

Wall wall = new Wall(l, r);

pqL.Enqueue(wall, l);

pqR.Enqueue(wall, r);

}

int ans = 0;

while (pqR.Count > 0)

{

// R が最小のものを探すがすでに破壊された壁であれば無視

while (pqR.Count > 0 && pqR.Peek().IsDestroyed)

pqR.Dequeue();

if (pqR.Count > 0)

{

// パンチが作用する壁を破壊する

int left = pqR.Dequeue().R + D - 1;

while (pqL.Count > 0 && pqL.Peek().L <= left)

pqL.Dequeue().IsDestroyed = true;

ans++;

if (pqL.Count == 0) // すべて破壊されたので終了

break;

}

Console.WriteLine(ans);

}

D – Shipping Center

問題の概要

N 個の荷物と M 個の箱がある。荷物 i の大きさは W[i] で価値は V[i]。
箱 i には大きさが X[i] 以下の荷物を入れることができるが、ひとつの箱に入れられる荷物はひとつだけ。
Q 個のクエリに答えよ。L[i] 番目から R[i] 番目の箱が使えなくなった。残りの箱の中に同時に入れることができる荷物の価値の合計の最大値は？

クエリは最大50個だが、それぞれにおいてL[i] 番目から R[i] 番目の箱を取り除いて処理を繰り返せばTLEすることなくACできます。

存在する箱のなかに入れることができる荷物の価値の総和の最大値を得る方法ですが、両者のサイズを小さい順にソートして同じリストのなかにいれます。サイズが同じ場合は荷物が前になるようにします。

リストから順番にとりだし荷物であれば集合 S のなかにいれます。リストから取り出されたものが存在する箱であれば集合 S に格納されている価値が最大のものを箱にいれます。この処理は PriorityQueue を使えば可能です。

class Program
{
    class ItemBox
    {
        public ItemBox(int idx, int w, int v)
        {
            Index = idx;
            W = w;
            V = v;
        }
        public int Index = 0;
        public int W = 0;
        public int V = 0;
    }

    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

        (int, int, int) ReadInt3()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2]));
        }

        (int N, int M, int Q) = ReadInt3();

        List<ItemBox> I = new List<ItemBox>();
        for (int i = 0; i < N; i++)
        {
            (int w, int v) = ReadInt2();
            I.Add(new ItemBox(-1, w, v));
        }

        int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        for (int i = 0; i < M; i++)
            I.Add(new ItemBox(i, X[i], -1));

        I = I.OrderBy(_ => _.W).ToList();

        for (int i = 0; i < Q; i++)
        {
            (int left, int right) = ReadInt2();
            left--;
            right--;
            long ans = Solve(left, right);
            Console.WriteLine(ans);
        }

        long Solve(int left, int right)
        {
            long ans = 0;

            PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
            foreach (var item in I)
            {
                if (item.V > 0) // 荷物
                    pq.Enqueue(item.V, -item.V);
                else if(pq.Count > 0 && (item.Index < left || right < item.Index)) // 存在する箱
                    ans += pq.Dequeue();
            }
            return ans;
        }
    }
}

class Program

{

class ItemBox

{

public ItemBox(int idx, int w, int v)

{

Index = idx;

W = w;

V = v;

}

public int Index = 0;

public int W = 0;

public int V = 0;

}

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

(int, int, int) ReadInt3()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2]));

}

(int N, int M, int Q) = ReadInt3();

List<ItemBox> I = new List<ItemBox>();

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

{

(int w, int v) = ReadInt2();

I.Add(new ItemBox(-1, w, v));

}

int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

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

I.Add(new ItemBox(i, X[i], -1));

I = I.OrderBy(_ => _.W).ToList();

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

{

(int left, int right) = ReadInt2();

left--;

right--;

long ans = Solve(left, right);

Console.WriteLine(ans);

}

long Solve(int left, int right)

{

long ans = 0;

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

foreach (var item in I)

{

if (item.V > 0) // 荷物

pq.Enqueue(item.V, -item.V);

else if(pq.Count > 0 && (item.Index < left || right < item.Index)) // 存在する箱

ans += pq.Dequeue();

}

return ans;

}

D – Choose Me

問題の概要

N 個の町があり、i 番目の町には青木派の有権者が A[i] 人、高橋派の有権者が B[i] 人いる。
高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票する。
高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行かない。
高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるだろうか？

最初に高橋氏がまったく演説をおこなわない場合を考えます。
高橋氏が演説をすることで (1) 高橋派が投票するので高橋氏の得票が増える、(2) 青木派が寝返るので (2a)青木氏の得票が減る、(2b) 高橋氏の得票が増えるという現象がおきます。

演説による効果は A[i] × 2 + B[i] なのでこの値が大きい順にソートしてシミュレーションしていけばよいです。

class Program
{
    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

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

        List<(long, long)> vs = new List<(long, long)> (); // int 型だと ※ でオーバーフローする
        long A = 0;
        long B = 0;
        for (int i = 0; i < N; i++)
        {
            (int a, int b) = ReadInt2();
            vs.Add((a, b));
            A += a;
        }

        vs = vs.OrderByDescending(_ => _.Item1 * 2 + _.Item2).ToList(); // ※

        for (int i = 0; i < N; i++)
        {
            A -= vs[i].Item1;
            B += vs[i].Item2 + vs[i].Item1;
            if (A < B)
            {
                Console.WriteLine(i + 1);
                return;
            }
        }
    }
}

class Program

{

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

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

List<(long, long)> vs = new List<(long, long)> (); // int 型だと ※ でオーバーフローする

long A = 0;

long B = 0;

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

{

(int a, int b) = ReadInt2();

vs.Add((a, b));

A += a;

}

vs = vs.OrderByDescending(_ => _.Item1 * 2 + _.Item2).ToList(); // ※

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

{

A -= vs[i].Item1;

B += vs[i].Item2 + vs[i].Item1;

if (A < B)

{

Console.WriteLine(i + 1);

return;

}

D – Takahashi Unevolved

問題の概要

自然数 X, Y, A, B が与えられる。
X を A 倍するか B を足すかの処理を Y 以上にならないように繰り返したい。
最大で何回繰り返すことができるだろうか？

実際に X を A 倍するか B を足すかの処理を繰り返すシミュレーションを繰り返す方法では操作の回数が多くなり TLE してしまいます。

X が小さいと B を足すのではなく A 倍したほうが小さいなる場合があるので、A 倍する操作を何回繰り返す必要があるかを考えます。それ以降は B を足す操作のみ繰り返すことになりますが、その回数は実際にシミュレーションしなくても割り算をすれば算出することができます。

掛け算をするときにlong型でもオーバーフローする可能性があります。double型にキャストして掛け算して Y よりも充分に大きな数（10^18 の 2倍とか long.MaxValue / 2 など）と比較して大きすぎる場合は巨大な数を返し、そうでない場合は通常の掛け算をしています。

class Program
{
    static void Main()
    {
        string[] vs = Console.ReadLine().Split();
        long X = long.Parse(vs[0]);
        long Y = long.Parse(vs[1]);
        long A = long.Parse(vs[2]);
        long B = long.Parse(vs[3]);

        long Kakezan(long x)
        {
            double d = (double)x * A;
            if (d > long.MaxValue / 2)
                return long.MaxValue / 2;
            return x * A;
        }

        long ans = 0;

        // X が小さいと A 倍したほうが小さいかもしれない
        for (int i = 0; i <= 60; i++)
        {
            if (Kakezan(X) < X + B)
            {
                X = Kakezan(X);
                if (X < Y)
                    ans++;
                else
                    break;
            }
            else
            {
                X = X + B;
                if (X < Y)
                    ans++;
                break; // これ以降は A 倍するより B を足し続けたほうがよい
            }
        }
        if (X < Y) // まだ B を足し続ける操作が可能。何回できるか計算で求める
        {
            ans += (Y - X) / B;
            if ((Y - X) % B == 0)
                ans--;
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

string[] vs = Console.ReadLine().Split();

long X = long.Parse(vs[0]);

long Y = long.Parse(vs[1]);

long A = long.Parse(vs[2]);

long B = long.Parse(vs[3]);

long Kakezan(long x)

{

double d = (double)x * A;

if (d > long.MaxValue / 2)

return long.MaxValue / 2;

return x * A;

}

long ans = 0;

// X が小さいと A 倍したほうが小さいかもしれない

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

{

if (Kakezan(X) < X + B)

{

X = Kakezan(X);

if (X < Y)

ans++;

else

break;

}

else

{

X = X + B;

if (X < Y)

ans++;

break; // これ以降は A 倍するより B を足し続けたほうがよい

}

if (X < Y) // まだ B を足し続ける操作が可能。何回できるか計算で求める

{

ans += (Y - X) / B;

if ((Y - X) % B == 0)

ans--;

}

Console.WriteLine(ans);

}

D – Powerful Discount Tickets

N 個の品物があり、i 番目の品物の値段は A[i] 円である。
M 枚の割引券があり、1枚使うたびにその品物の値段が半額になる。
すべての品物を買うために必要な金額の最小値は？

高い金額のものから割引券を使っていけばよいです。

class Program
{
    static void Main()
    {
        string[] vs = Console.ReadLine().Split();
        int N = int.Parse(vs[0]);
        int M = int.Parse(vs[1]);
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        for (int i = 0; i < N; i++)
            pq.Enqueue(A[i], - A[i]);

        for (int i = 0; i < M; i++)
        {
            // 「一番高いものを半額にする」を M 回繰り返す
            int v = pq.Dequeue();
            v /= 2;
            pq.Enqueue(v, -v);
        }

        long ans = 0;
        for (int i = 0; i < N; i++)
            ans += pq.Dequeue();

        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

string[] vs = Console.ReadLine().Split();

int N = int.Parse(vs[0]);

int M = int.Parse(vs[1]);

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

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

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

pq.Enqueue(A[i], - A[i]);

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

{

// 「一番高いものを半額にする」を M 回繰り返す

int v = pq.Dequeue();

v /= 2;

pq.Enqueue(v, -v);

}

long ans = 0;

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

ans += pq.Dequeue();

Console.WriteLine(ans);

}

D – Integer Cards

N 枚のカードがあり、i 番目のカードには整数 A[i] が書かれています。
「カードを B[j] 枚まで選んで C[j] に書き換える」という操作を M 回繰り返す。
操作後のカードに書かれた整数の合計の最大値は？

カードに書かれた整数のうち小さいものからB[j] 枚まで（ただしC[j]より小さい場合のみ）選んで C[j] に書き換えるという処理を M 回繰り返そうとすると時間がかかって TLE することになります。

10枚のカードを 10 に書き換える
3 枚のカードを 20 に書き換える

これは以下の処理と同じです。

7 枚のカードを 10 に書き換える
3 枚のカードを 20 に書き換える

つまりカードの書き換え回数を最大でもカードの枚数と同数に減らすことができるのです。

書き換えを圧縮することができたらどう書き換えるかですが、カードを書かれている数は小さい順に、書き換える値は大きい順にソートして組み合わせ、カードに書かれている数のほうが小さい場合は書き換えます（これがカードに書かれている数の総和を大きく増加させることができる）。

最後に実際に総和を計算します。

class Program
{
    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

        (int N, int M) = ReadInt2();
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        List<(int, int)> vs = new List<(int, int)>();
        for (int i = 0; i < M; i++)
        {
            (int b, int c) = ReadInt2();
            vs.Add((b, c));
        }

        // 書き換え後の値でソートして 長さ N の書き換え後の値のリストをつくる
        vs = vs.OrderByDescending(_ => _.Item2).ToList();

        List<int> newValues = new List<int>();
        foreach (var pair in vs)
        {
            for (int i = 0; i < pair.Item1; i++)
            {
                newValues.Add(pair.Item2);
                if (newValues.Count == N)
                    break;
            }
            if (newValues.Count == N)
                break;
        }

        // 長さが N に満たないときは後ろに 0 を追加して長さを N に調整する
        if (newValues.Count < N)
        {
            int cnt = N - newValues.Count;
            for (int i = 0; i < cnt; i++)
                newValues.Add(0);
        }

        Array.Sort(A);

        for (int i = 0; i < N; i++)
        {
            if (A[i] < newValues[i])
                A[i] = newValues[i];
        }

        long ans = 0;
        for (int i = 0; i < N; i++)
            ans += A[i];

        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

(int N, int M) = ReadInt2();

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

List<(int, int)> vs = new List<(int, int)>();

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

{

(int b, int c) = ReadInt2();

vs.Add((b, c));

}

// 書き換え後の値でソートして長さ N の書き換え後の値のリストをつくる

vs = vs.OrderByDescending(_ => _.Item2).ToList();

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

foreach (var pair in vs)

{

for (int i = 0; i < pair.Item1; i++)

{

newValues.Add(pair.Item2);

if (newValues.Count == N)

break;

}

if (newValues.Count == N)

break;

}

// 長さが N に満たないときは後ろに 0 を追加して長さを N に調整する

if (newValues.Count < N)

{

int cnt = N - newValues.Count;

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

newValues.Add(0);

}

Array.Sort(A);

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

{

if (A[i] < newValues[i])

A[i] = newValues[i];

}

long ans = 0;

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

ans += A[i];

Console.WriteLine(ans);

}

B – Increasing Triples

問題の概要

長さ N の整数列 A, B, C が与えられる。
これらを並べ替えて A[i] < B[i] < C[i] を満たす i の個数を最大化したい。
i の個数は最大でいくつになるだろうか？

A, B, C をすべてまとめてソートする。ただし同じ値のときは C の要素が一番前で A の要素が一番うしろになるようにします。

前から順番に見ていって、C を要素があれば、それより前にある A と B の要素を探して三つ組を作ります。PriorityQueue を使ってこれまでに見てきた A の最小値とその最小値よりも大きな　B の最小値を得ることができます。

class Program
{
    static void Main()
    {
        int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int N = int.Parse(Console.ReadLine());
        int[] A = ReadIntArray();
        int[] B = ReadIntArray();
        int[] C = ReadIntArray();

        List<(int, char)> vs = new List<(int, char)> ();
        foreach (int v in A)
            vs.Add((v, 'A'));
        foreach (int v in B)
            vs.Add((v, 'B'));
        foreach (int v in C)
            vs.Add((v, 'C'));

        vs = vs.OrderBy(_ => _.Item1).ThenByDescending(_ => _.Item2).ToList();

        PriorityQueue<int, int> pqA = new PriorityQueue<int, int>();
        PriorityQueue<int, int> pqB = new PriorityQueue<int, int>();

        int ans = 0;
        foreach (var pair in vs)
        {
            int v = pair.Item1;
            if (pair.Item2 == 'A')
                pqA.Enqueue(v, v);
            if (pair.Item2 == 'B')
                pqB.Enqueue(v, v);
            if (pair.Item2 == 'C' && pqA.Count > 0 && pqB.Count > 0)
            {
                int minA = pqA.Peek();

                // minA より大きい B を探す（pqB.Peek() <= minA ならいらないので捨てる）
                while (pqB.Count > 0 && pqB.Peek() <= minA)
                    pqB.Dequeue();

                if(pqB.Count > 0)
                {
                    pqA.Dequeue();
                    pqB.Dequeue();
                    ans++;
                }
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

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

int[] A = ReadIntArray();

int[] B = ReadIntArray();

int[] C = ReadIntArray();

List<(int, char)> vs = new List<(int, char)> ();

foreach (int v in A)

vs.Add((v, 'A'));

foreach (int v in B)

vs.Add((v, 'B'));

foreach (int v in C)

vs.Add((v, 'C'));

vs = vs.OrderBy(_ => _.Item1).ThenByDescending(_ => _.Item2).ToList();

PriorityQueue<int, int> pqA = new PriorityQueue<int, int>();

PriorityQueue<int, int> pqB = new PriorityQueue<int, int>();

int ans = 0;

foreach (var pair in vs)

{

int v = pair.Item1;

if (pair.Item2 == 'A')

pqA.Enqueue(v, v);

if (pair.Item2 == 'B')

pqB.Enqueue(v, v);

if (pair.Item2 == 'C' && pqA.Count > 0 && pqB.Count > 0)

{

int minA = pqA.Peek();

// minA より大きい B を探す（pqB.Peek() <= minA ならいらないので捨てる）

while (pqB.Count > 0 && pqB.Peek() <= minA)

pqB.Dequeue();

if(pqB.Count > 0)

{

pqA.Dequeue();

pqB.Dequeue();

ans++;

}

Console.WriteLine(ans);

}

C – Sequence

問題の概要

長さ N の数列 A がある。
1 回の操作でひとつの要素の値を 1 増やすか減らすことができる。

すべての i において i 番目までの和が 0 であってはならない。
i 番目までの和と i + 1 番目までの和の符号が異なる。

このような条件をみたすようにするために必要な最小の操作回数は？

和の符号が +, -, +, – となる場合と -, +, -, + となる場合の2パターンについて考えて操作回数が少なくなるほうが解です。符号があっていない場合、絶対値が 1 になるようにし、符号があっている場合はなにもしなくてよいです（値を変更することでもっと良い解が得られることは絶対にない）。

A[i] の値を変更することで i 番目以降の和がすべて増減します。なので差分を記録して処理を高速化しています。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        long[] B = new long[N + 1];

        for (int i = 0; i < N; i++)
            B[i + 1] = B[i] + A[i];

        B = B.Skip(1).ToArray();

        Console.WriteLine(Math.Min(Solve(true), Solve(false)));

        long Solve(bool is_first_plus)
        {
            long ans = 0;
            long diff_sum = 0;
            for (int i = 0; i < N; i++)
            {
                long b = B[i] + diff_sum;
                if (i % 2 == (is_first_plus ? 0 : 1))
                {
                    if (b <= 0)
                    {
                        long diff = Math.Abs(b) + 1;
                        diff_sum += diff;
                        ans += diff;
                    }
                }
                else
                {
                    if (b >= 0)
                    {
                        long diff = Math.Abs(b) + 1;
                        diff_sum -= diff;
                        ans += diff;
                    }
                }
            }
            return ans;
        }
    }
}

class Program

{

static void Main()

{

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

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

long[] B = new long[N + 1];

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

B[i + 1] = B[i] + A[i];

B = B.Skip(1).ToArray();

Console.WriteLine(Math.Min(Solve(true), Solve(false)));

long Solve(bool is_first_plus)

{

long ans = 0;

long diff_sum = 0;

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

{

long b = B[i] + diff_sum;

if (i % 2 == (is_first_plus ? 0 : 1))

{

if (b <= 0)

{

long diff = Math.Abs(b) + 1;

diff_sum += diff;

ans += diff;

}

else

{

if (b >= 0)

{

long diff = Math.Abs(b) + 1;

diff_sum -= diff;

ans += diff;

}

return ans;

}

D – Chat in a Circle

問題の概要

フレンドリーさが A[i] である N 人の人がいる。
人を適切な順番で輪に追加していく。一番最初に輪にはいった人以外は両隣にいる人のうちフレンドリーさが小さいほうと同じだけの心地よさを感じる。
心地よさの総和が最大になるときの値は？

X さんと Y さんの間に Z さんが入ると、次に輪に入る人はXさんとYさんの間には入れません。そのかわり、Z さんが輪に入ることで X さんと Z さん、Y さんと Z さんの間であれば人が入れるようになります（人が入れる場所が増えていく）。

もしフレンドリーさを大きい順にソートしておけば Z さんの隣に入ったときに得られる心地よさは Z さんのフレンドリーさと同じになります。つまりこの問題は PriorityQueue を使えば解くことができるのです。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        A = A.OrderByDescending(_ => _).ToArray();

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

        pq.Enqueue(A[0], - A[0]);

        long ans = 0;
        for (int i = 1; i < N; i++)
        {
            // 二人目以降が輪に入ると入れる場所が 1 箇所減り 2 箇所増える
            ans += pq.Dequeue();
            pq.Enqueue(A[i], - A[i]);
            pq.Enqueue(A[i], - A[i]);
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

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

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A = A.OrderByDescending(_ => _).ToArray();

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

pq.Enqueue(A[0], - A[0]);

long ans = 0;

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

{

// 二人目以降が輪に入ると入れる場所が 1 箇所減り 2 箇所増える

ans += pq.Dequeue();

pq.Enqueue(A[i], - A[i]);

}

Console.WriteLine(ans);

}

D – Islands War

東西一列に並んだ N 個の島と N – 1 本の橋がある。
橋はとなりあう島同士を繋いている。
a[i]番目とb[i]番目の島の間で争いが起こったために、橋を取り除いて両者のあいだを行き来できないようにしたい。
橋を取り除く数を最小化する場合、取り除かなければならない橋は何個か？

D – Destroyer Takahashiに似た問題です。「a[i] から b[i] – 1 までを覆うブロックが存在する。有効範囲 1 のパンチを繰り返してすべてのブロックを破壊したい。何回必要か？」と読み替えれば同じ問題になってしまいます。

これは区間スケジューリング問題（M 個の区間が与えられ、どのふたつの区間も時間帯を共有しないように最大個数の区間を選べ）と同じ解法です。なので解も区間スケジューリング問題と同じになります。

class Program
{
    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

        (int N, int M) = ReadInt2();

        PriorityQueue<(int, int), int> pq = new PriorityQueue<(int, int), int>();
        for (int i = 0; i < M; i++)
        {
            (int left, int right) = ReadInt2();
            right--;
            pq.Enqueue((left, right), right);
        }

        int ans = 0;

        int r = 0;
        while (pq.Count > 0)
        {
            while (pq.Count > 0 && pq.Peek().Item1 <= r)
                pq.Dequeue();

            if (pq.Count > 0)
            {
                r = pq.Dequeue().Item2;
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

(int N, int M) = ReadInt2();

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

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

{

(int left, int right) = ReadInt2();

right--;

pq.Enqueue((left, right), right);

}

int ans = 0;

int r = 0;

while (pq.Count > 0)

{

while (pq.Count > 0 && pq.Peek().Item1 <= r)

pq.Dequeue();

if (pq.Count > 0)

{

r = pq.Dequeue().Item2;

ans++;

}

Console.WriteLine(ans);

}

A – Diverse Word

問題の概要

英小文字からなる空でない文字列であって、文字がすべて異なる場合、これを多彩な文字列と定義する。
多彩な文字列 S が与えられる。これより辞書順で大きく最小の多彩な文字列は何か？

S のなかに使われていない文字がある場合、そのなかで最小の文字を末尾に追加したものが解となります。

そのような文字がない場合、S から末尾の文字を取り除き集合 no_use にいれておきます。no_use のなかにその文字よりも大きな文字がある場合はそのなかから最小の文字を取り出して S の末尾に追加したものが解です。解が見つからず S の長さが 0 になった場合は、題意をみたす解は存在しないので -1 を出力します。

class Program
{
    static void Main()
    {
        List<char> S = Console.ReadLine().ToList();

        HashSet<char> set = new HashSet<char>(S);

        List<char> no_use = new List<char>();
        for (int i = 0; i < 26; i++)
        {
            char ch = (char)('a' + i);
            if(!set.Contains(ch))
                no_use.Add(ch);
        }

        if (no_use.Count > 0)
        {
            char ch = no_use.Min();
            S.Add(ch);
            Console.WriteLine(new string(S.ToArray()));
            return;
        }

        while (true)
        {
            if (S.Count == 0)
            {
                Console.WriteLine(-1);
                return;
            }

            char last = S.Last();
            S.RemoveAt(S.Count - 1);
            no_use.Add(last);

            char[] arr = no_use.Where(_ => _ > last).ToArray();
            if (arr.Length > 0)
            {
                S.Add(arr.Min());
                Console.WriteLine(new string(S.ToArray()));
                return;
            }
        }
    }
}

class Program

{

static void Main()

{

List<char> S = Console.ReadLine().ToList();

HashSet<char> set = new HashSet<char>(S);

List<char> no_use = new List<char>();

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

{

char ch = (char)('a' + i);

if(!set.Contains(ch))

no_use.Add(ch);

}

if (no_use.Count > 0)

{

char ch = no_use.Min();

S.Add(ch);

Console.WriteLine(new string(S.ToArray()));

return;

}

while (true)

{

if (S.Count == 0)

{

Console.WriteLine(-1);

return;

}

char last = S.Last();

S.RemoveAt(S.Count - 1);

no_use.Add(last);

char[] arr = no_use.Where(_ => _ > last).ToArray();

if (arr.Length > 0)

{

S.Add(arr.Min());

Console.WriteLine(new string(S.ToArray()));

return;

}

A – Sorted Arrays

問題の概要

長さ N の配列 A が与えられる。
A を何箇所かで切って、A の連続した部分であるようないくつかの数列に分ける。
すべて広義単調増加または広義単調減少である配列にわける場合、最小で何個に分ければよいだろうか？

A の要素を別のリストに追加していきます。増加しているリストであるにもかかわらず小さな値を追加しようとした場合や減少しているリストであるにもかかわらず大きな値を追加しようとしている場合はリストを作り直します。

リストを何回作り直したかを数えればよいです。

class Program
{
    class Pair
    {
        public Stack<int> Stack = new Stack<int>();

        // 'U' 格納されている値は増加している
        // 'D' 減少している
        // 'N' まだ定まっていない（要素数が 1 または最初の値と同じ値が格納され続けている）
        public char Dir = 'N';
    }

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int ans = 1;
        Pair pair = new Pair();
        foreach (int v in A)
        {
            if (pair.Stack.Count == 0)
                pair.Stack.Push(v);

            else if (pair.Dir == 'N')
            {
                if (pair.Stack.Peek() < v)
                    pair.Dir = 'U';
                if (pair.Stack.Peek() > v)
                    pair.Dir = 'D';
                pair.Stack.Push(v);
            }
            else if (pair.Dir == 'U')
            {
                if (pair.Stack.Peek() > v)
                {
                    pair = new Pair();
                    ans++;
                }
                pair.Stack.Push(v);
            }
            else if (pair.Dir == 'D')
            {
                if (pair.Stack.Peek() < v)
                {
                    pair = new Pair();
                    ans++;
                }
                pair.Stack.Push(v);
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

class Pair

{

public Stack<int> Stack = new Stack<int>();

// 'U' 格納されている値は増加している

// 'D' 減少している

// 'N' まだ定まっていない（要素数が 1 または最初の値と同じ値が格納され続けている）

public char Dir = 'N';

}

static void Main()

{

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

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int ans = 1;

Pair pair = new Pair();

foreach (int v in A)

{

if (pair.Stack.Count == 0)

pair.Stack.Push(v);

else if (pair.Dir == 'N')

{

if (pair.Stack.Peek() < v)

pair.Dir = 'U';

if (pair.Stack.Peek() > v)

pair.Dir = 'D';

pair.Stack.Push(v);

}

else if (pair.Dir == 'U')

{

if (pair.Stack.Peek() > v)

{

pair = new Pair();

ans++;

}

pair.Stack.Push(v);

}

else if (pair.Dir == 'D')

{

if (pair.Stack.Peek() < v)

{

pair = new Pair();

ans++;

}

pair.Stack.Push(v);

}

Console.WriteLine(ans);

}

A71 – Homework

問題の概要

長さ N の自然数列 A, B が与えられる。
それぞれの順番を適切に入れ替えることで A[i] × B[i] の総和を最小化したい。最小値はなにか？

片方を昇順、他方を降順にソートして A[i] × B[i] の総和を計算すれば最小値が得られます。ただそれだけの問題です。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        A = A.OrderBy(x => x).ToArray();
        B = B.OrderByDescending(x => x).ToArray();

        int ans = 0;
        for (int i = 0; i < N; i++)
            ans += A[i] * B[i];

        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

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

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A = A.OrderBy(x => x).ToArray();

B = B.OrderByDescending(x => x).ToArray();

int ans = 0;

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

ans += A[i] * B[i];

Console.WriteLine(ans);

}

F – タスクの消化

問題の概要

N 個のタスクがあり、i 個目のタスクは A[i] 日目かそれ以降に実行することができる。
タスクを消化することで B[i] ポイントが得られる。
1 日ごとに「タスクを一つ選んでそれを消化する」ことを繰り返す場合、1 日から k 日までの間に得られるポイントの合計の最大値を求めよ。

1 日目から N 日目まで各日についてシミュレーションすればよいです。タスクが実行可能になった日に消化することでもらえるポイントを PriorityQueue に格納していき、それぞれの日に PriorityQueue から最大値を取得して加算していけばよいです。

class Program
{
    static void Main()
    {
        (int, int) ReadInt2()
        {
            string[] vs = Console.ReadLine().Split();
            return (int.Parse(vs[0]), int.Parse(vs[1]));
        }

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

        Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
        for (int i = 0; i < N; i++)
        {
            (int a, int b) = ReadInt2();
            a--;
            if(!dic.ContainsKey(a))
                dic.Add(a, new List<int>());
            dic[a].Add(b);
        }

        int ans = 0;

        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        for (int i = 0; i < N; i++)
        {
            if (dic.ContainsKey(i))
            {
                foreach (int v in dic[i])
                pq.Enqueue(v, - v);
            }
            if (pq.Count > 0)
                ans += pq.Dequeue();

            Console.WriteLine(ans);
        }
    }
}

class Program

{

static void Main()

{

(int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

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

Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();

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

{

(int a, int b) = ReadInt2();

a--;

if(!dic.ContainsKey(a))

dic.Add(a, new List<int>());

dic[a].Add(b);

}

int ans = 0;

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

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

{

if (dic.ContainsKey(i))

{

foreach (int v in dic[i])

pq.Enqueue(v, - v);

}

if (pq.Count > 0)

ans += pq.Dequeue();

Console.WriteLine(ans);

}

AtCoder NoviStepsを埋めてみる(2) 貪欲法 2Q問題

082 – Interval Scheduling Problem

079 – Two by Two（★3）

D – Take ABC 2

C – AtCoder Riko

C – Alternated

D – Get Many Stickers

C – Giant Domino

D – String Rotation

D – Merge Slimes

C – Approximate Equalization 2

D – Destroyer Takahashi

D – Shipping Center

D – Choose Me

D – Takahashi Unevolved

D – Powerful Discount Tickets

D – Integer Cards

B – Increasing Triples

C – Sequence

D – Chat in a Circle

D – Islands War

A – Diverse Word

A – Sorted Arrays

A71 – Homework

F – タスクの消化

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

コメントについて

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

コメントをどうぞ