第1回岩井星人アンソロジープログラミングコンテストの問題を解いてみる

第1回岩井星人アンソロジープログラミングコンテストはYouTubeで競技プログラミングの実況を行っている岩井星人さんを題材にした問題のみを出題するコンテストです。ちなみに岩井星人さんはこんな方です。

「鎖国派最後の生き残り♪令和の大政翼賛会♪」なんて言っちゃってますが、真に右寄りな方ではないのでご安心ください。

ではさっそくいってみましょう。

Contents

1 No.3010 水色コーダーさん
2 No.3011 あ、俺こいつの役やりたい！
3 No.3012 岩井星人グラフ
4 No.3013 ハチマキ買い星人
5 No.3014 岩井満足性問題
- 5.1 メモリー制限に引っかかって不正解
- 5.2 正解例
6 No.3015 右に寄せろ！
7 No.3016 ハチマキおじさん
8 No.3017 交互浴
9 No.3018 目隠し宝探し

No.3010 水色コーダーさん

この問題は、R_i が 1200 以上の場合、S_i の先頭4文字が “oooo” でなかった場合に気絶すると考えてよいので以下のようなコードになります。

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

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

        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            string[] vs = Console.ReadLine().Split();
            string s = vs[0];
            int r = int.Parse(vs[1]);
            if (r >= 1200 && s.Substring(0, 4) != "oooo")
                ans++;
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N, M;

{

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

N = vs[0];

M = vs[1];

}

int ans = 0;

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

{

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

string s = vs[0];

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

if (r >= 1200 && s.Substring(0, 4) != "oooo")

ans++;

}

Console.WriteLine(ans);

}

No.3011 あ、俺こいつの役やりたい！

問題文はこちらです ⇒ No.3011 あ、俺こいつの役やりたい！

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

予算である N 以下の値を出力してしまった段階で即終了となり、しかも

N が報酬の 2 倍以下、別の言い方をすると最後に出力した値が N の半分以上になるようにしなければならないので最初は N が取りうる最大値（10の9乗）を出力して 0 が入力されるたびに半分の値を出力し続ければ正解となります（10の9乗が2の30乗より小さいため）。

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

