「みんなのプロコン」2019 予選

全体

 A,B,Cの3完で472位。Cをそこそこ早めに解けて一安心し、さあ残った時間でD問題だと感じだったけど歯が立たず。まぁこんなもんですね。

A問題

 100点にしては一瞬考えないといけない問題。というか確信はないままだいたいこんな感じでしょで通した。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    cout << (K <= (N + 1) / 2 ? "YES" : "NO") << endl;
}

B問題

 一筆書きできる(準オイラーグラフというらしい)ものは次数が奇数であるものがちょうど2つだったよなぁという性質を思い出してそれを書く。これも完全に証明できてないままとりあえず提出して通ったという感じで、感覚的にはA,Bのどちらかで1WAくらい食らっててもおかしくない。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    vector<ll> num(4);
    for (ll i = 0; i < 3; i++) {
        ll a, b;
        cin >> a >> b;
        num[a - 1]++;
        num[b - 1]++;
    }

    ll odd = 0;
    for (ll i = 0; i < 4; i++) {
        if (num[i] % 2 == 1) {
            odd++;
        }
    }

    cout << (odd == 2 ? "YES" : "NO") << endl;
}

C問題

 A \lt Bのとき、2回の操作を使ってA枚からB枚に増やせるという話。基本的にはこの交換を繰り返して、最後1回残ったら1枚増やしをする。A \ge Bの場合や最初にA枚まで増やす過程で操作回数がKに達する場合を弾いて、これで大丈夫かなと思ったらサンプル2が合わない。ちょっと考えてそれらで弾かれない場合でも1枚増やしを連打する方が良い場合もあると気づいて、じゃあ連打して得られる 1 + Kと最大の方を答えとすればいいなとしてAC。場合分けをせずこの最大値を取る操作だけで答えを作ろうと悩んでいた時間が無意味だった。場合分けは見落としを生みやすいからあまり入れたくもないが、無理やり消しに行っても良いことはないか。

 解説を読んだらB - A \le 2での場合分けなのか。それはそうだ。頭が悪すぎた。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll K, A, B;
    cin >> K >> A >> B;
    if (A >= B) {
        cout << 1 + K << endl;
        return 0;
    }

    //A枚まで増やす
    if (K <= A - 1) {
        //そこまでで終わってしまう
        cout << 1 + K << endl;
        return 0;
    }

    ll remain = K - (A - 1);
    ll half = remain / 2;
    ll ans = max(1 + K, A + half * (B - A) + (remain % 2));
    cout << ans << endl;
}

D問題

 かなり時間あったのに解けず。このDP見える人間多すぎない? 魔境だなぁ。

 コンテスト中に考えていたこと。まず0をまたぐことはできないから0で分断される各塊について考える。それぞれのコストを計算して、一番小さいところを選んで実行するというイメージ。

 各塊について、基本的には左の1区間から見ていき、その区間を往復して十分回数達したら次の1区間へ移動する。目標回数が奇数ならこれで処理できる。偶数のときは1回余計に多く(あるいは少なく)なるのでコストが1増える。しかし偶数だけで構築されているとまとめて処理することができる。たとえば目標回数が4 4 4だった場合、全部まとめて2往復すればピッタリ達成できる。偶数が連続しているとまとめられる? 奇数が連続していてもまとめられそう。つまり重要なのは偶奇の切り替え回数。

 パターンを考えてみる。O:奇数、E:偶数だとして、偶数同士、奇数同士はまとめるのでOOやEEと連続することはない。まとめた結果長さが2になってOEやEOになるとコスト0で取れる。長さ3だとEOEはコスト0で取れ、OEOにはコスト1かかる。ということを先々までやっていくとなんか法則性があるっぽい? エスパーしたものを書いて出す。半分くらいWA。方針がダメそうなWAの出方だ。考えてみるとEEEをまとめてEにしたとき、コストの増え方は1ではなく3になる。まとめられないじゃん。時間切れ。

 解説を読むと、つまりEOEだけを考えるので良いということか。というか移動の仕方がそうなっていると。目標回数ではなく移動方法に着目してもっと性質を考えないとだめだった。うーん、なるほど。しかしこれをひねり出すのはなかなか難しそうだ。