2018-10-06

AtCoder Beginner Contest 112

結果

　36分22秒(3WA)で全完。89位。WAが多すぎた。

AtCoder Regular Contest 052 C - 高橋くんと不思議な道

問題

　 $N$ 個の町が $M$ 個の道で結ばれている。道はタイプ $A,B$ の二種類が存在し、タイプ $A$ のコストは1、タイプ $B$ のコストは(今まで通ったタイプ $B$ の道の本数) + 1である。全ての町について町0からの最小コストを求めよ。

解法

　タイプ $B$ の道はあまり多く使わない方が良い。具体的には解説PDFの通り最小の使用本数+ $\sqrt{N}$ 程度である。頂点をこれらのタイプ $B$ の使用本数で拡張してダイクストラ法を行えばよいわけだが、そもそもこの使用回数がそこまで大きくならないので使用本数が小さい順にpriority_queueから出てくるようにして普通にダイクストラ法をやれば通る。

反省

　1時間53分(5WA)でAC。愚直にダイクストラ法をやってみたり(TLE)、セグメント木を使って高速化(？)してみたり(MLE)、最小全域木問題に帰着したりしないのかなーと思っていろいろ考えていたが1時間経ってしまったので解説を見た。

　なにやら前処理が面倒くさそうだなと思って、同実装するのかcreep04の提出を見てみたらなんか普通のダイクストラ法をやっているようにしか見えない。しばらく考えてから、tupleの順番がb, costの順番になっているのでそれで枝刈り相当のことが実現されているのだと気づいた。

　これで本当に上手くいくのかはきっちり証明できないが、制約の関係から枝刈りっぽいダイクストラ法をやるんだろうなというのは気づきたかったところ。ダイクストラ法は応用が結構あって難しい。

AtCoder Regular Contest 051 C - 掛け算

競技プログラミング

問題

　 $N(\le 50)$ 個の整数 $a_1, \dots, a_N(\le 10^9)$ が与えられる。「一番小さいものを $A(\le10^9)$ 倍する」という操作を $B(\le 10^9)$ 回繰り返した後の整数たちを昇順に並べ出力せよ。

解法

　解説PDFの通り。

　 $a_1, \dots, a_N$ がソートしてあるとして、 $a_1 \times A \ge a_N$ ならばそのあと操作される整数は $a_1, a_2, \dots, a_N, a_1, a_2, \dots, a_N, a_1, a_2, \dots$ となる。したがってそれ以降 $A$ が何回かけられるかは簡単に求めることができる。

　 $a_1 \times A \ge a_N$ になるまでは愚直にシミュレーションするとすると、これは最大値以外の $a_i$ を $A$ 倍していって最大値を超えるまで操作をするということなので、高々 $O(N\log{(\max{a_i})})$ 程度の計算量である。最小値の探索に $O(N)$ かかったとしても $O(N^2\log{(\max{a_i})})$ 。

　シミュレーションが終わったあとは高速な累乗を用いて $O(N\log{B})$ (ここは解説PDFでは $O(N\log{A})$ とあったが違う気がする。自分の勘違いだろうか)で計算できるので、これでこの問題が解けた。

反省

　1時間20分(2WA)でAC。

　最初のころは $\log_A{a_i}$ を考えていけば解けるのかと思ったが、最終的に高速累乗を使わなければならないことは目に見えていて、それだと整数型でかける回数を持っていないとダメだということに気づいて頓挫。

　よってこれを商と余り、みたいな感じで $A^n$ が $a_i$ を超えない最大の $n$ と、そのときの残り部分を持って、 $a_i = A^n + p$ というように分解すれば解けそうと思って実装していく。全操作後の最小な $n$ について二分探索をして、必要な最小操作回数が $B$ となるように求めていく方針でいけると思っていた。

　1時間経ったくらいタイミングでサンプル1と2は合うものができたが、サンプル3がどうしても合わなず、しばらく格闘したが諦めて解説を見た。

