ABC191 復習 - 文学徒が競プロをするブログ

出れなかったんだけど出なくて正解だった気がするな。C問題の問題文が最後まで意味不明だったんだけど、あれで良いとなったのはマジで謎。

あの問題文で速攻通してる人も謎。

A問題 Vanishing Pitch

丁寧に式を書きました。

B問題 Remove It

for文とif文を書きます。append系の操作が出来るデータ構造を使うと良いですね。

C問題 Digital Graffiti

問題の問題。この問題文で速攻通してる人マジで何？エスパー能力が高すぎる。あとサンプルが一個だけなのも謎ポイント。普通に意味が分からなくて困った。ドット絵かと思うだろ。

ちなみに問題を理解してもそこそこ難しいです。問題文抜きでも茶色diff以上はあるんじゃないかな。ハマるとかなり焦るタイプの問題だと思います。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int h,w; cin>>h>>w;
    vector<string> s(h);
    rep(i,h) cin>>s[i];
    int ans = 0;

    for (int i = 1; i < h-1; ++i) {
        for (int j = 1; j < w-1; ++j) {
            if (s[i][j] == '.') continue;
            int cnt = 0;
            if (s[i+1][j] == '.' && s[i][j-1] == '.') cnt++;
            if (s[i+1][j] == '.' && s[i][j+1] == '.') cnt++;
            if (s[i-1][j] == '.' && s[i][j-1] == '.') cnt++;
            if (s[i-1][j] == '.' && s[i][j+1] == '.') cnt++;
            ans += cnt;
        }
    }

    for (int i = 1; i < h-1; ++i) {
        for (int j = 1; j < w-1; ++j) {
            if (s[i][j] == '#') continue;
            int cnt = 0;
            if (s[i+1][j] == '#' && s[i][j-1] == '#') cnt++;
            if (s[i+1][j] == '#' && s[i][j+1] == '#') cnt++;
            if (s[i-1][j] == '#' && s[i][j-1] == '#') cnt++;
            if (s[i-1][j] == '#' && s[i][j+1] == '#') cnt++;
            ans += cnt;
        }
    }


    cout << ans << '\n';

    return 0;
}

自分は上のようなコードで解きました。

D問題 Circle Lattice Points

問題文を見る -> 「円格子点の数」でググる -> 勝ちを確信して実装 -> 誤差死

多分上の一連を3000人くらいの人がやってそう。

何がアレってpythonで書き直してもそのままじゃ通らないんだよね。pythonは無条件で無限精度だと思っていたのでびっくりしました(カス)。

情報系の教育を受けていないので、倍精度浮動小数点数の誤差は15桁くらいというのを知らなかったのは痛かったです。

整数に直して考える時も、roundでepsを丸めてやるというテクを知らなかったのでバグり散らかしました。小手先テクとして覚えておきます。あとpythonのDecimalね。

E問題 Come Back Quickly

貴重な癒し枠。こいつがいなかったら心が折れていたと思います。ありがとう......。

各頂点について、1本以上の道を通ったあと元の頂点に戻ってくる最短経路を求めろという問題。
まず明らかに、「自分のところに来る辺が存在しない頂点」には、出ていったあと返ってこれないので考えなくていい。

あとは各頂点からダイクストラして、その頂点に帰る辺でつながっている頂点への最短距離を求めてあげて、総距離が一番短いものを選んであげると通ります。

間に合うか若干不安でしたが、他にやりようもなく、辺の数も少ないのでエイっと投げると通りました。信じる心。

F問題

初手の考察を微妙に間違えて、あとワンステップのところまでたどり着けませんでした......。

まずこういった、操作によって状態を変化させていく数え上げ系の問題は、最後に残る数の上界と下界を考えるのが定石だと思います。

まず下界ですが、最後に残る数の最小値は全ての要素のGCDです。
何故かというと、 $gcd(x, y) \leq min(x, y)$ だからです。 $X = Y$ のとき $gcd(x, y) = min(x, y)$ となり、それ以外のときは必ず二値のgcd < 二値のminとなります。

次に上界ですが、これは与えられる数列の最小値です。gcdを取ると必ずmin以下の数になるため、全ての操作でminを取った結果残る数が明らかに最大です。

ここまで五分かそこら程度でわりとすんなり出来たのは良かったなと思います。数式で考えず直感で考えてしまったのは反省ですが。

ここから「GCDとしてあり得る数を全て求めて、上界より小さいかどうかチェックする」ところまで行ければ考察としては完璧だったのですが、
何故かここで「二乗だし各ペアでGCD取ってグループ分けとかすればいいんじゃね」みたいなとんちんかんなことを考え始めてしまいました。

そして各ペアのGCDを列挙して上界より小さい値であればインクリメントするというアルゴリズムを提出し、無事WA......。どうしてそこでそうなっちゃうかな。

敗因は「考察すべき点をしっかり詰めて、迷いのない状態で進めていかないと脳がバグる」という事実を軽視していたことでしょう。

