ABC166振り返り

んぐです。気が向いた回はコンテストの振り返りをすることにしました。今回は一日遅れですが、基本はコンテストがあった日にさっと書いてしまおうと思います。解答までの思考プロセスを書いていきたいんですけど、口調をどうしようか困りますね（解説口調で喋られるほど実力がない）。まあ適当に書きます。

結果

atcoder.jp

実力相応でした。でも安定して緑になるためにもう少し高いパフォーマンスをとっていきたいですね。

解答

A問題

受け取った文字列がABCならARC、ARCならABCと出力すれば良いですね。簡単な条件分岐を書けばよいですが、直前に解いていた過去問で map を使っていたのでそれで解きました。問題タイトルのヒント（？）にしたがってS[2文字目]だけを比較して条件分岐する方法もありますね。もちろんそんなことしませんが。

int main() {
    string S; cin >> S;
    map<string, string> mp;
    mp["ABC"] = "ARC";
    mp["ARC"] = "ABC";

    cout << mp[S] << endl;

    return 0;
}

B問題

難しめのBでしたね。問題文の意味を汲み取るのに苦労しました（解いてるときはってなんだ…？悩んでしまいました）。

「すぬけ君」が（種類によらず）とにかく何か持っていればお菓子を持っていさえすれば、いたずらされません。よって「お菓子をもらったら、そのすぬけ君はいたずら対象から外す」ということが書ければなんとかなりそうですね。

僕は「あるすぬけ君がお菓子をもらったら、そのすぬけ君をいたずら非対象集合sにinsertする。すぬけ君の数からいたずら非対象集合sの要素数を引けば、いたずらされるすぬけ君の数が得られる」という方法で実装しました。

int main() {
    int N, K; cin >> N >> K;
    set<int> s;
    rep (i, K) {
        int d; cin >> d;
        rep (m, d) {
            int a; cin >> a;
            s.insert(a);
        }
    }

    cout << N - s.size() << endl;

    return 0;
}

C問題

今回は簡単めのCで安心しました（前回のC許さん）。このコンテストの前日にこの問題を解いていたのが効いたのか、すんなり解法の発想が浮かびました。

例がどちらもそんなに大きなでなかったので素直に紙に図示してみました。「一つの頂点について、そこからいけるどの頂点にある展望台よりも高ければ良い展望台」ということは「一つの頂点について、そこからいける頂点にある展望台のほうが高ければ良い展望台でない」ということです。辺, が与えられた時点で]と]を比べちゃえば良いので、オーダーはO(M)であることがわかります。これは間に合うので、この方針にしました。この問題もsetが役に立ってくれました。

int main() {
    int N, M; cin >> N >> M;
    vector<int> H(N); for(auto& it : H) { cin >> it; }

    set<int> s;
    rep (i, M) {
        int a, b; cin >> a >> b;
        a--; b--; // 0-index

        if (H[a] <= H[b]) s.insert(a);
        if (H[b] <= H[a]) s.insert(b);
    }

    cout << N - s.size() << endl;

    return 0;
}

D問題

未証明で出しちゃったやつです。Maximaを使ってとなることは容易に知ったので、の約数を求めて…みたいな解法でやろうとたのですが、実装がうまくできず順位表を見るにもっと簡単な解法で解けるんだろうということもあり諦めました。

そこで、「はlong longに収まる問題設定になってるやろ！」ということを仮定し、LLONG_MINからLLONG_MAXの5乗根の範囲で全探索することにしました。long longの最大値といってもそんなに大きくないですし、5乗根をとれば十分間に合うと判断しました。しかし、さすがに2乗オーダーで解くわけにもいかなかったので、 が整数ならOKという方法を用いることで線形オーダーに落としました。5乗根のとり方が難しかったのと、これ誤差でWAにならないか？という一抹の不安はありましたが、楽観的に見積もって提出しました。ACしたときは手を叩いて喜んでしまいました（そこまでの問題か？（））

template <class Type> inline constexpr Type Pow5(Type x) { return x*x*x*x*x; } // 英語違う気がするけど気にしない

int main() {
    lint X; cin >> X;
 
    for (lint A = 0; Pow5(A) < LINT_MAX; ++A) {
        lint B5 = Pow5(A) - A;
        lint B;
        if (B5 < 0) {
            B = powl((long double)-B5, (long double)0.2);
            if (-Pow5(B) == B5) { Print(A, -B); return 0; }
        }
        else {
            B = powl((long double)B5, (long double)0.2);
            if (Pow5(B) == B5) { Print(A, B); return 0; }
        }
    }

    /* LINT_MIN ~ 0 の範囲も同様に */

    return 0;
}

E問題

コンテストが終わってから解きました。なんとなく連想記憶使ったら良さそうだなーとかいい感じに問題を分離して前計算的なことをすれば解けそうだなーとか考えていたのですが、わかりませんでした。後から解説を見て次のコードで通しました。

発想さえできれば非常に簡単な実装だったため、めちゃくちゃコンディション良ければ通せたりしたのかなーとか（たられば）

学びとしては

• とりあえず式を立ててみる
• 絶対値は外すというよりは、とりあえず中身は正だと仮定する
• 添字の分離

ですかね

int main() {
    lint N; cin >> N;
    vector<lint> A(N); for(auto& it:A) { cin >> it; }

    map<lint, lint> L, R;
    rep (i, N) L[i] = (i+1) + A[i];
    rep (k, N) R[(k+1) - A[k]]++;

    lint ans = 0;
    rep (i, N) ans += R[L[i]];

    Print(ans);

    return 0;
}

F問題

解説見て「よくわからんけど概ね貪欲にやればええんやなふーん」となって終わりました。以上

総括

可もなく不可もなくって感じですね。このパフォーマンスを安定してだせればいいんですが、定期的に2完をかますのでなかなか緑安定しません。