JOI 2017-2018 本選参加記

自戒の意をこめて問題に関するものだけ書きます。

問題は https://www.ioi-jp.org/joi/2017/2018-ho/index.html で見てください。

1 問目

やるだけ。

適当に不連続な部分の長さをカウントして、短い方から使う。

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

int main() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int64_t> times(n);
    for (auto&& e : times)
        std::cin >> e;
        
    std::sort(times.begin(), times.end());

    int block = n;
    std::vector<int64_t> blanks;
    blanks.reserve(n);

    for (int i = 1; i < n; ++i) {
        if (times[i - 1] != times[i] - 1)
            blanks.push_back(times[i] - times[i - 1] - 1);
        else
            --block;
    }

    std::sort(blanks.begin(), blanks.end());
    block -= k;

    int64_t ans = n;
    for (int i = 0; i < block; ++i)
        ans += blanks[i];
    
    std::cout << ans << std::endl;
}

2 問目

大きさに関しては最大最小のみが重要なのでとりあえず大きさでソートしてみる。

するとソートした中では連続している美術品を展示する方が良いのがわかる。

また、隣合う美術品の大きさの差を diff とすると例えば入力例 1 では次のようになる。

水色の枠の中にあるのは美術品の価値。

今回は大きさでソートすると [(2, 3), (4, 5), (11, 2)] みたいになるので図のような感じになる。

すると求めたい最大値は「ある美術品と美術品の間の価値の合計からその間にある diff を全て引いた数の最大値」と言い換えられる。

例えば入力例 1 では最初の美術品の価値が 3、次の美術品との diff が 2、二つ目の美術品の価値が 5 で、これを考えた 3 + 5 - 2 = 6 が最良になる。

そう考えるとこの問題は「数列(もどき)の区間和を最大化する」問題に帰着できる。

一瞬セグ木を書きそうになるが、グッと堪えると別に配列を舐めながら走査すれば求まることに気づく。

そんな感じで思考して AC。

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

int main() {
    int64_t n;
    std::cin >> n;

    std::vector<std::pair<int64_t, int64_t>> ab(n);
    for (auto&& e : ab)
        std::cin >> e.first >> e.second;

    std::sort(ab.begin(), ab.end());

    int64_t ans = 0;
    int64_t sum = 0, min = 0;
    for (int i = 0; i < n; ++i) {
        sum += ab[i].second;

        ans = std::max(ans, sum - std::min(min, sum));
    
        if (i < n - 1)
            sum -= ab[i + 1].first - ab[i].first;

        min = std::min(min, sum);
    }
    
    std::cout << ans << std::endl;
}

3 問目

最初団子が刺さる向きが規定されていないと思ってしまいグラフ問題か？となるが、問題をちゃんと読むと刺さる向きは左→右か上→下と書いてある。

考えると左肩下がりの斜め向きの RGW だけ考えればそれ以外は干渉しない気がするので、斜め向きに DP して後で全部足す。提出。小課題 1 以外通らない。

コンテストが残り 1 時間のため「きっと解法が違うんだろう」と諦めて他の問題の部分点を狙おうとする。

これが結果的に大間違いだった事が後で分かる。解法は完全に正しくて実装がバグっていただけだったっぽい。

4 問目

満点解法は微塵も思いつかず、小課題 2 と 3 は分かったため書こうとする。Dijkstra の経路復元をバグらせて Ubuntu の仮想マシンがフリーズする。焦る。

バグを直したところでタイムアップになり、提出できずに終わる。

5 問目

問題だけ読んでデータ構造っぽいとか言ってた。大嘘だった。

総評

2 完 + 3 問目の部分点で 213 点。おそらく 30 位前後だと思う。春合宿には行けなかった。

敗因が明確すぎてとても悔しかった。去年部分点を取らなかったせいで春合宿を逃したのが、今年は部分点を取ろうとしたせいで春合宿を逃すという良い失敗の事例っぽい感じ。

相方がやる気を出し、僕もこれで終わりたくないので PCK には多分出ます。