　各 $i$ について $n$ の最大と最小が高々1しか差がないことはサンプルの3のデバッグをしているときに気づいたのに、それでシミュレーションすればいいという発想に至らなかった。これはなかなか気づきが必要で難しいように思えるが、問題の考察が足りなかったということだろう。すぐ知っているアルゴリズムに結び付けようとしてしまうが、その前にもっと問題自体の性質を考えなくてはならないなぁ。

AtCoder Regular Contest 050 C - LCM 111

競技プログラミング

問題

　 $1$ を $A$ 個並べてできる整数を $x$ 、 $B$ 個並べてできる整数を $y$ としたとき、 $x$ と $y$ の最小公倍数を $M$ で割った余りを求めよ。

解法

　 $1$ を $n$ 個並べてできる整数を $f(n)$ としたとき $\mathrm{gcd}(f(A), f(B)) = f(\mathrm{gcd}(A, B))$ であることがわかる。最小公倍数は $\mathrm{LCM}(x, y) = \frac{xy}{\mathrm{gcd}(x, y)}$ であるので、 $\frac{f(A)f(B)}{f(\mathrm{gcd}(A, B))}$ を $M$ で割った余りが求まれば良い。 $\mathrm{gcd}(A, B) = g$ とする。ここで $\frac{f(B)}{f(g)}$ は「 $0$ が $g - 1$ 個、 $1$ が1個」という整数を $\frac{B}{g}$ 個並べてできる整数である。

　例. $A = 12, B = 8$ のとき、 $f(A) = 111111111111, f(B) = 11111111$ であり、 $\frac{f(B)}{f(g)} = \frac{11111111}{1111} = 00010001$

　結局 $f(A), \frac{f(B)}{f(g)}$ はそれぞれ「ある整数をある回数並べてできる整数」という形で表現できる。これを $M$ で割った余りは並べる回数を $n$ としたときダブリングによって $O(\log{n})$ で求めることができるので、それぞれ個別に余りを求めた後掛け合わせて最後に $M$ で割った余りを取ればこの問題が解ける。

反省

　51分31秒(0WA)でAC。久しぶりにしっかりと考察して自力で解けたという感じだったが、おそらくこれもコンテストに当時参加していたようなので解説スライドをチラ見したことがあるのだろう。2年半前のコンテストらしいのではっきりと記憶に残っているわけではないが、何となくの方向性などはどこか覚えていて考察が変な方向にいかないというくらいの影響はありそうだ。

　あまりコンテストは休んでないはずなのでここから先は一応見たことがある問題が多いのではないか。B問題で詰まってC問題まで読んでないということはいくらかありそうだが。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll A, B, M;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= M;
        }

        m /= 2;
        n *= n;
        n %= M;
    }

    return result;
}

ll f(ll n, ll c) {
    //「0がc - 1個,1が1個」をn回繰り返し並べた数を返す
    ll result = 0;
    ll m = 1;
    ll d = c;
    while (n) {
        if (n & 1) {
            result *= MODpow(10, d);
            result += m;
            result %= M;
        }

        m = m * MODpow(10, d) + m;
        m %= M;
        d *= 2;
        n /= 2;
    }
    return result;
}

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

int main() {
    cin >> A >> B >> M;
    if (A < B) {
        swap(A, B);
    }

    ll g = gcd(A, B);
    cout << f(A, 1) * f(B / g, g) % M << endl;
}

2018-10-03

AtCoder Regular Contest 049 C - ぬりまーす

競技プログラミング

問題

　 $N(\le 100)$ 頂点のグラフについて、二つのタイプの条件の下に色を塗っていくことを考える。

タイプ1:ある頂点 $x$ に色を塗るとき、既に頂点 $y$ に色が塗られてなければならない。
タイプ2:ある頂点 $u$ に色を塗るとき、既に頂点 $v$ に色が塗られていてはいけない。

　タイプ1の制約は $A(\le 100)$ 個、タイプ2の制約は $B(\le 10)$ 個である。条件を守る限り任意の順番でグラフの頂点を塗れる場合に、最大で何個の頂点を塗ることができるか求めよ。

