AtCoder Beginner Contest 128 F - Frog Jump

問題: F - Frog Jump

公式解説: https://img.atcoder.jp/abc128/editorial.pdf

問題概要

座標 上を移動する．移動は座標 0 から始めて， だけ正の方向に進むことと， だけ負の方向に進むことを交互に繰り返す． にたどり着いた地点で終了する．同じ座標を2度訪れてはいけない．

座標 0 と 座標 以外の各座標は，訪れると点数がもらえる．負の点数もありうる．

と を適切に定め，もらえる点数の合計を最大化せよ．

解法概要

座標 以降に移動することは考えなくて良いので， にたどり着くことができるとしたら正の方向に進んだときだけである．また， であるような場合も考えなくて良い． したがって，座標の遷移は次のような形になるはずである:

回移動するとする) ．

これの奇数 / 偶数番目を抜き出した数列を考えると，隣接する要素の差が の等差数列となっている:

奇数番目の要素を抜き出した数列:

偶数番目の要素を抜き出した数列．

ここで， とおくと

奇数番目の要素を抜き出した数列:

偶数番目の要素を抜き出した数列．

だいぶスッキリして見える (主観) ．偶数番目の要素について，(0 との差ではなく) N-1 との差に注目して式変形をすると:

奇数番目の要素を抜き出した数列:

偶数番目の要素を抜き出した数列．

したがって，題意の通りに移動したときのスコアは の関数 として表現することができる．

と表現できることから， が決まればスコアは程数時間で求めることができる．

また， でなければならないことから，全体の時間計算量は である．*1

