ABC290

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc290

問題A

コンテスト提出

A[B[i]]の合計値が答えとなります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var answer = B.Sum(x => A[x - 1]);
    Console.WriteLine(answer);
}

問題B

コンテスト提出

oの数がKの場合かつS[i]がoの場合はT[i]はoとなり、それ以外の場合はT[i]はxになります。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var S = Scanner.Scan<string>();
    var buffer = new char[N];
    var k = 0;
    for (var i = 0; i < N; i++)
    {
        if (k < K && S[i] == 'o')
        {
            buffer[i] = 'o';
            k++;
        }
        else
        {
            buffer[i] = 'x';
        }
    }
    var answer = new string(buffer);
    Console.WriteLine(answer);
}

問題C

コンテスト提出

Aの重複を取り除き昇順にソートした初めのK個以内のものをCとしたとき、0から順に数えて初めてCに出現しなかった数が答えとなります。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var mex = 0;
    foreach(var x in A.OrderBy(x => x).Distinct().Take(K))
    {
        if(x == mex) mex++;
        else break;
    }

    Console.WriteLine(mex);
}

問題D

コンテスト提出

マスが無限に続き、手順i-iiiをt回操作したのときのxをf(t)としたとき、f(t)==D*(t-1)になります。 また、マスがN個で始点を0としたときに、手順i-iiiを繰り返して再び始点0に戻ってくる、つまりf(t)%N==0となるには、Lcm(a,b)をaとbの最小公倍数としたとき、f(t)==Lcm(N,D)になる必要があります。
そして、手順iiにより始点に再び戻ってきたときに始点を+1することから、K回操作したときの始点の変更回数は、f(K)/Lcm(N,D)回であることがわかります。 このことから、K回目のxの位置は(f(K) + f(K)/Lcm(N,D)) % Nとなります。

public static void Solve()
{
    var T = Scanner.Scan<int>();
    while (T-- > 0)
    {
        var (N, D, K) = Scanner.Scan<long, long, long>();
        var x = D * (K - 1);
        var answer = (x + x / Lcm(N, D)) % N;
        Console.WriteLine(answer);
    }
}

public static long Lcm(long a, long b) => a / Gcd(a, b) * b;
public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);