解法

　解説スライドはスライド中の文字が消えているため下のテキスト部分から解読した。

　タイプ1の制約だけの場合は、塗れるものを塗っていって変化がなくなるまでループを回し続けることで $O(N(N + A))$ で解ける。タイプ2の制約は「頂点 $u$ を塗らないか、あるいは頂点 $v$ に色を塗るときには既に頂点 $u$ に色が塗られてなければならない」と言い換えることができ、後者はタイプ1の制約である。頂点 $u$ を塗らないという制約は簡単に実現できるため、つまりタイプ2の制約については $2^B$ 通り試せばよい。 $B$ は小さいのでこれでこの問題が解けた。

反省

　1時間8分(4WA)でAC。最初はタイプ1の制約もタイプ2の制約もそのまま愚直に考えて、変化がなくなるまでループするという解答を書いて出したところ当然WA。サンプルは合うというのがいやらしい。

　頂点を選択する順番をランダムに選択して何度か実行し最大値を出力するという完全な嘘解法を書いてみて出してみたがダメ。WAは確実に減っているが……。これが解き始めてから30分ほどの時点。

　ちゃんと考察しようと考えなおして強連結成分分解とかdfsでの自己ループ検出とか考えてみたが、結局サンプルが合う解法すらひねり出せず1時間が経ったので解説スライドを見た。

　こういう問題を言い換えるタイプの解法が全然思いつかない。結局考察がほとんどできていないんじゃないか。確信を持っていない解法を書き始めるのはいい加減やめよう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, A, B;

ll solve(vector<vector<ll>> edge, vector<bool> forbid) {
    vector<bool> colored(N, false);
    ll result = 0;
    while (true) {
        bool change = false;

        for (ll i = 0; i < N; i++) {
            //i個目の頂点が塗れるか
            if (colored[i] || forbid[i]) {
                continue;
            }

            bool ok = true;
            for (ll to : edge[i]) {
                if (!colored[to]) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                continue;
            }
            colored[i] = true;
            change = true;
            result++;
        }

        if (!change) {
            break;
        }
    }
    return result;
}

int main() {
    cin >> N;

    vector<vector<ll>> edgeA(N);

    cin >> A;
    for (ll i = 0; i < A; i++) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        edgeA[x].push_back(y);
    }
    cin >> B;
    vector<ll> u(B), v(B);
    for (ll i = 0; i < B; i++) {
        cin >> u[i] >> v[i];
        u[i]--; v[i]--;
    }

    ll ans = 0;

    for (ll i = 0; i < (1LL << B); i++) {
        auto edge = edgeA;
        vector<bool> forbid(N, false);
        for (ll j = 0; j < B; j++) {
            if ((1LL << j) & i) {
                edge[v[j]].push_back(u[j]);
            } else {
                forbid[u[j]] = true;
            }
        }

        ans = max(ans, solve(edge, forbid));
    }
    
    cout << ans << endl;
}

2018-10-02

AtCoder Regular Contest 048 C - 足の多い高橋君

競技プログラミング

問題

　高橋君には足が $N(\le 10^5)$ 本あり、 $i$ 番目の足は $L_i(\le10^9)$ 本の骨が一列に繋がった構造をしている。全ての骨に $0$ または $1$ を書き込むことにし、任意の足2本について片方の足先から胴体を通ってもう一方の足先まで辿って読むと回文になるようにしたとき、文字の書き込み方としてあり得る数を求めよ。

解法

　まず $L_i$ はソートされているものとして考える。次の3つのことが言える。

全ての文字列について先頭 $L_1$ 文字は等しく、これは任意に $0, 1$ を選べる。
各文字列に対して先頭 $L_1$ 文字を取り除いた文字列は回文
2つの異なる文字列に対し「1つ目の文字列の先頭 $L_i$ 文字を取り除いたもの + 2つ目の文字列の先頭 $L_i$ 文字を取り除いたものの反転」が回文

