【AtCoder 反省会】AtCoder Beginner Contest 425

コンテストサイト
前回

今回からちょっと方針を変えようと思います。
というのも、AtCoderの高難易度問題は、実務で必要なものとはちょっと違うと感じたからです。
なので、A,B,C 問題のみに絞ってやろうと思います。

A

AC

回答コード

static void impl()
{
    int N;
    cin >> N;

    int ans = 0;
    FOR1(i, N)
    {
        int pre = (i & 1) ? -1 : 1;
        int num = i * i * i;
        ans += pre * num;
    }

    cout << ans << '\n';
}

B

AC

回答コード

static void impl()
{
    int N;
    cin >> N;

    vec<int> A(N);
    for (auto &a : A)
        cin >> a;

    vec<int> P(N);
    FOR1(i, N)
    P[i - 1] = i;

    sort(all(P));
    do
    {
        bool ok = true;
        FOR1(i, N)
        {
            if (A[i - 1] != -1)
            {
                if (A[i - 1] != P[i - 1])
                {
                    ok = false;
                    break;
                }
            }
        }
        if (ok)
        {
            out << "Yes\n";
            FOR(i, N)
            {
                out << P[i];
                if (i < N - 1)
                    out << ' ';
            }
            return;
        }
    } while (next_permutation(all(P)));

    out << "No\n";
    return;
}

C

TLE

回答コード

static void impl()
{
    int N, Q;
    cin >> N >> Q;

    vec<int> A(N);
    for (auto &a : A)
        cin >> a;

    int head = 0;

    while (Q--)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int c;
            cin >> c;

            head = (head + c) % N;
        }
        else
        {
            int l, r;
            cin >> l >> r;

            int begin = (head + l - 1) % N;
            int end = (head + r - 1) % N;

            ull sum = 0;
            int i = begin;
            while (true)
            {
                sum += A[i];

                if (i == end)
                    break;
                i = (i + 1) % N;
            }

            out << sum << "\n";
        }
    }
}

クエリ2の計算時間を短縮できなかった。
累積和が使えるとのことで、なるほど、と思った。
コンテスト後、改良してAC。

改良コード

static void impl()
{
    int N, Q;
    cin >> N >> Q;

    vec<int> A(N);
    vec<int> A_doubled(N << 1);
    FOR(i, N)
    {
        int a;
        cin >> a;

        A[i] = a;
        A_doubled[i] = a;
        A_doubled[i + N] = a;
    }

    // A_doubledの先頭からi番目までの和
    vec<ull> sums(N << 1, 0);
    sums[0] = A_doubled[0];
    FOR1(i, (N << 1) - 1)
    sums[i] = sums[i - 1] + A_doubled[i];

    int head = 0;

    while (Q--)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int c;
            cin >> c;

            head = (head + c) % N;
        }
        else
        {
            int l, r;
            cin >> l >> r;

            ull sum = sums[head + r - 1] - sums[head + l - 1];
            sum += A_doubled[head + l - 1];
            out << sum << "\n";
        }
    }
}