ただし， が の約数であるような場合のみ注意が必要である．このような場合は， となったとき，同じ座標のスコアを 2 回足してしまうことになる．同じ座標を 2 度訪れてはいけないから， が の約数である場合には となった地点でループを抜けなければならない．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> s(n);
    for(int i=0;i<n;++i){
        cin >> s[i];
    }

    ll score = 0LL;
    for(int c=1;c<n/2;++c) {
        ll tmp_score = 0LL;
        if((n-1) % c) {
            for(int x=0;n-1-c*x>=c;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        } else {
            for(int x=0;c*x<n-1-c*x;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        }
        
    }

    cout << score << endl;
}

所感

考察難易度 >> 実装難易度な問題は不得意．

*1: より

AtCoder Beginner Contest 128 F - Frog Jump

問題: F - Frog Jump

公式解説: https://img.atcoder.jp/abc128/editorial.pdf

問題概要

座標 $ 0, 1, 2, \cdots, N-2, N-1 (3 \leq N \leq 10^5) $ 上を移動する．移動は座標 0 から始めて，$ A (\gt 0) $ だけ正の方向に進むことと，$ B (\gt 0) $ だけ負の方向に進むことを交互に繰り返す． $ N-1 $ にたどり着いた地点で終了する．同じ座標を2度訪れてはいけない．

座標 0 と 座標 $ N-1 $ 以外の各座標$ i $は，訪れると点数$ s_i $がもらえる．負の点数もありうる．

$ A $ と $ B $ を適切に定め，もらえる点数の合計を最大化せよ．

解法概要

座標 $ N $ 以降に移動することは考えなくて良いので，$ N-1 $ にたどり着くことができるとしたら正の方向に進んだときだけである．また，$ A \leq B $ であるような場合も考えなくて良い． したがって，座標の遷移は次のような形になるはずである:

$ 0, A, A-B, 2A-B, 2A-2B, \cdots, xA-(x-1)B, xA-xB, (x+1)A-xB=N-1 (2x+1 $回移動するとする) ．

これの奇数 / 偶数番目を抜き出した数列を考えると，隣接する要素の差が$ A-B $ の等差数列となっている:

奇数番目の要素を抜き出した数列: $ 0, A-B, 2A-2B, \cdots, xA-xB $

偶数番目の要素を抜き出した数列$ A, 2A-B, \cdots, xA-(x-1)B, (x+1)A-xB=N-1 (2x+1 $．

ここで，$ A-B=C$ とおくと

奇数番目の要素を抜き出した数列: $ 0, C, 2C, \cdots, xC $

偶数番目の要素を抜き出した数列$ A, A+C, \cdots, A+(x-1)C, A+xC=N-1$．

だいぶスッキリして見える (主観) ．偶数番目の要素について，(0 との差ではなく) N-1 との差に注目して式変形をすると:

奇数番目の要素を抜き出した数列: $ 0, C, 2C, \cdots, xC $

偶数番目の要素を抜き出した数列$ N-1-xC, N-1-(x-1)C, \cdots, N-1-C, N-1$．

したがって，題意の通りに移動したときのスコアは $ C,x $ の関数$ f(C,x) $ として表現することができる．

$ f(C,x) = f(C, x-1) + s_{xC} + s_{N-1-xC} $ と表現できることから，$ x, C $ が決まればスコアは程数時間で求めることができる．

また，$ xC \lt N $ でなければならないことから，全体の時間計算量は $ O(N \log N) $ である．*1

ただし，$ C $ が $ N-1 $ の約数であるような場合のみ注意が必要である．このような場合は，$ xC \leq N-1-xC $ となったとき，同じ座標のスコアを 2 回足してしまうことになる．同じ座標を 2 度訪れてはいけないから，$ C $ が $ N-1 $ の約数である場合には $ xC \leq N-1-xC $ となった地点でループを抜けなければならない．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> s(n);
    for(int i=0;i<n;++i){
        cin >> s[i];
    }

    ll score = 0LL;
    for(int c=1;c<n/2;++c) {
        ll tmp_score = 0LL;
        if((n-1) % c) {
            for(int x=0;n-1-c*x>=c;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        } else {
            for(int x=0;c*x<n-1-c*x;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        }
        
    }

    cout << score << endl;
}

所感

考察難易度 >> 実装難易度な問題は不得意．

*1:$ \log N = \sum_{i=1}^{\infty} \frac{1}{i} $ より

Chokudai SpeedRun 002 L - 長方形 β

L - 長方形 β

問題概要

$ N (\leq 2 \times 10^5) $ 個の長方形がある．$ i (1 \leq i \leq N) $ 番目の長方形は幅 $ A_i (1 \leq A_i \leq 10^9) $ ，高さ $ B_i (1 \leq B_i \leq 10^9) $ である．

以下の条件で長方形を重ねていく．最大いくつの長方形を重ねることができるか．

• 長方形の幅と高さを入れ替えても良い．
• j 番目に配置した長方形が j-1 番目に配置した長方形に完全に含まれる．
• j 番目に配置した長方形の辺と j-1 番目に配置した長方形の辺が接してはならない
• j 番目に配置した長方形の各辺は j-1 番目に配置した長方形の辺のうちいずれかと並行でなければならない．

解法概要

D - プレゼント の類題．違いは幅と高さを入れ替えても良いのかどうかぐらい？

ただ，横長 (縦長) の長方形の中に縦長 (横長) の長方形を入れるくらいだったら縦長横長を揃えた方がたくさんの長方形を重ねられるので，初めに 幅 < 高さ か 高さ < 幅 かで揃えておく．

D - プレゼント と同様に，最長増加列 (LIS) を求める要領で解く．

LIS は $ i \lt j $ かつ $ X_i \lt X_j $ となるような列で長さが最大になるものであり，

$ dp_i = $ 長さが i の増加列の最後の値の最小値

として時間計算量 $ O(n\log n)$ で求める DP が有名である．

$ A_i $ ， $ B_i $ で同じ値が再度登場しないとすると，$ A_i $ の昇順で長方形の ($ A_i, B_i $ ) のペアをソートしておいて，$ B_i $ の LIS を求めればよい．

問題は，$ A_i $ や $ B_i $ で同じ値が登場しうるということである．これについては，ペアをソートする際に例えば ($ A_i , -B_i $ ) でソートするなどすればよい．すると， $ A_i $ が同じなら $ B_i $ } の降順でソートされることになる．こうすることで， $ A_i = A_j $ なのに $ B_i \lt B_j $ となっているがために長方形 i を長方形 j が包んでいることになってしまう……といった事態を防ぐことができる．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pii;

const int A_MAX = 1<<30;

int main() {
    int n;
    cin >> n;
    vector<Pii> a(n);
    for(int i=0;i<n;++i){
        cin >> a[i].first >> a[i].second;
        if(a[i].first > a[i].second) {
            swap(a[i].first, a[i].second);
        }
        a[i].second *= -1;
    }

    sort(a.begin(), a.end());

    vector<int> dp(n+1, A_MAX);
    dp[0] = -a[0].second;
    for(int i=1;i<n;++i) {
        *lower_bound(dp.begin(), dp.end(), -a[i].second) = -a[i].second;
    }

    cout << distance(dp.begin(), lower_bound(dp.begin(), dp.end(), A_MAX)) << endl;
}

所感

SpeedRun は初めてだったけど楽しかった！

LIS を求める DP は見かけるたびに理解し直しになってる気がする……．