　ここで3つ目の条件は、組み合わせる2つの文字列は2つ目の条件から回文であることがわかっているので、結局「回文と回文を繋げると回文ができる」ということを示している。ここで「長さ $X$ の回文Aと長さ $Y$ の回文Bを繋げて回文ができるとき、AもBも周期 $\mathrm{gcd}(X, Y)$ を持ち、さらにその1周期は回文」である(証明は解説スライドを参照のこと)

　この条件が満たされるように $L_i - L_1$ たちのgcdを取っていけばこれが最小の周期となる。これが回文となるように選べる部分は2で割った切り上げ。先頭 $L_1$ 文字分自由に選べるのと合わせて、2をこれらの数の和で累乗したものが答えとなる。

反省

　48分13秒(2WA)でAC。いろいろ考察していたら(足の長さでソートしてuniqueを取ったとして)一番長い足について、一番短い足の分は任意に取れて、あとは残りの部分が $L_N - L_1$ 文字の回文かつ $L_N - L_2$ 文字の回文かつ $\dots$ かつ $L_N - L_{N - 1}$ の回文になればいいというところまではわかった。つまりだいたい $ans = 2^{L_0 + x}$ という形になっていて $x$ が特定できればいいと考えた。

　サンプルの3つ目をこの形で解くと $x = 5 \times 10^5$ になることがわかって、これはいかにも $10^6 / 2$ っぽい。そして $10^6$ というのは $L_i$ の差分の最小公倍数っぽいなーというのをエスパーして、あとはサンプル1,2も合うように奇数の場合は+1してから2で割るということをして(まぁ回文だしそれっぽい操作だと思った)適当に投げたらAC。完全に考察ではなくエスパーで解いてしまった。多分これはコンテスト後かなんかで一度解説を読んだことがある気がする。

　同じ文字列長のものがあったときの処理が不安でuniqueを取ってしまったが別にこれは必要なかったか。gcd(0, x) = xになるから問題ないんだな。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> L(N);
    for (ll i = 0; i < N; i++) {
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    L.erase(unique(L.begin(), L.end()), L.end());

    ll diff_gcd = L[1] - L[0];
    for (ll i = 2; i < L.size(); i++) {
        diff_gcd = gcd(diff_gcd, L[i] - L[i - 1]);
    }

    cout << MODpow(2, L[0]) * MODpow(2, (diff_gcd + 1) / 2) % MOD << endl;
}

2018-10-01

AtCoder Regular Contest 047 C - N!÷K番目の単語

競技プログラミング

問題

　 $N(\le 10^5)$ までの整数による順列は $N!$ 個あるが、それらを辞書順に並べたときの $K(\le N)$ 個目のものを求めよ。

解法

　先頭からどの数字を置くべきか決定していくが、それを「まだ使っていない数字の中で何番目に小さいものを置くべきか」を求めることによって決定していく。辞書順 $X$ 番目のものについて、たとえば1文字目は数字を決めると2番目以降は $(N - 1)!$ 通りあるため $\left\lfloor \frac{X}{(N - 1)!} \right\rfloor + 1$ を置けば良い。

　ここで $X = N! / K$ であるから、これを $(N - 1)!$ で割った商は $N \div K$ の商に等しく、余りは $N \% K / K \times (N - 1)!$ であるという性質がある。これにより2文字目を決定するときは余りの数を用いて $N \% K / K \times (N - 2)!$ と求められる。何を言っているのか理解できていないので解説スライドを参照のこと。

反省

　2時間54分(1WA)でAC。睡眠不足と体調不良でほとんどまともに考察できなかったが、とりあえず2時間を過ぎたあたりで解説スライドを見た。しかし何を言っているのか理解ができず、他の人の提出を見てほぼ写して通したという感じになった。最初の部分もわからないし、それを求めたあともBITを使って二分探索すればいいというのも出てこない考えだと思う。

