ABC292の解法の要点、感想(AからE問題まで)

はじめに

A,B,C,Dの4完で37:24+0ペナでした。
コンテスト後にEも解いたので、それについてもまとめておきます。
コンテスト成績証

なお、記事内で登場するコードには独自のテンプレートやマクロが含まれている場合があります。
それらの詳細については、お手数ですがこちらの記事をご確認ください。

A問題

問題文:

Diff: 7

英小文字からなる文字列を、全て英大文字に変換する問題です。文字列全体を一気に大文字に変換するというよりは、文字列に含まれる文字を1つずつ大文字に変換するイメージで解くとよいでしょう。¹
英小文字を英大文字に変換する方法として、大まかには2パターン挙げられます。

まずASCIIコードの性質を利用する方法です。自分の提出はこのやり方です。
英大文字+32 すると英小文字に、逆に 英小文字-32 すると英大文字になります。異なる型同士で演算しているようですが、char型は整数値をASCIIコードによって文字に変換しているだけなので、内部的には整数同士の演算といえます。とりあえず、英大文字と英小文字間で変換したいときは32という数字が大事なことを覚えておけばよいです。
ASCIIコードはこちらのサイトなどで確認できます。http://www3.nit.ac.jp/~tamura/ex2/ascii.html

もう1つの方法として、std::toupperを利用する方法があります。こちらは公式解説で書かれているので、説明は省きます。

int main() {
    string s;
    cin >> s;
    rep(i, 0, s.size()) { s[i] = s[i] - 32; }
    cout << s << el;
}

提出コード: https://atcoder.jp/contests/abc292/submissions/39405306

B問題

問題文:

Diff: 39

「イエローカード2枚、もしくはレッドカード1枚が提示された選手は退場処分」という条件を言い換えると、「イエローカードは+1のペナルティが、レッドカードは+2のペナルティが、カードを提示された選手に付与されます。ペナルティが2以上の選手は退場処分です。」となります。配列を用いて、この方針に沿った処理をするとよいです。
下のコードでは、vector vが選手のペナルティを表す配列となっています。while(q--)はループのたびにqをデクリメントし、q==0がtrueになるタイミングでループ終了する記法です。

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n, 0);

    while (q--) {
        int t, x;
        cin >> t >> x;
        x--;
        if (t == 1) v[x]++;
        else if (t == 2) v[x] += 2;
        else {
            if (v[x] >= 2) YES;
            else NO;
        }
    }
}

提出コード: https://atcoder.jp/contests/abc292/submissions/39408622

C問題

問題文:

Diff: 444

A,B,C,Dを愚直に全探索で求めようとすると当然TLEするので、1つ1つの操作の性質を見つけて方針を立てていくような形で解きました。
まずAB+CD=Nを満たすAB,CDの通り数は、N-1通りになりそうです(AB,CDは正整数なため)。AB,CDが必ず1以上N未満の値をとることもわかります。
次に、ABはA×Bで表せる数なので、ABの約数にはAとBが含まれていないとおかしいです。(CDも同様、約数にCとDを必ず含む)
よって、N未満の正整数全てについて約数列挙すると、AB,CDの表し方の通り数が求められるのでよさそうです。

なおABの約数の個数と, AB=A×B の表し方の通り数の関係についてですが、この2つの数は等しいです。
例えば9と10について調べてみると、9は{1×9, 3×3, 9×1}と表せるので3通り、約数は{1, 3, 9}の3個なので等しいです。10は{1×10, 2×5, 5×2, 10×1}と表せるので4通り、約数は{1, 2, 5, 10}の4個なので等しいです。

では前準備が終わったので、答えを求めていきます。ABを 1,2,3,...,N-1 と全探索すると、CD=N-AB よりCDにあたる数を$O(1)$で求められます。²ABの約数の個数とCDの約数の個数で積をとり、それを答えに加算していくと求めることができます。

これは約数列挙を$O(\sqrt{N})$で行った場合 $O(N\sqrt{N})$ となり、この問題の制約上では十分高速であるといえます。(とはいえC++でも566msかかったので、もしかしたらPythonとかでは落ちるかも？)

int main() {
    int n;
    cin >> n;
    ll ans = 0;
 
    vector facts(n, vector<ll>());
    rep(i, 1, n) {
        for (ll j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                facts[i].push_back(j);
                if (i / j != j) facts[i].push_back(i / j);
            }
        }
    }
 
    rep(i, 1, n) {
        int N = n - i;
        ans += facts[i].size() * facts[N].size();
    }
    cout << ans << el;
}

提出コード: https://atcoder.jp/contests/abc292/submissions/39423622

D問題

