ABC251

はじめに

AtCoder Beginner Contest 251の復習記事です。

記事におけるScannerクラスは、自作の入力クラスです。

コンテスト

https://atcoder.jp/contests/abc251

問題A

コンテスト提出

Sを繰り返して長さ6以上の文字列を作成し、長さ6の文字をSubStringやRangeで作成します。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var answer = S;
    while (answer.Length < 6)
    {
        answer += S;
    }

    answer = answer[0..6];
    Console.WriteLine(answer);
}

問題B

コンテスト提出

1<=i,j,k<=Nの組み合わせのうち、A[i]、A[i]+A[j]、A[i]+A[j]+A[k]かつW以下になる組み合わせを全探索し、重複をなくしたものが答えとなります。

public static void Solve()
{
    var (N, W) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var set = new HashSet<int>();
    for (var i = 0; i < N; i++)
    {
        set.Add(A[i]);
        for (var j = i + 1; j < N; j++)
        {
            set.Add(A[i] + A[j]);
            for (var k = j + 1; k < N; k++)
            {
                set.Add(A[i] + A[j] + A[k]);
            }
        }
    }

    var answer = set.Count(x => x <= W);
    Console.WriteLine(answer);
}

問題C

コンテスト提出

各文字列において2番目以降のスコアを無視したとき、スコアが最大の文字列が何番目にでてくるかを解答します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var sub = new (string S, int T)[N];
    for (var i = 0; i < N; i++)
    {
        var (s, t) = Scanner.Scan<string, int>();
        sub[i] = (s, t);
    }

    var dict = new Dictionary<string, int>();

    for (var i = N - 1; i >= 0; i--)
    {
        var (s, t) = sub[i];
        dict[s] = t;
    }

    var max = -1;
    var result = "";
    foreach (var (s, t) in dict)
    {
        if (max < t)
        {
            max = t;
            result = s;
        }
    }

    for (var i = 0; i < N; i++)
    {
        if (result == sub[i].S)
        {
            Console.WriteLine(i + 1);
            return;
        }
    }
}

問題D

復習提出

• なにこれ?????????
• フィボナッチ数列とかでどうにかならないか
• W=100,000が解ければよさそう

1-100、100-10000、10000-1000000をカバーできれば全ての範囲をカバーできるようです。

public static void Solve()
{
    var W = Scanner.Scan<int>();
    var list = new List<int>();

    for (var i = 1; i <= 100; i++)
    {
        list.Add(i);
        list.Add(i * 100);
        list.Add(i * 10000);
    }

    Console.WriteLine(list.Count);
    Console.WriteLine(string.Join(" ", list));
}

問題E

復習提出

• 二部探索?
• 動的計画法?
• i=1とi=Nの処理をどうするか

i=1を採用したときとi=Nを採用したときの2つのパターンで動的計画法を解くことが解法でした。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    const long inf = (long)1e18;

    var answer = inf;
    for (var k = 0; k < 2; k++)
    {
        var dp = new long[N + 10, 2];
        if (k == 0)
        {
            dp[1, 0] = 0;
            dp[1, 1] = inf;
        }
        else
        {
            dp[1, 0] = inf;
            dp[1, 1] = A[0];
        }

        for (var i = 1; i < N; i++)
        {
            dp[i + 1, 0] = dp[i, 1];
            dp[i + 1, 1] = Math.Min(dp[i, 0], dp[i, 1]) + A[i];
        }

        if (k == 0) answer = Math.Min(answer, dp[N, 1]);
        else answer = Math.Min(answer, Math.Min(dp[N, 0], dp[N, 1]));
    }

    Console.WriteLine(answer);
}