　0-indexedによるズレが生じるのも面倒で、prev_permutationを使って戻す実装にしてみたところ、 $K = 1$ でWAが出るようだ。確かに手元でやってみるとそうなるんだけどさっぱりわからない。そこだけ場合分けしたらなんとか通った(これも他の人の提出で場合分けされていたのでやってみただけ)が、謎である。とにかく難しい問題だった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class BinaryIndexedTree {
public:
    BinaryIndexedTree(ll N) : N_(N), bit_(N + 1, 0) {}
    void add(ll a, ll w) {
        for (ll x = a; x <= N_; x += (x & -x)) {
            bit_[x] += w;
        }
    }
    ll sum(ll a) {
        ll result = 0;
        for (ll x = a; x > 0; x -= (x & -x)) {
            result += bit_[x];
        }
        return result;
    }
private:
    ll N_;
    vector<ll> bit_;
};

int main() {
    ll N, K;
    cin >> N >> K;

    if (K == 1) {
        for (ll i = N; i >= 1; i--) {
            cout << i << endl;
        }
        return 0;
    }

    //残っているものの中で何番目か
    vector<ll> f(N);

    //解説スライドにおける「整数」
    ll p = 1;

    //先頭から決定していく
    for (ll i = 0; i < N; i++) {
        f[i] = (N - i) * p / K + 1;
        p = (N - i) * p % K;
    }

    BinaryIndexedTree bit(N);
    for (ll i = 1; i <= N; i++) {
        bit.add(i, 1);
    }

    vector<ll> ans;
    for (ll i = 0; i < N; i++) {
        //bitの値を使って二分探索をする
        //残っているものの中でx番目の数字 <=> bit.sum(j) = xとなるj
        ll low = 0, eq_high = N;
        while (low + 1 != eq_high) {
            ll mid = (low + eq_high) / 2;
            (bit.sum(mid) < f[i] ? low = mid : eq_high = mid);
        }
        ans.push_back(eq_high);
        bit.add(eq_high, -1);
    }

    //求めたのは0-indexedのN!÷K番目なので1個戻す
    prev_permutation(ans.begin(), ans.end());

    for (ll a : ans) {
        cout << a << endl;
    }
}

2018-09-29

AtCoder Regular Contest 046 C - 合コン大作戦

競技プログラミング

問題

　 $N(\le 150,000)$ 人の男性と $M(\le150,000)$ 人の女性が合コンをした。男性は年収が $A_i$ 円であり、年収が $B_i$ 円以上の女性とカップルになりたいと考えている。女性もまた年収 $C_j$ と相手の年収 $D_j$ の希望を持っている。これらが同時に満たされるとカップルが成立するとき、最大のカップル数を求めよ。

解法

　男性と女性を混ぜて、男性は年収、女性は希望する相手の年収でソートし、小さい方から見ていく。今考えている人物が女性であれば年収をmultisetに突っ込んでいき、男性であればmultisetの中で希望年収以上であるものを一つ取り出す。この取り出す操作が可能であった回数が答えとなる。

反省

　1時間25分(3WA)でAC。40分を過ぎたあたりで男女を混ぜてそれぞれの値でソートすればいいということに気づいて実装して58分が過ぎたあたりで提出したがWA。自信があったのに取らなくて落胆してしまい、解説スライドを見た。解法は考えていたものと同じようなことが書かれていて、何が間違っているのかわからなくて結構悩んだ。