問題文:

Diff: 579

全ての連結成分において、頂点の個数と辺の本数が等しいかを判定する問題です。(グラフが直感に反する形で与えられて少し困惑しました。)
まず与えられたグラフについて連結成分ごとに区別しないと話が始まらないので、そこからやりましょう。
連結成分の検出方法としてはDFSやBFSもありますが、UnionFind(DSU) を使うのが楽です。自分はAtCoder LibraryのDSUを利用して解いています。
dsu::groupsは連結成分ごとにまとめた形の二次元配列を返してくれるので、それによって連結成分ごとに分けます。下のコードにおけるgがそれにあたります。

各連結成分における、頂点の個数と辺の本数の求め方についてですが、まず頂点の個数は各連結成分を表す配列の大きさと等しいです。連結している頂点の番号を配列にして表現しているので、それはそうですね。
辺の本数についてですが、各頂点がUで何回登場したかを調べておくとよいです。Uに{任意の頂点}が登場した場合、その{任意の頂点}から辺が出ているわけなので、回数を記録しておくと本数も答えられる、という寸法です。あまり上手く説明できませんが、イメージするとなんとなく理解してもらえるはずです。
下のコードでは連想配列のstd::mapで記録していますが、別にサイズNの配列を用意して記録しても構いません。

あとは各連結成分について、上の考え方の通りに頂点の個数と辺の本数が一致するかを判定すればよいです。

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    map<int, int> M;
    dsu tree(n);
    rep(i, 0, m) {
        cin >> u[i] >> v[i];
        u[i]--, v[i]--;
        tree.merge(u[i], v[i]);
        M[u[i]]++;
    }
 
    vector<vector<int>> g = tree.groups();
    rep(i, 0, g.size()) {
        int x = 0;
        for (auto y : g[i]) {
            x += M[y];
        }
        if (g[i].size() != x) {
            NO;
            return 0;
        }
    }
    YES;
}

提出コード: https://atcoder.jp/contests/abc292/submissions/39425974

E問題

問題文:

Diff: 1272

問題文が少しつかみづらいので、参考として入出力例1を図示してみましょう。(汚い図ですみません)

実線は入力として与えられていた有向辺で、破線は操作として追加した有向辺を表しています。
これを見ると、破線が向かう先は「始点から有向辺を辿って到達できる頂点のうち、直接有向辺で接続されていないもの」だとわかります。
やるべきことを言い換えると、「全頂点について、距離2以上の頂点に有向辺を張り、その回数を求めよ。 ただし、到達可能な頂点間でのみ距離を定義するものとする。」 となりそうです。これはBFSが非常に有用そうですね。

上記の方針通りに実装しましょう。ただし、実際に有向辺を張る必要はなく、またグラフに閉路が含まれる場合があることに注意が必要です。(入力例3など)
自分の実装では、辺を張ったか確認するためのstd::setを用意し、それに予め始点となる頂点自身と距離1の頂点を入れることで操作しています。

int main() {
    int n, m;
    cin >> n >> m;
    vector g(n, vector<int>());
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
    }
 
    int ans = 0;
    rep(i, 0, n) {
        set<int> se;
        se.insert(i);
        queue<int> que;
        for (auto x : g[i]) {
            que.push(x);
            se.insert(x);
        }
 
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (auto x : g[p]) {
                if (!se.count(x)) {
                    que.push(x);
                    se.insert(x);
                    ans++;
                }
            }
        }
    }
 
    cout << ans << el;
}

提出コード: https://atcoder.jp/contests/abc292/submissions/39490205

感想

C問題がかなり苦手な系統の問題だったので、そこを時間内に解けたのがよかったですね。D問題も考察と実装が悪くない速度でできました。よくわからないまま適当にやっただけ
ただ、E問題が「距離2以上の点に有向辺を張る」と言い換えられず、「距離2の点に有向辺を張る、新しく距離2になった点に有向辺を張る…」といった具合に考察が甘いまま実装してしまったため、解くことができませんでした。BFS問は得意だっただけにかなりくやしい。
あとその名残でグラフをvector<set<int>>で受け取っていたので、コンテスト終了後に解こうにもTLEに苦しまされました。std::setの操作はあくまでも$O(logN)$であり、「ほぼ$O(1)$みたいなものだろ」と過信してはならないんだなぁ、と痛感させられました。
あとC問題のDiff低すぎです。絶対もっと高くていい。

1. std::transformを使えばできなくはないですが、使い方がやや複雑です。Pythonなら楽に一括で変換できるのですが…… ↩

2. ABSのOtoshidamaなどでもみられる工夫ですね。式変形は大事。 ↩