「GCDとしてあり得る全ての数のうち、上界より小さいものは全て残すことが出来る」「だからGCDとしてあり得る数を全て求めて、上界より小さいかどうかチェックすればいい」という方針を確信を持って言語化出来ていればこんなことにはならなかったはずです。

反省しながらこの主張が正しいことを証明してみます。

$Z = gcd(a, b, c, d, ...), M = min_{i=1}^{N} A$ とします。

$M \lt Z$ のとき

$gcd(Z, M) \leq min(Z, M) \lt Z$

となるので、絶対に最後まで残すことが出来ません。

逆に $M \geq Z$ のとき、

$Z = min(Z, M)$ となるので、必ず残すことが出来ます。

頭の中でごちゃごちゃ考えていると
$Z = gcd(a, b, c), S = gcd(s, t, u)$ として、 $S \lt Z \leq M$ の場合、 $Z$ は上界 $M$ より小さいにも関わらず残すことが出来ないように一瞬思えます。

しかしこれは支離滅裂な例です。
$Z$ と $S$ は独立している( $S$ を作っておかなければ $Z$ を作れないというような依存関係はない)ので、普通に $S$ を作らなければ $Z$ をそのまま残すことが出来ます。

以上より、「GCDとしてあり得る全ての数のうち、上界より小さいものは全て残すことが出来る」ことがわかりました。
場合分けすると脳がバグらないな。ノーベル賞級の発見だと思います。複雑な問題を漏れなく単純な問題に場合分けして、それらを個別で解くと頭をバグらせずに元の複雑な問題を解いたことになるんですよね。魔法。

さて続きですが、「GCDとしてあり得る数を全て求めて、上界より小さいかどうかチェックすればいい」ことも示されたので、GCDとしてあり得る数を高速に求められればこの問題を解くことが出来ます。

一番楽な考え方だと $2^{n}$ でGCDを求めればいいですが、当然これは間に合いません。部分和問題っぽいDPが何となく浮かびますが、変な形になりそうなので置いておきます

数学的に良い性質がありそうな気がするので、最大公約数の定義を見ます。「２つ以上の正の整数に共通な約数（公約数）のうち最大のもの」です。

ここで各数字の約数の個数を考えてみると、どうやってもそんなに多くならないので、各数字の約数を全て列挙して、その約数が最大公約数になり得るかどうかを一つずつ確かめれば良さそうな気がしてきます。

ある数の約数 $K$ が、数列 $A$ からいくつかの要素を選んだ集合のGCDとなるか判定することを考えます。

数列 $A$ の要素の内、 $K$ を公約数として含む全ての数(= 全ての $K$ の倍数)を列挙します。

$[a \times K, b \times K, c \times K, d \times K ...$ ]

そしてこの列挙した集合のGCDを実際に取ってみましょう。

もしこの列挙した集合のGCDが $K$ であった場合、 $K$ は明らかにGCDとしてあり得る数の一つです。現行犯ですね。

次にこの集合のGCDが $K$ ではなかった場合を考えます。GCDの定義より、この集合のGCDが $K$ より小さくなることはありません。
よって、GCDが $K$ ではなかった場合、GCDは必ず $K$ よりも大きくなります。

そのGCDを $t \times K$ と置きましょう。すると列挙した全ての $K$ の倍数は、全て $t \times K$ の倍数でもあることになります。

「全ての $K$ の倍数は、全て $t \times K$ の倍数でもある」
　= 「どんな取り方をしてもGCDは $t \times K$ 以上になって、絶対に $K$ にはならない」
ということが言えます。

そして各数字の約数を全て決め打って試すので、この $t \times K$ も放っておけばいずれ試されます。
つまりある数の約数 $K$ について $K$ の倍数を全て列挙し、その集合のGCDが $K$ と一致すれば、 $K$ はGCDとしてあり得る数の一つであると言えます。

これを全ての約数について試せば、GCDとしてあり得る数の全てを求めることが出来ます。

あとは、GCD判定された数が上界以下であることを確認して、setか何かに突っ込んでやれば良いです。実装は結構軽いと思います。

約数を全探索するっていう大ヒントは見てしまったけど、その後を自力で出来たのはよかったかな。

以下コードです。

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (a % b == 0ll) return b;
    return gcd(b, a%b);
}

ll gcd_multi(vector<ll> A) {
    ll n = A.size();
    ll G = A[0];
    for (ll i = 1; i < n; ++i) G = gcd(G, A[i]);
    return G;
}

int main(int argc, char const *argv[]) {
    ll n; cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    map<ll, vector<ll>> mp;

    auto div_cnt = [&](const ll m) {
        for (ll i = 1; i*i <= m; ++i) {
            if (m % i == 0ll) {
                mp[i].push_back(m);
                if (i != m/i) mp[m/i].push_back(m);
            }
        }
        return;
    };

    unordered_set<ll> st;
    ll mini = *min_element(a.begin(), a.end());
    st.insert(mini);

    for (auto &&e: a) div_cnt(e);

    for (const auto [div, arr]: mp) {
        if (gcd_multi(arr) == div) {
            if (div <= mini) st.insert(div);
        }
    }

    cout << st.size() << '\n';

    return 0;
}