スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

AtCoder Grand Contest 047 感想

atcoder.jp

Aの1完。まーたつまらんパフォをとってしまった。

A - Integer Product

まず、問題文と入力を見て「う゛っ・・・」となった。見たらわかるめんどくさいやつ!

 N \le 2 \times 10^5 なので当然全探索は無理で、なんらかの工夫がいることはすぐにわかる。こういうのはだいたい片方を固定して、条件を満たすもう片方の個数を 高速に求められる方法を頑張って考えればいいんですよね~、と言いながら考察を進めた。

とりあえず、有理数に直すんやろなと思って有理数同士の積が整数となるための条件を考えた。 これはそんなに難しくなくて、2つの有理数  \displaystyle{\frac{p_1}{q_1}, \frac{p_2}{q_2}} (既約) の積が整数となるための条件は  p_1 q_2 の倍数であって、かつ、 p_2 q_1 の倍数であること。

さらによく考えると、入力は小数点つき10進数なのでもう少し形を限定できる。具体的には、次の4パターンがある。

  • パターンa : \displaystyle{p}
  • パターンb : \displaystyle{\frac{p}{2^x}}
  • パターンc : \displaystyle{\frac{p}{5^y}}
  • パターンd : \displaystyle{\frac{p}{2^x 5^y}}

なお  p, x, y は正整数。で、積が整数になる可能性があるのは次の3通り:

(1) パターンa × パターンa (絶対に整数)
(2) パターンa × パターンb,c,d
(3) パターンb × パターンc

[(2)の場合]
パターンaの数を  a、パターンb,c,dの数を  \displaystyle{\frac{b}{2^x 5^y}} ( x, y は非負整数)とする。 これらの積は整数となるための必要十分条件は、 a素因数分解したときに2と5の指数がそれぞれ  x, y 以上になること。

なので、

table1[i][j] = (パターンb,c,dの数のうち「 x \le i かつ  x \le j」を満たすものの個数)

をimosか何かで求めておけば、各パターンaの数について、これとの積が整数となるパターンb,c,dの数の個数が  O(\log a) で求められる。OK!

[(3)の場合]
パターンbの数を  \displaystyle{\frac{b}{2^x}}、パターンcの数を  \displaystyle{\frac{c}{5^y}} ( x, y は正整数) とする。 これらの積が整数となるための必要十分条件は、 b素因数分解したとき5の指数が  y 以上であって、かつ、  c素因数分解したとき2の指数が  x 以上であること。

なので、

table2[i][j] = ( x \le i であるパターンbの数のうち、 b素因数分解したとき5の係数が  y 以上であるものの個数)

をimosか何かで求めておけば、各パターンcの数について、これとの積が整数となるパターンbの数の個数が  O(\log c) で求められる。OK!

うーん、これ解けたときよっしゃ!と思ったけど、実際は解くのがかなり遅かったみたいだ。かなしい。。。

クソ長実装になっちゃったけど簡潔な方法あるのかな。

(下のコードは上の説明と若干違うことをしているので注意 (実質同じだけど))

提出コード

リンク: https://atcoder.jp/contests/agc047/submissions/15785516

ll power(ll a, ll n) {
    ll res = 1;
    for (; n > 0; n >>= 1) {
        if (n & 1) res *= a;
        a *= a;
    }
    return res;
}
 
Pll analyze(ll a) {
    ll cnt2 = 0, cnt5 = 0;
    while (a % 2 == 0) {
        ++cnt2;
        a /= 2;
    }
    while (a % 5 == 0) {
        ++cnt5;
        a /= 5;
    }
    return {cnt2, cnt5};
}
 
using Tup = tuple<ll, ll, ll>;
 
ll table1[31][31];
ll table2[31][31][31];
 