　一つにはまずmultisetではなくただのsetを使っていたというミスがあるのはわかったけれど、それを修正しても通らず。mapでやっている人が多かったのでそうしてみたがそれでも通らなかった。違う部分にミスがあると判断してコードを見直したところ、ソートするときに余計なものを考慮していたせいで順番がめちゃくちゃになってしまっていた。それを修正してAC。惜しいところまで行っていたので自力で通したかった……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;

    enum {
        //男が後になるようにソートされて欲しいのでこの順番
        FEMALE, MALE
    };
    struct Human {
        ll income, hope, sex;
    };
    vector<Human> humans(N + M);
    for (ll i = 0; i < N; i++) {
        cin >> humans[i].income >> humans[i].hope;
        humans[i].sex = MALE;
    }
    for (ll i = 0; i < M; i++) {
        cin >> humans[N + i].income >> humans[N + i].hope;
        humans[N + i].sex = FEMALE;
    }

    sort(humans.begin(), humans.end(), [&](Human& lhs, Human& rhs) {
        ll l1 = (lhs.sex == MALE ? lhs.income : lhs.hope);
        ll r1 = (rhs.sex == MALE ? rhs.income : rhs.hope);

        return (l1 == r1 ? lhs.sex < rhs.sex : l1 < r1);
    });
    
    ll ans = 0;
    multiset<ll> women_income;
    for (auto h : humans) {
        if (h.sex == MALE) {
            auto pair = women_income.lower_bound(h.hope);
            if (pair != women_income.end()) {
                ans++;
                women_income.erase(pair);
            }
        } else {
            women_income.insert(h.income);
        }
    }

    cout << ans << endl;
}

2018-09-28

SRM517 Div1 Easy - CompositeSmash

競技プログラミング

問題

　整数 $N$ をそれぞれ2以上である数字の積に分解する操作が行える。分解して得られる整数はランダムであるとするとき、整数 $target$ を作ることができるかどうか判定せよ。

解法

　気合を入れて場合分けをする。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class CompositeSmash {
public:
    string thePossible(int N, int target) {
        if (N % target != 0) {
            return "No";
        }
        if (N == target) {
            return "Yes";
        }
        auto target_factor = primeFactorization(target);
        if (target_factor.size() != 1) {
            return "No";
        }
        auto top = target_factor.front();
        if (top.second == 1) {
            //targetは素数
            return "Yes";
        } else if (top.second == 2) {
            //Nもtop.firstの累乗ならYes
            auto N_factor = primeFactorization(N);
            if (N_factor.size() == 1 && N_factor.front().first == top.first) {
                return "Yes";
            } else {
                return "No";
            }
        } else {
            return "No";
        }
    }
private:
    vector<pair<ll, ll>> primeFactorization(ll n) {
        vector<pair<ll, ll>> result;
        for (ll i = 2; i * i <= n; i++) {
            ll num = 0;
            while (n % i == 0) {
                n /= i;
                num++;
            }
            if (num != 0) {
                result.push_back({ i, num });
            }
        }

        if (n != 1) {
            result.push_back({ n, 1 });
        }

        return result;
    }
};

2018-09-28

SRM516 Div1 Easy - NetworkXOneTimePad

競技プログラミング

問題

　ciphertextsにある任意の数字が、plaintextsのどれかの数字にxorしたものに等しくなるようなキーの数を求めよ。

解法

　各暗号化済みの数字と暗号化前の数字のxorを取るとキーとなり得る数字を求められる。それの登場回数をmapで数えておく。キーとなる数が暗号化済みの数字数と同じ数だけ出てきたらそれはすべてに対してキーになっているということなので計算量は $O(NM\log{NM})$ でこの問題が解けた。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class NetworkXOneTimePad {
public:
    int crack(vector<string> plaintexts, vector<string> ciphertexts) {
        vector<ll> p(plaintexts.size()), c(ciphertexts.size());
        for (ll i = 0; i < plaintexts.size(); i++) {
            p[i] = toLL(plaintexts[i]);
        }

        map<ll, ll> num;
        for (ll i = 0; i < ciphertexts.size(); i++) {
            c[i] = toLL(ciphertexts[i]);
            for (ll j = 0; j < plaintexts.size(); j++) {
                num[c[i] ^ p[j]]++;
            }
        }

        ll ans = 0;
        for (auto p : num) {
            if (p.second == ciphertexts.size()) {
                ans++;
            }
        }

        return ans;
    }
private:
    ll toLL(string binary) {
        ll result = 0;
        for (ll i = 0; i < binary.size(); i++) {
            if (binary[i] == '1') {
                result |= (1LL << (binary.size() - i - 1));
            }
        }
        return result;
    }
};