【AtCoder 反省会】AtCoder Beginner Contest 423

コンテストのサイト
前回

今回の成績

A,B,C 正答
全体的に、問題の理解は簡単だけど、実装は難しいものが多かった。

A

無事一発正解。
特段言うことはなし。

static void impl()
{
    int X, C;
    cin >> X >> C;

    int ans = X / (1e3 + C);
    ull ans_ull = ans * 1000ULL;

    out << ans_ull << endl;
}

B

無事一発正解。
特段言うことはなし。

static void impl()
{
    // ドアの数
    int N;
    cin >> N;

    // 鍵
    vec<int> L(N);
    FOR(i, N)
    cin >> L[i];

    int lidx = -1;
    for (int i = 0; i < N; ++i)
    {
        if (L[i] == 1)
        {
            lidx = i;
            break;
        }
    }

    int ridx = -1;
    for (int i = N - 1; i >= 0; --i)
    {
        if (L[i] == 1)
        {
            ridx = i;
            break;
        }
    }

    if (ridx <= lidx)
    {
        out << 0 << "\n";
        return;
    }

    int ans = ridx - lidx;
    out << ans << "\n";
}

C

無事一発正解。
スッキリした解法で解けて気持ちよかった。

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

    vec<int> L(N);
    FOR(i, N)
    cin >> L[i];

    int cnt = 0;
    // 左
    {
        // 際左の0を探す
        int idx = -1;
        for (int i = 0; i < R; ++i)
        {
            if (L[i] == 0)
            {
                idx = i;
                break;
            }
        }

        // 無いなら終わり
        if (idx != -1)
        {
            // そこから自分までの間で、0なら+1, 1なら+2
            for (int i = idx; i < R; ++i)
            {
                if (L[i] == 0)
                    cnt += 1;
                else
                    cnt += 2;
            }
        }
    }
    // 右
    {
        // 際右の0を探す
        int idx = -1;
        for (int i = N - 1; i >= R; --i)
        {
            if (L[i] == 0)
            {
                idx = i;
                break;
            }
        }

        // 無いなら終わり
        if (idx != -1)
        {
            // そこから自分までの間で、0なら+1, 1なら+2
            for (int i = idx; i >= R; --i)
            {
                if (L[i] == 0)
                    cnt += 1;
                else
                    cnt += 2;
            }
        }
    }

    cout << cnt << '\n';
}

そして…

ここまで21分で完了！自己ベストのパフォーマンス。
F,Gはちょっと難しそうで、D,Eのどちらにしようか悩む。
詰まるポイントが少なそう、ということでE問題に狙いをつけるが、めちゃくちゃ詰まった。

E

実行時間が足らず、残念ながら終了。
考え自体は合っていて、いいところまで来ていた。
whileとforを併用すると、最大 9x10^10 回も計算してしまうので、なんとかwhileの中をO(1)かO(logN)くらいにしたい、と思いつつ、その方法が思いつかなかった。

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

    vec<int> A(N);
    FOR(i, N)
    cin >> A[i];

    while (Q--)
    {
        int L, R;
        cin >> L >> R;

        ull ans = 0;
        int len = R - L + 1;
        for (int i = L, multi = 1; i <= R; ++i, ++multi)
        {
            // 係数
            ull multiplier = multi * (len - multi + 1);
            ans += A[i - 1] * multiplier;
        }
        out << ans << "\n";
    }
}

終了後

解説を見てなるほどと思いつつ、実際に作ってみたが、なぜか一部のテストケースで落ちてしまう。
なぜ？？

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

    vec<int> A(N);
    FOR(i, N)
    cin >> A[i];

    // 0-indexed
    // S0[i] : A[1,i+1] の総和
    // S1[i] : S0[i]*(i+1) の総和
    // S2[i] : S0[i]*(i+1)*(i+1) の総和
    vec<ll> S0(N, 0), S1(N, 0), S2(N, 0);
    FOR(i, N)
    {
        int a = A[i];

        if (i == 0)
        {
            S0[i] = S1[i] = S2[i] = a;
            continue;
        }

        S0[i] = S0[i - 1] + a;
        S1[i] = S1[i - 1] + a * (i + 1);
        S2[i] = S2[i - 1] + a * (i + 1) * (i + 1);
    }

    int L, R;
    while (Q--)
    {
        cin >> L >> R;

        if (L == R)
        {
            out << A[L - 1] << "\n";
            continue;
        }

        // 係数
        ll m0 = (-L + 1) * (R + 1);
        ll m1 = L + R;
        ll m2 = -1;

        // 今回使う総和
        ll s0 = L >= 2 ? (S0[R - 1] - S0[L - 2]) : S0[R - 1];
        ll s1 = L >= 2 ? (S1[R - 1] - S1[L - 2]) : S1[R - 1];
        ll s2 = L >= 2 ? (S2[R - 1] - S2[L - 2]) : S2[R - 1];

        ll ans = m2 * s2 + m1 * s1 + m0 * s0;
        out << ans << "\n";
    }
}

他の問題

D

こっちの方が簡単だったかも。
時間がたっぷり余ったので、4問正解したかった。

F,G

簡単と思いきや難しいヤツ。
いつものことながら、解説が解説してない。

総括

Makefile を作って、コマンドのタイピング時間が減った。結構快適。
出来れば4問正解したかったけど、とりあえずA,B,Cを過去最速&一発正解出来たので、十分な戦果だと思う。
次回も頑張ろう！（今回が簡単だったから、ムズくなってそう）