Blog

Codeforces Round #672 (Div.2)に参加しました

試験が少なすぎて4連休になりました。時間があるので普段はあまり参加しないコドフォに出てみました。

A. Cubes Sorting

バブルソートを行います。操作回数が\(\frac{n(n-1)}{2} - 1\)以下となる配列ならYESを、そうでなければNOと出力しなさい。という問題できた。

バブルソートの「最悪」計算量が\(\frac{n(n-1)}{2}\)であることを知っていれば、そのようなケースの配列と一致しているかを確認するだけですね。知らなくても滅茶苦茶ググってバブルソートの交換回数（反転数と言います）を求めるプログラムを探せば難なくACできます。

しかし私はこの問題を解く直前、下のツイートのような問題を作問しておりまして、まんまと引っ張られました。

流石に2WAしたのは僕の落ち度ですけど…w

結局僕はググってFenwick tree (BIT)による計算方法をコピって通しました。今後このようなことがないようライブラリ化しました。よければ見てください

              
struct FenwickTree {
    int n;
    vi bit;
    FenwickTree(int _n) : n(_n), bit(n+1, 0) {}

    void add(int i, int x) {
        if (i == 0) return;
        for (int k = i; k <= n; k += (k & -k)) bit[k]+=x;
    }

    int sum(int i) {
        int s = 0;
        if (i == 0) return s;
        for (int k = i; k > 0; k -= (k & -k)) s+=bit[k];
        return s;
    }

    int lower_bound(int x) {
        if (x <= 0) return 0;
        else {
            int i = 0; int r = 1;
            while (r < n) r <<= 1;
            for (int dist = r; dist > 0; dist >>= 1) {
                if (i + dist < n and bit[i + dist] < x) {
                    x -= bit[i + dist];
                    i += dist;
                }
            }
            return i+1;
        }
    }
};

int InversionNumber(const vi& v) {
    const int n = len(v);
    FenwickTree fw(n);
    int ret = 0;
    rep (i, n) {
        ret += i - fw.sum(v[i]);
        fw.add(v[i], 1);
    }
    return ret;
}

「転倒数を求めよ」という問題以外で使えるかは分かりませんが…反省の意味も込めて。

B. Rock and Leve

目は通しました。左辺を \(i\) の関数に、右辺を \(j\) の関数にするタイプの問題かなぁと考えていたんですが、そう簡単には移項させてくれませんでした。

仕方がないので本番では先にC1を通すことにしました。時間があれば解けただろうなーというレベルの問題なので悔しい

C1. Pokémon Army (easy version)

DeepLがいきなり「ピカチュウ」とか言い始めたのでびっくりしました。原文読んだらちゃんとピカチュウって書いててさらにびっくり。てかよくよくタイトルみたらPokémonって書いとるやん。

ポケモン好きなので問題になるのは嬉しいのですが、プレッシャーにもなるので解くのはちょっと焦りました。

問題をよく読むとAtCoderでやった問題だ！となりました（全く同じ問題なかった？）。配列の極値を求めて、あとは偶奇や最初の山谷に気をつけて良い感じに足し引きすれば答えが求まります。

DPで解く解法もあるみたいですね。僕はできません。

\(q = 0\)で良かった～～～！

© Copyright 2020 ngng628. All Rights Reserved.