class Program
{
    static void Main()
    {
        int x = (int)Math.Pow(10, 9);

        while (true)
        {
            Console.WriteLine(x);
            int r = int.Parse(Console.ReadLine());
            if (r == 0)
                x /= 2;
            else
                return;
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int x = (int)Math.Pow(10, 9);

while (true)

{

Console.WriteLine(x);

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

if (r == 0)

x /= 2;

else

return;

}

No.3012 岩井星人グラフ

問題文はこちらです ⇒ No.3012 岩井星人グラフ

要はこんなグラフを出力すればよいのです（ただし頂点番号は0-indexed。回答を出力するときは1-indexedにしないといけないので注意）。

長さがYの腕を先にX本つくります。頂点を番号を0はじまりだとすれば腕の付け根の番号は Yの倍数です。以降の頂点を番号が次のYの倍数より1少ない値になるまで直線上につなげます。最後に腕の付け根を環状に連結します。

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

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

        Console.WriteLine($"{X * Y} {X * Y}");

        List<int> starts = new List<int>();
        for (int s = 0; s < X * Y; s += Y)
        {
            starts.Add(s + 1);
            for (int i = s; i < s + Y - 1; i++)
                Console.WriteLine($"{i + 1} {i + 2}");
        }

        starts.Add(1);
        for (int i = 0; i < starts.Count - 1; i++)
            Console.WriteLine($"{starts[i]} {starts[i + 1]}");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int X, Y;

{

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

X = vs[0];

Y = vs[1];

}

Console.WriteLine($"{X * Y} {X * Y}");

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

for (int s = 0; s < X * Y; s += Y)

{

starts.Add(s + 1);

for (int i = s; i < s + Y - 1; i++)

Console.WriteLine($"{i + 1} {i + 2}");

}

starts.Add(1);

for (int i = 0; i < starts.Count - 1; i++)

Console.WriteLine($"{starts[i]} {starts[i + 1]}");

}

No.3013 ハチマキ買い星人

問題文はこちらです ⇒ No.3013 ハチマキ買い星人

移動するとカツアゲされて残金が減ります。なのであまりカツアゲされないうちに近くて買ってしまうほうがよいか、それとも多少カツアゲされても安くハチマキを買うことができる店まで移動するか、という問題です。これはカツアゲされる合計を頂点までの移動コストと考えて、店がある頂点で残金でどれだけハチマキを買えるかを考えればよいです。またハチマキはすべて同じ店で買います。複数の店で買っても同じ店で買うよりよい解を得ることはできないからです。

失敗例ダイクストラ法ではなくただの幅優先探索

ダイクストラ法ではなくただの幅優先探索で解こうとすると制限時間以内に処理は終わりません。

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

class Edge
{
    public Edge(int f, int n, int c)
    {
        From = f;
        Next = n;
        Cost = c;
    }
    public int From = 0;
    public int Next = 0;
    public int Cost = 0;
}

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

        List<Edge>[] lists = new List<Edge>[N];
        for (int i = 0; i < N; i++)
            lists[i] = new List<Edge>();

        for (int i = 0; i < M; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = vs[0] - 1;
            int b = vs[1] - 1;
            int c = vs[2];
            lists[a].Add(new Edge(a, b, c));
            lists[b].Add(new Edge(b, a, c));
        }

        // 幅優先探索で各頂点までの移動コストを求めようとしている
        long[] costs = new long[N];
        for (int i = 0; i < N; i++)
            costs[i] = long.MaxValue;

        costs[0] = 0;
        Queue<int> q = new Queue<int>();
        q.Enqueue(0);
        while (q.Count > 0)
        {
            int cur = q.Dequeue();
            long cost = costs[cur];
            foreach (Edge edge in lists[cur])
            {
                long ncost = cost + edge.Cost;
                int next = edge.Next;
                if (costs[next] > ncost)
                {
                    costs[next] = ncost;
                    q.Enqueue(next);
                }
            }
        }

        // その頂点に店があるなら残金でハチマキを買えるだけ買ったときの本数を計算する
        long ans = 0;
        for (int i = 0; i < P; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = vs[0] - 1;
            int c = vs[1];
            if (Y - costs[a] > 0)
                ans = Math.Max(ans, (Y - costs[a]) / c);
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Edge

{

public Edge(int f, int n, int c)

{

From = f;

Next = n;

Cost = c;

}

public int From = 0;

public int Next = 0;

public int Cost = 0;

}

class Program

{

static void Main()

{

long N, M, P, Y;

{

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

N = vs[0];

M = vs[1];

P = vs[2];

Y = vs[3];

}

List<Edge>[] lists = new List<Edge>[N];

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

lists[i] = new List<Edge>();

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

{

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

int a = vs[0] - 1;

int b = vs[1] - 1;

int c = vs[2];

lists[a].Add(new Edge(a, b, c));

lists[b].Add(new Edge(b, a, c));

}

// 幅優先探索で各頂点までの移動コストを求めようとしている

long[] costs = new long[N];

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

costs[i] = long.MaxValue;

costs[0] = 0;

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

q.Enqueue(0);

while (q.Count > 0)

{

int cur = q.Dequeue();

long cost = costs[cur];

foreach (Edge edge in lists[cur])

{

long ncost = cost + edge.Cost;

int next = edge.Next;

if (costs[next] > ncost)

{

costs[next] = ncost;

q.Enqueue(next);

}

// その頂点に店があるなら残金でハチマキを買えるだけ買ったときの本数を計算する

long ans = 0;

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

{

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

int a = vs[0] - 1;

int c = vs[1];

if (Y - costs[a] > 0)

ans = Math.Max(ans, (Y - costs[a]) / c);

}

Console.WriteLine(ans);

}

普通の幅優先探索と異なりダイクストラ法は

始点から移動可能な頂点への移動コストの暫定値を計算・記憶しておき、そのなかから最小のものを取り出します。辺の重みがすべて非負数であればその値が更新されることはないので確定させる。移動コストが確定した頂点から移動可能な頂点から移動できる頂点への移動コストの暫定値を計算する……という処理を繰り返す

という方法です。こうすることで無駄な探索と値の更新をなくしています。そしてキューのなかから移動コストが最小のものを取り出すためには優先度付きキュー（PriorityQueue）を使わなければなりません。

失敗例正しくないダイクストラ法

ただし上記コードのQueueをPriorityQueueに取り替えただけでは不十分です。TLE（時間切れ）の件数は減りましたが、やはりすべてのテストケースを通すことができません。

class Program
{
    static void Main()
    {
        // 省略

        List<Edge>[] lists = new List<Edge>[N];
        for (int i = 0; i < N; i++)
            lists[i] = new List<Edge>();

        for (int i = 0; i < M; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = vs[0] - 1;
            int b = vs[1] - 1;
            int c = vs[2];
            lists[a].Add(new Edge(a, b, c));
            lists[b].Add(new Edge(b, a, c));
        }
        long[] costs = new long[N];
        for (int i = 0; i < N; i++)
            costs[i] = long.MaxValue;

        costs[0] = 0;
        PriorityQueue<int, long> pq = new PriorityQueue<int, long>();
        pq.Enqueue(0, 0);
        while (pq.Count > 0)
        {
            int cur = pq.Dequeue();
            long cost = costs[cur];
            foreach (Edge edge in lists[cur])
            {
                long ncost = cost + edge.Cost;
                int next = edge.Next;
                if (costs[next] > ncost)
                {
                    costs[next] = ncost;
                    pq.Enqueue(next, ncost);
                }
            }
        }

        // 省略
    }
}

class Program

{

static void Main()

{

// 省略

List<Edge>[] lists = new List<Edge>[N];

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

lists[i] = new List<Edge>();

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

{

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

int a = vs[0] - 1;

int b = vs[1] - 1;

int c = vs[2];

lists[a].Add(new Edge(a, b, c));

lists[b].Add(new Edge(b, a, c));

}

long[] costs = new long[N];

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

costs[i] = long.MaxValue;

costs[0] = 0;

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

pq.Enqueue(0, 0);

while (pq.Count > 0)

{

int cur = pq.Dequeue();

long cost = costs[cur];

foreach (Edge edge in lists[cur])

{

long ncost = cost + edge.Cost;

int next = edge.Next;

if (costs[next] > ncost)

{

costs[next] = ncost;

pq.Enqueue(next, ncost);

}

// 省略

}

正解例正しいダイクストラ法

ダイクストラ法では、始点から移動可能な頂点への移動コストの暫定値を計算・記憶しておき、そのなかから最小のものを取り出し、この値を確定させます。確定したあとであってもPriorityQueueから同じ頂点への移動コストに関する情報は取り出され続けるので、確定後はそれらは無視しなければなりまん。そうでないと無駄な処理が発生して制限時間以内に終わりません。

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

class Edge
{
    public Edge(int f, int n, int c)
    {
        From = f;
        Next = n;
        Cost = c;
    }
    public int From = 0;
    public int Next = 0;
    public int Cost = 0;
}

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

        List<Edge>[] lists = new List<Edge>[N];
        for (int i = 0; i < N; i++)
            lists[i] = new List<Edge>();

        for (int i = 0; i < M; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = vs[0] - 1;
            int b = vs[1] - 1;
            int c = vs[2];
            lists[a].Add(new Edge(a, b, c));
            lists[b].Add(new Edge(b, a, c));
        }

        long[] costs = new long[N];
        for (int i = 0; i < N; i++)
            costs[i] = long.MaxValue;

        bool[] seen = new bool[N]; // 確定済みかチェックする

        costs[0] = 0;
        PriorityQueue<int, long> pq = new PriorityQueue<int, long>();
        pq.Enqueue(0, 0);
        while (pq.Count > 0)
        {
            int cur = pq.Dequeue();

            if(seen[cur]) // すでに移動コストが確定した頂点であれば無視
                continue;

            seen[cur] = true;

            long cost = costs[cur];
            foreach (Edge edge in lists[cur])
            {
                long ncost = cost + edge.Cost;
                int next = edge.Next;
                if (costs[next] > ncost)
                {
                    costs[next] = ncost;
                    pq.Enqueue(next, ncost);
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < P; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = vs[0] - 1;
            int c = vs[1];
            if (Y - costs[a] > 0)
                ans = Math.Max(ans, (Y - costs[a]) / c);
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Edge

{

public Edge(int f, int n, int c)

{

From = f;

Next = n;

Cost = c;

}

public int From = 0;

public int Next = 0;

public int Cost = 0;

}

class Program

{

static void Main()

{

long N, M, P, Y;

{

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

N = vs[0];

M = vs[1];

P = vs[2];

Y = vs[3];

}

List<Edge>[] lists = new List<Edge>[N];

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

lists[i] = new List<Edge>();

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

{

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

int a = vs[0] - 1;

int b = vs[1] - 1;

int c = vs[2];

lists[a].Add(new Edge(a, b, c));

lists[b].Add(new Edge(b, a, c));

}

long[] costs = new long[N];

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

costs[i] = long.MaxValue;

bool[] seen = new bool[N]; // 確定済みかチェックする

costs[0] = 0;

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

pq.Enqueue(0, 0);

while (pq.Count > 0)

{

int cur = pq.Dequeue();

if(seen[cur]) // すでに移動コストが確定した頂点であれば無視

continue;

seen[cur] = true;

long cost = costs[cur];

foreach (Edge edge in lists[cur])

{

long ncost = cost + edge.Cost;

int next = edge.Next;

if (costs[next] > ncost)

{

costs[next] = ncost;

pq.Enqueue(next, ncost);

}

long ans = 0;

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

{

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

int a = vs[0] - 1;

int c = vs[1];

if (Y - costs[a] > 0)

ans = Math.Max(ans, (Y - costs[a]) / c);

}

Console.WriteLine(ans);

}

No.3014 岩井満足性問題

問題文はこちらです ⇒ No.3014 岩井満足性問題

動的計画法の問題ですが、単純なナップサック問題とちがって満足度と美しさというふたつの要素があります。そこで最初は2次元配列ではなく3次元配列を用いた方法を考えてみることにします。

メモリー制限に引っかかって不正解

以下のコードはやり方はあっているはずなのですが、メモリー制限に引っかかって不正解です。

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

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

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

        // 3次元配列を定義してlong.MinValueで初期化する
        long[,,] dp = new long[N + 1, D + 1, K + 1];
        for (int a = 0; a < dp.GetLength(0); a++)
        {
            for (int b = 0; b < dp.GetLength(1); b++)
            {
                for (int c = 0; c < dp.GetLength(2); c++)
                    dp[a, b, c] = long.MinValue;
            }
        }

        // 最初はなにも選択していないので0個までを選択するかどうかを決定し、実際に0個が選択され、
        // その美しさは0という状態のみが存在する。それ以外の場合は存在しない
        dp[0, 0, 0] = 0;

        for (int i = 0; i < A.Length; i++)
        {
            for (int b = 0; b < dp.GetLength(1); b++)
            {
                for (int c = 0; c < dp.GetLength(2); c++)
                {
                    // 存在しない場合はなにもしない
                    if (dp[i, b, c] == long.MinValue)
                        continue;

                    // i 番目の問題は選択しない場合
                    dp[i + 1, b, c] = Math.Max(dp[i, b, c], dp[i + 1, b, c]);

                    // すでに D 個選択しているのであれば continue
                    if(b >= D)
                        continue;

                    // i 番目の問題は選択した結果、美しさが Kを超える場合は
                    // dp[i + 1, b + 1, K]に値を格納する
                    if (c + C[i] < K)
                        dp[i + 1, b + 1, c + C[i]] = Math.Max(dp[i, b, c] + A[i], dp[i + 1, b + 1, c + C[i]]);
                    else
                        dp[i + 1, b + 1, K] = Math.Max(dp[i, b, c] + A[i], dp[i + 1, b + 1, K]);
                }
            }
        }

        // dp[N, D, K] に long.MinValue 以外の値が格納されていたらそれが満足度の最大値
        if(dp[N, D, K] > long.MinValue)
            Console.WriteLine(dp[N, D, K]);
        else
            Console.WriteLine("No");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N, D, K;

{

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

N = vs[0];

D = vs[1];

K = vs[2];

}

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

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

// 3次元配列を定義してlong.MinValueで初期化する

long[,,] dp = new long[N + 1, D + 1, K + 1];

for (int a = 0; a < dp.GetLength(0); a++)

{

for (int b = 0; b < dp.GetLength(1); b++)

{

for (int c = 0; c < dp.GetLength(2); c++)

dp[a, b, c] = long.MinValue;

}

// 最初はなにも選択していないので0個までを選択するかどうかを決定し、実際に0個が選択され、

// その美しさは0という状態のみが存在する。それ以外の場合は存在しない

dp[0, 0, 0] = 0;

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

{

for (int b = 0; b < dp.GetLength(1); b++)

{

for (int c = 0; c < dp.GetLength(2); c++)

{

// 存在しない場合はなにもしない

if (dp[i, b, c] == long.MinValue)

continue;

// i 番目の問題は選択しない場合

dp[i + 1, b, c] = Math.Max(dp[i, b, c], dp[i + 1, b, c]);

// すでに D 個選択しているのであれば continue

if(b >= D)

continue;

// i 番目の問題は選択した結果、美しさが Kを超える場合は

// dp[i + 1, b + 1, K]に値を格納する

if (c + C[i] < K)

dp[i + 1, b + 1, c + C[i]] = Math.Max(dp[i, b, c] + A[i], dp[i + 1, b + 1, c + C[i]]);

else

dp[i + 1, b + 1, K] = Math.Max(dp[i, b, c] + A[i], dp[i + 1, b + 1, K]);

}

// dp[N, D, K] に long.MinValue 以外の値が格納されていたらそれが満足度の最大値

if(dp[N, D, K] > long.MinValue)

Console.WriteLine(dp[N, D, K]);

else

Console.WriteLine("No");

}

正解例

3次元配列の各行は次の行の値が確定したら使わないので2次元配列で済むように書き換えます。

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

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

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

        long[,] dp = new long[D + 1, K + 1];
        for (int d = 0; d <= D; d++)
        {
            for (int k = 0; k <= K; k++)
                dp[d, k] = long.MinValue;
        }

        dp[0, 0] = 0;

        for (int i = 0; i < A.Length; i++)
        {
            long[,] nextdp = new long[D + 1, K + 1];
            for (int d = 0; d <= D; d++)
            {
                for (int k = 0; k <= K; k++)
                    nextdp[d, k] = long.MinValue;
            }

            for (int d = 0; d <= D; d++)
            {
                for (int k = 0; k <= K; k++)
                {
                    if (dp[d, k] == long.MinValue)
                        continue;

                    nextdp[d, k] = Math.Max(dp[d, k], nextdp[d, k]);
                    if(d >= D)
                        continue;

                    if (k + C[i] < K)
                        nextdp[d + 1, k + C[i]] = Math.Max(dp[d, k] + A[i], nextdp[d + 1, k + C[i]]);
                    else
                        nextdp[d + 1, K] = Math.Max(dp[d, k] + A[i], nextdp[d + 1, K]);
                }
            }
            dp = nextdp;
        }
        if(dp[D, K] > long.MinValue)
            Console.WriteLine(dp[D, K]);
        else
            Console.WriteLine("No");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N, D, K;

{

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

N = vs[0];

D = vs[1];

K = vs[2];

}

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

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

long[,] dp = new long[D + 1, K + 1];

for (int d = 0; d <= D; d++)

{

for (int k = 0; k <= K; k++)

dp[d, k] = long.MinValue;

}

dp[0, 0] = 0;

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

{

long[,] nextdp = new long[D + 1, K + 1];

for (int d = 0; d <= D; d++)

{

for (int k = 0; k <= K; k++)

nextdp[d, k] = long.MinValue;

}

for (int d = 0; d <= D; d++)

{

for (int k = 0; k <= K; k++)

{

if (dp[d, k] == long.MinValue)

continue;

nextdp[d, k] = Math.Max(dp[d, k], nextdp[d, k]);

if(d >= D)

continue;

if (k + C[i] < K)

nextdp[d + 1, k + C[i]] = Math.Max(dp[d, k] + A[i], nextdp[d + 1, k + C[i]]);

else

nextdp[d + 1, K] = Math.Max(dp[d, k] + A[i], nextdp[d + 1, K]);

}

dp = nextdp;

}

if(dp[D, K] > long.MinValue)

Console.WriteLine(dp[D, K]);

else

Console.WriteLine("No");

}

No.3015 右に寄せろ！

問題文はこちらです ⇒ No.3015 右に寄せろ！

これは文字列の中の 110 という連続部分列を 011 に変える操作が何回できるかを数える問題です。

110 を 011 に変えることで 0 の位置が右に 2 つ移動します。なので 0 を何回右に 2 つ移動できるかを数えます。

そのためには 0 の位置をリストに格納して、位置が小さいものから何回 2 を引くことができるかを数えます。このとき indexs[i] から 2 を引くことで 0 を下回ったり indexs[i-1] が存在する場合はこれ以下の値にならないように注意します。

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

class Program
{
    static void Main()
    {
        char[] S = Console.ReadLine().ToArray();
        List<int> indexs = new List<int>();
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] == '0')
                indexs.Add(i);
        }

        long ans = 0;
        for (int i = 0; i < indexs.Count; i++)
        {
            if (i == 0)
            {
                int v = indexs[0] / 2; // 2 を引くことができる回数を計算する
                indexs[0] -= 2 * v; // 引いたあとの値に更新する
                ans += v;
            }
            else
            {
                // indexs[i-1] が存在する場合はこれ以下の値にならないように注意
                int v  = (indexs[i] - indexs[i-1] - 1) / 2;
                indexs[i] -= 2 * v;
                ans += v;
            }
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

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

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

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

{

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

indexs.Add(i);

}

long ans = 0;

for (int i = 0; i < indexs.Count; i++)

{

if (i == 0)

{

int v = indexs[0] / 2; // 2 を引くことができる回数を計算する

indexs[0] -= 2 * v; // 引いたあとの値に更新する

ans += v;

}

else

{

// indexs[i-1] が存在する場合はこれ以下の値にならないように注意

int v = (indexs[i] - indexs[i-1] - 1) / 2;

indexs[i] -= 2 * v;

ans += v;

}

Console.WriteLine(ans);

}

No.3016 ハチマキおじさん

問題文はこちらです ⇒ No.3016 ハチマキおじさん

配列 A と B があり、A の長さのほうが 1 大きいです。このとき、|A[i] – B[j]| の総和を最小化するにはどうすればいいかを問う問題です。

もし A と B が同じ長さなら A と B をソートしてあとは添字が同じもの同士を計算すればよいです。問題では A のほうが 1 長いのでどれを取り除くと総和を最小化することができるかを考えるのですが、実は A[0] を取り除いたときの総和がわかれば、この値を利用して A[1] を取り除いたときの総和を求める簡単な方法があるのです。

A[0] を取り除いたときの総和とは、|A[1] – B[0]| + |A[2] – B[1]| + |A[3] – B[2]| + |A[4] – B[3]| + … ですが、これに |A[0] – B[0]| を足して |A[1] – B[0]| を引けば A[1] を取り除いたときの総和になるのです。

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

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(_ => _).ToArray();
        B = B.OrderBy(_ => _).ToArray();

        long sum = 0;
        for (int i = 1; i < N; i++)
        {
            int v = Math.Abs(A[i] - B[i - 1]);
            sum += v;
        }

        // Keyが取り除いたハチマキの長さ Valueが不満度の総和
        List<KeyValuePair<int, long>> list = new List<KeyValuePair<int, long>>();
        list.Add(new KeyValuePair<int, long>(A[0], sum));

        for (int i = 0; i < N - 1; i++)
        {
            sum += Math.Abs(A[i] - B[i]);
            sum -= Math.Abs(A[i + 1] - B[i]);
            list.Add(new KeyValuePair<int, long>(A[i + 1], sum));
        }

        // 不満度の総和の最小値を求める
        long min = list.Min(_ => _.Value);

        // 必要なのは不満度の総和が最小になるときのハチマキの長さ（重複は取り除く）
        int[] rets = list.Where(_ => _.Value == min).Select(_ => _.Key).Distinct().OrderBy(_ => _).ToArray();

        Console.WriteLine(rets.Length);
        Console.WriteLine(string.Join(" ", rets));
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

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(_ => _).ToArray();

B = B.OrderBy(_ => _).ToArray();

long sum = 0;

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

{

int v = Math.Abs(A[i] - B[i - 1]);

sum += v;

}

// Keyが取り除いたハチマキの長さ Valueが不満度の総和

List<KeyValuePair<int, long>> list = new List<KeyValuePair<int, long>>();

list.Add(new KeyValuePair<int, long>(A[0], sum));

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

{

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

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

list.Add(new KeyValuePair<int, long>(A[i + 1], sum));

}

// 不満度の総和の最小値を求める

long min = list.Min(_ => _.Value);

// 必要なのは不満度の総和が最小になるときのハチマキの長さ（重複は取り除く）

int[] rets = list.Where(_ => _.Value == min).Select(_ => _.Key).Distinct().OrderBy(_ => _).ToArray();

Console.WriteLine(rets.Length);

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

}

No.3017 交互浴

問題文はこちらです ⇒ No.3017 交互浴

温泉に入ることで身体の色が塗り替えられていきます。水色の部分の長さを求めよという問題です。

塗り替えられた長さをStackに追加していくのですが、そのまえに前の色が新しい色で完全に塗り替えられるのであればその部分は同じ色でも異なる色でもStackから削除します。Stackから削除した結果、前の色と新しい色が同じ場合は追加しません。Stackへの追加と削除が繰り返されるたびに ans の値を加除します。

途中でStackが空になってしまうと処理が面倒になるので、最初に 10^9 + 1 の長さで緑色に塗っておきます。問題文では最初は岩井星人さんの身体は全身が緑色であることと、色が変わるのは 10^9 までなのでこれでも問題はありません。

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

class Data
{
    public Data(int color, int height)
    {
        Color = color;
        Height = height;
    }
    public int Color = 0;
    public int Height = 0;
}

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

        int ans = 0;
        Stack<Data> stack = new Stack<Data>();
        stack.Push(new Data(0, (int)Math.Pow(10, 9) + 1));

        for (int i = 0; i < N; i++)
        {
            int v = A[i];

            while (true)
            {
                if (stack.Peek().Height > v)
                    break;

                // 水色の部分が取り除かれた場合はそのぶん水色の部分が短くなるので減算する
                // 緑色の部分が取り除かれた場合はそのぶん水色の部分が長くなるので加算する
                Data pop = stack.Pop();
                ans -= pop.Color == 1 ? pop.Height : -pop.Height;
            }

            Data peek = stack.Peek();
            if (i % 2 == 0 && peek.Color == 0) // 水色の温泉に入った場合、かつ stack.Peek()が緑
            {
                // 水色の部分が追加された場合はそのぶん水色の部分が長くなるので加算する
                stack.Push(new Data(1, v));
                ans += v;
            }
            else if (i % 2 == 1 && peek.Color == 1) // 緑色の温泉、かつ stack.Peek()が水色
            {
                // 緑色の部分が追加された場合はそのぶん水色の部分が短くなるので減算する
                stack.Push(new Data(0, v));
                ans -= v;
            }
            Console.WriteLine(ans);
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Data

{

public Data(int color, int height)

{

Color = color;

Height = height;

}

public int Color = 0;

public int Height = 0;

}

class Program

{

static void Main()

{

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

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

int ans = 0;

Stack<Data> stack = new Stack<Data>();

stack.Push(new Data(0, (int)Math.Pow(10, 9) + 1));

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

{

int v = A[i];

while (true)

{

if (stack.Peek().Height > v)

break;

// 水色の部分が取り除かれた場合はそのぶん水色の部分が短くなるので減算する

// 緑色の部分が取り除かれた場合はそのぶん水色の部分が長くなるので加算する

Data pop = stack.Pop();

ans -= pop.Color == 1 ? pop.Height : -pop.Height;

}

Data peek = stack.Peek();

if (i % 2 == 0 && peek.Color == 0) // 水色の温泉に入った場合、かつ stack.Peek()が緑

{

// 水色の部分が追加された場合はそのぶん水色の部分が長くなるので加算する

stack.Push(new Data(1, v));

ans += v;

}

else if (i % 2 == 1 && peek.Color == 1) // 緑色の温泉、かつ stack.Peek()が水色

{

// 緑色の部分が追加された場合はそのぶん水色の部分が短くなるので減算する

stack.Push(new Data(0, v));

ans -= v;

}

Console.WriteLine(ans);

}

No.3018 目隠し宝探し

問題文はこちらです ⇒ No.3018 目隠し宝探し

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。基本的に質問は2回で宝物の位置を特定できます。またグリッドのサイズによっては質問は1回だけ、または0回で宝物の位置を特定できる場合があります。この場合は質問回数がそれよりも多いと不正解になってしまいます。

グリッドの幅と高さが両方とも 1 の場合は質問しなくても宝物の位置は特定されます。それ以外の場合は左上から宝物までのユークリッド距離の 2 乗を質問します。そしてグリッド上を全探索して該当するマスを列挙します。もしそのようなマスがひとつに限定されたら処理は終了です。ひとつに限定されなかった場合は続いて右上から宝物までのユークリッド距離の 2 乗を質問します。これで宝物があるマスは必ずひとつに限定されます。宝物があるマスが特定されたらその座標を出力するだけです。

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

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

        if (H == 1 && W == 1) // この場合はただちに特定される
        {
            Console.WriteLine($"! {1} {1}");
            return;
        }

        bool[,] grid = new bool[H, W];
        for (int row = 0; row < H; row++)
        {
            for (int col = 0; col < W; col++)
                grid[row, col] = true;
        }

        int y = 0;
        int x = 0;
        Console.WriteLine($"? {y + 1} {x + 1}");
        int d = int.Parse(Console.ReadLine());
        if (d == -1) // 入力が -1 なら直ちに終了
            return;
        if (Check(grid, H, W, y, x, d)) // trueが返されたときは特定できたので直ちに終了
            return;

        x = W - 1;
        Console.WriteLine($"? {y + 1} {x + 1}");
        d = int.Parse(Console.ReadLine());
        if (d == -1)
            return;
        Check(grid, H, W, y, x, d);
    }

    // （y, x）からユークリッド距離の 2 乗が d であるマスがひとつだけならtrueを返す
    static bool Check(bool[,] grid, int H, int W, int y, int x, int d)
    {
        for (int row = 0; row < H; row++)
        {
            for (int col = 0; col < W; col++)
            {
                if ((row - y) * (row - y) + (col - x) * (col - x) != d)
                    grid[row, col] = false;
            }
        }

        int hit = 0;
        int hitX = 0;
        int hitY = 0;
        for (int row = 0; row < H; row++)
        {
            for (int col = 0; col < W; col++)
            {
                if (grid[row, col])
                {
                    hit++;
                    hitY = row;
                    hitX = col;
                }
            }
        }
        if (hit == 1)
        {
            Console.WriteLine($"! {hitY + 1} {hitX + 1}");
            return true;
        }
        else
            return false;
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int H, W;

{

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

H = vs[0];

W = vs[1];

}

if (H == 1 && W == 1) // この場合はただちに特定される

{

Console.WriteLine($"! {1} {1}");

return;

}

bool[,] grid = new bool[H, W];

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

{

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

grid[row, col] = true;

}

int y = 0;

int x = 0;

Console.WriteLine($"? {y + 1} {x + 1}");

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

if (d == -1) // 入力が -1 なら直ちに終了

return;

if (Check(grid, H, W, y, x, d)) // trueが返されたときは特定できたので直ちに終了

return;

x = W - 1;

Console.WriteLine($"? {y + 1} {x + 1}");

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

if (d == -1)

return;

Check(grid, H, W, y, x, d);

}

// （y, x）からユークリッド距離の 2 乗が d であるマスがひとつだけならtrueを返す

static bool Check(bool[,] grid, int H, int W, int y, int x, int d)

{

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

{

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

{

if ((row - y) * (row - y) + (col - x) * (col - x) != d)

grid[row, col] = false;

}

int hit = 0;

int hitX = 0;

int hitY = 0;

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

{

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

{

if (grid[row, col])

{

hit++;

hitY = row;

hitX = col;

}

if (hit == 1)

{

Console.WriteLine($"! {hitY + 1} {hitX + 1}");

return true;

}

else

return false;

}

第1回岩井星人アンソロジープログラミングコンテストの問題を解いてみる

No.3010 水色コーダーさん

No.3011 あ、俺こいつの役やりたい！

No.3012 岩井星人グラフ

No.3013 ハチマキ買い星人

失敗例ダイクストラ法ではなくただの幅優先探索

失敗例正しくないダイクストラ法

正解例正しいダイクストラ法

No.3014 岩井満足性問題

メモリー制限に引っかかって不正解

正解例

No.3015 右に寄せろ！

No.3016 ハチマキおじさん

No.3017 交互浴

No.3018 目隠し宝探し

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

コメントについて

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

コメントをどうぞ

No.3010 水色コーダーさん

No.3011 あ、俺こいつの役やりたい！

No.3012 岩井星人グラフ

No.3013 ハチマキ買い星人

失敗例 ダイクストラ法ではなくただの幅優先探索

失敗例 正しくないダイクストラ法

正解例 正しいダイクストラ法

No.3014 岩井満足性問題

メモリー制限に引っかかって不正解

正解例

No.3015 右に寄せろ！

No.3016 ハチマキおじさん

No.3017 交互浴

No.3018 目隠し宝探し

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

コメントについて

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

コメントをどうぞ

失敗例ダイクストラ法ではなくただの幅優先探索

失敗例正しくないダイクストラ法

正解例正しいダイクストラ法