ABC172に挑んだ回

投稿日: 2020年6月28日 2020年6月28日
投稿者: sorahako
カテゴリー: Atcoder

ちょっと今回異様に難しくないですか？
B止まりはめちゃくちゃ悔しい。
発想力というか、柔軟さに欠けている。

C - Tsundoku

最初愚直に少ない方を加算してた。
その後問題文見返して、あぁDPか。DP理解できないって逃げた。
そして蓋を開けたらDPじゃない。なにこれ。

解答は解説通り。


void funcC() {
    ll N, M, K;
    cin >> N >> M >> K;

    // 棚Aの先頭からの合算値と、棚Bの先頭からの合算値をBooksに保存。
    // 合算値の時点で合計時間を超えたらBooksには入れない。
    vector<ll> aBooks;
    {
        ll a = 0;
        aBooks.push_back(0);
        for (ll i = 0; i < N; ++i) {
            ll n;
            cin >> n; // 読み込み中断すると次のB列に影響するので注意（やらかした）
            if (a + n < K) {
                aBooks.push_back(a + n);
                a += n;
            }
        }
    }

    vector<ll> bBooks;
    {
        ll a = 0;
        bBooks.push_back(0);
        for (ll i = 0; i < M; ++i) {
            ll n;
            cin >> n;
            bBooks.push_back(a+n);
            a += n;
            if (a > K)   break;
        }
    }

    // ここまでで、Booksにはそれぞれ棚Aだけ・棚Bだけを読める最大数が保存されてる。

    ll bRead = bBooks.size()-1; // 棚Bを全部読めたと仮定する
    ll ans = 0;

    // 下記forループでやってること。

    // 最初は棚Aのを1冊だけ読んでみる。
    // その時点で棚A＋棚Bの読んだ時間が制限時間を超えたら、棚Bの本を1冊ずつ減らす。
    // 棚A1冊+棚Bの読めた数：ansで、より多く読めてた方を採用する(max)

    // forループで次は棚Aを2冊読んだ…で計算を続ける。
    // 本は上から順に読むので、棚Bの本は減らしたら戻ることはない。

    for (ll i = 1; i < aBooks.size(); ++i) {
        auto n = K - aBooks[i];
        while (bBooks[bRead] > n) {
            bRead--;
        }
        ans = max(ans, bRead + i);
    }

    DisplayAnswer(ans);
}

void funcC() {

ll N, M, K;

cin >> N >> M >> K;

// 棚Aの先頭からの合算値と、棚Bの先頭からの合算値をBooksに保存。

// 合算値の時点で合計時間を超えたらBooksには入れない。

vector<ll> aBooks;

{

ll a = 0;

aBooks.push_back(0);

for (ll i = 0; i < N; ++i) {

ll n;

cin >> n; // 読み込み中断すると次のB列に影響するので注意（やらかした）

if (a + n < K) {

aBooks.push_back(a + n);

a += n;

}

vector<ll> bBooks;

{

ll a = 0;

bBooks.push_back(0);

for (ll i = 0; i < M; ++i) {

ll n;

cin >> n;

bBooks.push_back(a+n);

a += n;

if (a > K) break;

}

// ここまでで、Booksにはそれぞれ棚Aだけ・棚Bだけを読める最大数が保存されてる。

ll bRead = bBooks.size()-1; // 棚Bを全部読めたと仮定する

ll ans = 0;

// 下記forループでやってること。

// 最初は棚Aのを1冊だけ読んでみる。

// その時点で棚A＋棚Bの読んだ時間が制限時間を超えたら、棚Bの本を1冊ずつ減らす。

// 棚A1冊+棚Bの読めた数：ansで、より多く読めてた方を採用する(max)

// forループで次は棚Aを2冊読んだ…で計算を続ける。

// 本は上から順に読むので、棚Bの本は減らしたら戻ることはない。

for (ll i = 1; i < aBooks.size(); ++i) {

auto n = K - aBooks[i];

while (bBooks[bRead] > n) {

bRead--;

}

ans = max(ans, bRead + i);

}

DisplayAnswer(ans);

}

D - Sum of Divisors

約数の情報を保存して計算回数減らしたりするかなー。
でも面倒だし、DPの勉強してこよって逃げた。
仮に約数に着目して続けてたとしても、時間的に間に合わないように作られてたらしい。
ある意味逃げてて正解。
そういう部分も計算量からぱっと理解できるようになりたい。

約数うんぬんから目をそらして、普通に計算式としてどうなりそうかに着目すべき？だった問題らしい。
（解説PDF見てもあんま理解できなくて、他の人の答えを見ながら考えて理解した。

例題ケースの[4]の場合、約数の件の詳細は以下のような感じ。
1:1→1個*1
2:1,2→2個*2
3:1,3→2個*3
4,1,2,4→3個*4

1は1,2,3,4…のすべてで登場するし、2は2,4,6…の2の倍数、3は3,6,9…の3の倍数で登場する。
ので、これらの登場回数を配列でカウントして、最後に配列のインデックスで掛け算すれば答えになる。

void funcD() {

    ll N;
    cin >> N;

    ll ans = 0;
    vector<ll> counts(N+1, 0); // 要素を1~N+1で使う
    for (ll i = 1; i <= N; ++i) {
        // 1~Nまで、割り切れる数として+=iで計算する
        // 結果、jはiの倍数なので、登場回数として[j]++する。
        for (ll j = i; j <= N; j+=i) {
            counts[j]++;
        }
    }

    // 登場回数*iを加算する
    for (ll i = 1; i <= N; ++i) {
        ans += counts[i] * i;
    }
    DisplayAnswer(ans);
}

void funcD() {

ll N;

cin >> N;

ll ans = 0;

vector<ll> counts(N+1, 0); // 要素を1~N+1で使う

for (ll i = 1; i <= N; ++i) {

// 1~Nまで、割り切れる数として+=iで計算する

// 結果、jはiの倍数なので、登場回数として[j]++する。

for (ll j = i; j <= N; j+=i) {

counts[j]++;

}

// 登場回数*iを加算する

for (ll i = 1; i <= N; ++i) {

ans += counts[i] * i;

}

DisplayAnswer(ans);

}

DP

↓見ながらお勉強中。
蛙は飛ばしたよ。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

C - Tsundoku

D - Sum of Divisors

DP

sorahako

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル