AtCoder Grand Contest 024 参加ログ

結果

 A,B,Cの3完で597位。C問題で7WAも出してしまったのが反省点だけど、簡単めとはいえ700点問題を通せたので個人的には悪くない結果だと思った。

 パフォーマンスは1621、レートは1598(+3)で、惜しくも青コーダー復帰とはならず。 f:id:tokumini:20180521093647p:plain

思考ログ

 解法はほぼ公式の解説PDFの通りなので、そこに至るまでの思考過程を中心に記録。

A問題

 300点問題なのでちょっとひねるのかなとは思いつつ、まずは愚直に式変形をしてみるとそのまま法則性が見えたのですぐAC。単純に設問の操作通り式変形して法則性が見える問題というのも多くはないだろうけど、初手としてやる価値はあるんだろう。

B問題

 抽象的に考えるのは難しそうだったので入力例を紙の上で解いてみてまずは解法を探る。

 やっていると、先頭に入れていく数字は1ずつ小さくする、末尾に入れていく数字は1ずつ大きくすることで整列した形で入れられることに気づく。そうなると挿入しないでも整列している数字が何個あるかがわかれば解けそうだという考えに至った。

 その後すぐは、もとの数列内で単調増加する最長の部分列かなと考えたけど、入力例3などでそれはダメ。で、ちょっと考えているとより厳しく1ずつ増えていく最長の部分列じゃないかという発想に至り、理屈を考えてもそれでうまくいきそうだと確認した。つまり先頭にx, x-1, ..., 1、末尾にy, y+1, ..., Nを入れていくことになるわけで、x+1 から y-1がもとの数列で整列していれば良いということ。

 あとはその実装なんだけど、競技プログラミングに慣れて一番伸びたのはこういう実装がすぐにできるところなんじゃないかと思う。

num[i] := iから始まる1ずつ増加する部分列の長さ

として、数列の後ろから見ていけばいいと考えてAC。25分弱で解けてなかなか良いペースだと感じた。

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

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }

    vector<int> num(N + 2, 0);
    for (int i = N - 1; i >= 0; i--) {
        num[P[i]] = num[P[i] + 1] + 1;
    }

    cout << N - *max_element(num.begin(), num.end()) << endl;
}

C問題

 やっぱり入力例を手で解いていくわけだけど、まず先頭は0でないといけないということはすぐわかる。また連続した2つの差が2以上あるのもダメだなというのは気づいた。

 これで多分ダメなケースは弾けたと感じて最小回数の方を考えてみると、やはり後ろから山を作っていくイメージで最小になるんじゃないかと考えた。

 最終的にみるとこれでおおむね合っていたわけだけど、最小回数を求める方の実装がバグっておりWA。しかしダメな例の判定の方がバグっていそうと感じてそっちを修正しに行ってしまった。0の次に2が来る場合だけとか、0からの距離が数字以上に離れていたらダメとか、変なことを考えてWAを重ねていく。

 そのせいで最小回数を求める方のバグに気づいても負例の除去がバグっていてさらにWA。なにもわからなくなってしまいassertを仕込んで負例の除去がちゃんとできているか確認したところ、どうもそれがおかしいと気づいて、一番最初の条件に戻してやっとAC。

 一回WAを出したあと、もうちょっと冷静にどこが間違っているのか考える必要がある。これは今までに何回も思っていることなんだけど、性格にもかかわることでそう簡単に直せるものでもないなぁ。

 数列を後ろから見ていくという発想がB問題と同じだったのが多少幸運だったか。

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

int main() {
    int64_t N;
    cin >> N;
    vector<int64_t> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    if (A[0] != 0) {
        cout << -1 << endl;
        return 0;
    }

    for (int i = 1; i < N; i++) {
        if (A[i] - A[i - 1] > 1) {
            cout << -1 << endl;
            return 0;
        }
    }

    uint64_t ans = 0;
    vector<int64_t> X(N, 0);
    for (int64_t i = N - 1; i >= 1; i--) {
        if (X[i] != A[i]) {
            ans += A[i];
        }
        X[i - 1] = A[i] - 1;
    }

    cout << ans << endl;
}

D問題

 問題の意味さえあまりわからなかった。なんか対称性? を作ればいいのかなという感じに思ったけど、それをグラフとしてどう実装するのかもさっぱりわからず、残り時間は座っているだけだった。1100点という数字を見るだけで思考が停止してしまうようなところがあり、ダメだなぁと感じる。