void solve() {
    ll N;
    cin >> N;
    Vl zs;
    vector<Tup> bs, cs, ds;
    for (ll i = 0; i < N; i++) {
        string s;
        cin >> s;
        ll p = 0, cnt = 0;
        bool is_shou = false;
        for (auto c : s) {
            if (c == '.') {
                is_shou = true;
            }
            else {
                ll d = c - '0';
                p *= 10;
                p += d;
                if (is_shou) {
                    ++cnt;
                }
            }
        }
        ll q = power(10, cnt);
        ll g = gcd(p, q);
        p /= g;
        q /= g;
        auto [cnt2, cnt5] = analyze(q);
        if (cnt2 > 0 && cnt5 > 0) {
            ds.emplace_back(p, cnt2, cnt5);
        }
        else if (cnt2 > 0) {
            bs.emplace_back(p, cnt2, 0);
        }
        else if (cnt5 > 0) {
            cs.emplace_back(p, 0, cnt5);
        }
        else {
            zs.emplace_back(p);
        }
    }
 
    ll ans = 0;
 
    // 整数と小数
    for (auto [p, x, y] : bs) {
        ++table1[x][y];
        --table1[30][y];
        --table1[x][30];
        ++table1[30][30];
    }
    for (auto [p, x, y] : cs) {
        ++table1[x][y];
        --table1[30][y];
        --table1[x][30];
        ++table1[30][30];
    }
    for (auto [p, x, y] : ds) {
        ++table1[x][y];
        --table1[30][y];
        --table1[x][30];
        ++table1[30][30];
    }
    for (ll i = 0; i < 30; i++) {
        for (ll j = 0; j < 30; j++) {
            table1[i][j + 1] += table1[i][j];
        }
    }
    for (ll j = 0; j < 30; j++) {
        for (ll i = 0; i < 30; i++) {
            table1[i + 1][j] += table1[i][j];
        }
    }
    for (auto p : zs) {
        auto [cnt2, cnt5] = analyze(p);
        ans += table1[cnt2][cnt5];
    }
 
    // 小数と小数
    for (auto [p, x, y] : bs) {
        auto [cnt2, cnt5] = analyze(p);
        ++table2[x][0][0];
        --table2[x][cnt2 + 1][0];
        --table2[x][0][cnt5 + 1];
        ++table2[x][cnt2 + 1][cnt5 + 1];
    }
    for (ll k = 0; k <= 30; k++) {
        for (ll i = 0; i < 30; i++) {
            for (ll j = 0; j < 30; j++) {
                table2[k][i][j + 1] += table2[k][i][j];
            }
        }
        for (ll j = 0; j < 30; j++) {
            for (ll i = 0; i < 30; i++) {
                table2[k][i + 1][j] += table2[k][i][j];
            }
        }
    }
    for (auto [p, x, y] : cs) {
        auto [cnt2, cnt5] = analyze(p);
        for (ll i = 0; i <= cnt2; i++) {
            ans += table2[i][0][y];
        }
    }
 
    // 整数と整数
    ll nz = (ll)zs.size();
    ans += nz * (nz - 1) / 2;
 
    prints()(ans);
}

B - First Second

解けなかった。。。

文字列  t を操作によって文字列  s に一致させることができるための条件は下の2つを満たすこと:

  •  s t の後ろ  |s| - 1 文字が一致すること
  •  t の後ろから  |s| - 1 文字目より前に 文字  s[1] が含まれる

まぁこれはすぐにわかったけど、ライバル帯もこれはすぐにわかっていそう。ここから先が分からず。。。

各文字列を反転して、キーにそれらのprefixをもつ map か unordered_map で処理しようかなと一瞬思ったけど、どう考えてもメモリが足りないからやめた。

コンテスト終了後にTLを見ると「Trie木を使えばいけるよ!」と書いてあった。Trie木、知らず......。

Trie木を履修した後すぐに解法が思い浮かんだ。くそ~~~おしかった(適当)

Trie木の各ノードに「そのノードを共有する文字列のうち、そのノードより後ろに文字  c を持つ文字列の個数」を c='a', 'b', ..., 'z' について持たせればOK。 これはdfsで求められる。

ローリングハッシュで運ゲーをしてもACをとれるらしい。ロリハもそろそろ履修しないとな......。努力が足りないね。

コンテスト後提出コード

リンク: https://atcoder.jp/contests/agc047/submissions/15834278

template <int char_num, char base>
class Trie {
private:
    struct Node {
        std::array<int, char_num> children;
        std::vector<int> accept;
        std::array<int, char_num> count;
        int common = 0;
        int c;
        Node(int c) : c(c) {
            children.fill(-1);
            count.fill(0);
        }
    };
 
    std::vector<Node> nodes;
    const int root = 0;
 
public:
    Trie() {
        nodes.emplace_back(root);
    }
    void add(const string& str, int str_id) {
        int node_id = 0;
        int sz = static_cast<int>(str.size());
        for (int i = 0; i < sz; i++) {
            int c = static_cast<int>(str[i] - base);
            int next_id = nodes[node_id].children[c];
            if (next_id == -1) {
                next_id = static_cast<int>(nodes.size());
                nodes[node_id].children[c] = next_id;
                nodes.push_back(Node(c));
            }
            ++nodes[node_id].common;
            node_id = next_id;
        }
        ++nodes[node_id].common;
        nodes[node_id].accept.emplace_back(str_id);
    }
    void add(const string& str) {
        add(str, nodes[0].common);
    }
    int query(const string& str, char x) {
        int node_id = 0;
        int sz = static_cast<int>(str.size());
        for (int i = 0; i < sz; i++) {
            int c = static_cast<int>(str[i] - base);
            int next_id = nodes[node_id].children[c];
            if (next_id == -1) {
                return 0;
            }
            node_id = next_id;
        }
        return nodes[node_id].count[x - base];
    }
    int count() {
        return nodes[0].common;
    }
    int size() {
        return static_cast<int>(nodes.size());
    }
 
    void dfs(int idx) {
        auto& count = nodes[idx].count;
        for (int i = 0; i < char_num; i++) {
            int u = nodes[idx].children[i];
            if (u == -1) continue;
            dfs(u);
            count[i] += nodes[u].common;
            for (int j = 0; j < char_num; j++) {
                if (j == i) continue;
                count[j] += nodes[u].count[j];
            }
        }
    }
};
 
void solve() {
    ll N;
    cin >> N;
    vector<string> S(N);
    Trie<26, 'a'> trie;
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
        reverse(S[i].begin(), S[i].end());
        trie.add(S[i]);
    }
    trie.dfs(0);
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans += trie.query(S[i].substr(0, (int)S[i].size() - 1), S[i].back()) - 1;
    }
    prints()(ans);
}