Joeの精進記録

旧：競プロ練習記録

Codeforces Round #511 (Div. 2)

Codeforces

ABC早解きで123位でした。DはHack中にミスに気づいて厳しい気持ちになってました

Div. 1との同時開催だったので普段より強い（早い？）人が少なくて、A, Bを解き終えた時点でほぼトップだったのでびっくりしてました

C - Enlarge GCD

まず制限時間1秒を見て驚く。さすがに、 O(n\log^2 n)より速くなる気がしないので、愚直に実装することにする。

アルゴリズム自体はすぐに思いついた。すべてのgcdで各項を割った状態で考える。 このとき、各素数2, 3, 5, ...について、その倍数がいくつあるかをカウントする。一番倍数の数が多かった素数の倍数を残すように残りの数を削除する。

最悪ケースを考えると、どうせ各素数について調べる必要がありそうだから、事前に1.5e7以下の素数を列挙して、それらすべてについて調べるというので良さそう。

念のためcin.tie(0); ios::sync_with_stdio(0);しておきましたが、実行時間を見るに本当にしておいてよかった気がします。

以下コード。エラトステネスの篩部分（つまりis_primeとprimesの構築）は省略してます。

constexpr int MAX_A = 15000000;
int is_prime[MAX_A];
vi primes;
int a[MAX_A + 1];

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vi as(n);
    i64 g;
    for (int i = 0; i < n; i++) {
        cin >> as[i];
        if (i == 0) {
            g = as[i];
        } else {
            g = gcd(g, as[i]);
        }
    }
    
    for (int i = 0; i < n; i++) {
        as[i] /= g;
    }
    
    int max_c = -1;
    for (int i: as) {
        a[i]++;
    }
    for (int i = 0; i < primes.size(); i++) {
        int p = primes[i];
        int c = 0;
        for (int j = 1; p * j <= MAX_A; j++) {
            if (a[p * j]) {
                c += a[p * j];
            }
        }
        max_c = max(max_c, c);
    }
    int ans = n - max_c;
    cout << (ans == n ? -1 : ans) << endl;
}

D - Little C Loves 3 II

Cを解き終えた時点で正解者が1人だったので、最悪解けなくてもいいかなぁ〜と思っていたのですが、WAを生成しているうちに100人とかまで増えてきてすごく焦りました。

まず最初、3xmを手で試しました。このとき、頭がついていなくて、3x4のときに敷き詰められないと結論づけてしまったことがすごくあとに響きました。 二部グラフの最大マッチングのライブラリでも使って検証するべきでした、、、

n, mが4以上の偶数のときに敷き詰められることはわりと序盤で気づけたのですが、問題は奇数x偶数のときでした。2x5が敷き詰められることや3x4が敷き詰められることに気づいた頃には終了10分前ぐらいになっていて、pretestを通すことはできましたが、細かいミスで落ちてしまいました、、、

証明

と、まあコンテスト中の試行錯誤はともかく、記事的に重要なのはおそらく証明だと思うので、証明を載せておきます。

以下、 n \le mとします。

n = 1のとき

貪欲に敷き詰めるしかないです。すなわち、abcabcdefdef...のように敷き詰めます。空きマスは 1,2,3,2,1,0,1,2,3,2,1,0,1,\ldotsのように変化していきます。

nまたは mが6の倍数のとき

1x6をabcabcのように敷き詰められるため空きマスを0にすることができます。

n = 2のとき

m \le 2のときは何も置けません。

m = 3のとき、試すと空きマスを2つまで少なくすることができることがわかります。

m = 4のとき

abcd
cdab

のように置くことで、空きマスを0にすることができます。

m = 5のとき

abceb
deadc

のように置くことで、空きマスを0にすることができます。

m = 6のとき6の倍数なので空きマスをなくせます。

m = 7のとき、これが無理になることは手でめっちゃ試すとわかります。雑ですみません。

m \ge 8のとき、8以上の整数は、これまでに空きマスを0にすることができるような mをいくつか選んで足すと作れるため、空きマスを0にすることができます。

以下は n \ge 3の場合です

n, mがどちらも偶数の場合

2x(4以上の偶数)が可能だったことにより空きマスを0にすることができます。

nが奇数、 mが偶数の場合

いま n \ge 3より m \ge 4です。3x4を以下のように構成できることがこの場合の証明ですごく重要です。2x4が構成できることより、nx4がすべて構成できることがわかります。さらに、nx6が構成可能なことと、8以上の偶数が4の倍数と6の倍数を足し合わせて作れることから、nxmすべてが可能なことがわかります。

acdb
ebaf
cfed

nが偶数、 mが奇数の場合

n = 2の場合は調べたので、 n \ge 4です。そうすると m \ge 5です。これは nが奇数、 mが偶数の場合の結果を使うと、同様にすべて可能であることがわかります。

nが奇数、 mが奇数の場合

いよいよ最後です。 これは正直あまりきれいな証明が思いつきませんでした。

n = 3の場合に

abd
d c
cab
***bc
*a* a
***cb
*****bc
***a* a
*****cb

のように空きマスを1にするように構成していけることがわかります（図では、それまでに敷き詰められた部分を*で表しています）。

n \ge 5のとき、2xmで敷き詰められるようなm対して、nxmは、3xmと(n - 3)xmを組み合わせることで、空きマスを1にできることがわかります。

さて、これを満たさないmは今の条件下では m = 7だけです。しかし、4xnが構成可能であることは証明済みですから、nx7をnx4とnx3に分解することで、空きマスを1にすることが証明できます。

さて、これですべての場合が証明できました。いや〜つかれた。

以下実装

int main() {
    i64 n, m;
    cin >> n >> m;
    if (n > m) {
        swap(n, m);
    }
    
    i64 ans;
    if (n == 1) {
        int rem[] = {1,2,3,2,1,0};
        ans = n * m - rem[(m - 1) % 6];
    } else if (n == 2) {
        if (m <= 2) {
            ans = 0;
        } else if (m == 3 || m == 7) {
            ans = n * m - 2;
        } else {
            ans = n * m;
        }
    } else if (n % 2 && m % 2) {
        ans = n * m - 1;
    } else {
        ans = n * m;
    }
    cout << ans << endl;
}

感想

小さいケースは手でやるより最大マッチングのライブラリを使うべきですね、、、、、、、、ほんとに

C - Chokutter

AtCoder

C - Chokutter

かなり古い企業コンの問題です。点数はついていませんが、感覚では500ぐらいかなと思います。

問題概要

2 \le n \le 100000頂点のグラフが与えられます。はじめグラフには辺がまったく張られていません。 0 \le m \le 100000個のクエリが与えられます。クエリには以下の3種類があります。

  1. tweet u: 頂点 uおよび隣接する頂点のポイントを1増やす
  2. follow u, v: 辺 (u, v)を張る
  3. unfollow u, v: 辺 (u, v)を削除する

m個のクエリを処理した後、それぞれの頂点のポイントを答えよ。

解説

誤読防止のためにあえて書いておきますが、タイプ1のクエリでは、連結成分に+1するのではなくて 自分自身および隣接する頂点を対象とします。

クエリ1がくるたびに毎回隣接する頂点を列挙してインクリメントしていくのは O(nm)かかり間に合いません。 unfollowするときに差分を一気に更新するようなアルゴリズムを考えます（与えられたすべてのクエリを処理し終わった後、 今張られている辺をすべて削除するまでunfollowを繰り返すようなクエリを追加したとしても答えは変わりません）。

さて、unfollow u, vされたとしましょう。このとき、いつかにfollow u, vが呼ばれたわけですが、 そのときの vのポイントをhogeとします。unfollowまでにhogeがhoge+nになったとすると、unfollow時に uのポイントをn増やせばいいですね。

これをするには、実はどのタイミングで (u, v)の辺が張られたかなどを記録せずとも、 followされた瞬間に uのポイントを-hogeし、unfollowされた瞬間に（その瞬間の vのポイント、すなわちhoge+n）を 加えればいいです。

実装

原題は、 k番目に多いポイントを答えよ、という問題だったので最後に結果をソートしてます。

int tw[101010];
int dif[101010];
set<ii> edges;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        char c;
        cin >> c;
        if (c == 't') {
            int u;
            cin >> u;
            tw[u]++;
            dif[u]++;
        } else if (c == 'f') {
            int u, v;
            cin >> u >> v;
            edges.insert(ii(min(u, v), max(u, v)));
            tw[u] -= dif[v];
            tw[v] -= dif[u];
        } else {
            int u, v;
            cin >> u >> v;
            edges.erase(ii(min(u, v), max(u, v)));
            tw[u] += dif[v];
            tw[v] += dif[u];
        }
    }
    for (ii edge: edges) {
        int u = edge.first, v = edge.second;
        tw[u] += dif[v];
        tw[v] += dif[u];
    }
    vi ans;
    for (int i = 1; i <= n; i++) {
        ans.push_back(tw[i]);
    }
    sort(ans.begin(), ans.end(), greater<>());
    cout << ans[k - 1] << endl;
}

感想

隣接する頂点ではなく連結成分にポイントを加えるんだったらどうするんだろう

J - Prime Routing

AtCoder

JAG Camp 2018 Day 3の問題

J - Prime Routing

問題の本質を抽出すると次のようになります。

問題

連結で単純な無向グラフが与えられる。頂点Sから頂点Tに向かう奇数長の最短路の長さはいくらか（辺の長さはすべて1）。存在しない場合は-1を出力せよ。

こんなことを考えてハマってしまいました

  • もともと最短路が奇数長ならそれでおｋ
  • 最短路が偶数長だったら、ちょっと遠回りして奇数長にしなきゃいけない
  • 二部グラフだったらどう頑張っても偶数長。そうでなければ可能
  • 二部グラフじゃないとして、どうやって最短の奇数長を得るか？
  • 二部グラフじゃないなら奇数長のサイクルを含むので、それを見つける？見つけたところで最短の奇数長路をさがすのは難しそう？

解答

各頂点 vを v_0, v_1の２つに増やした、頂点数が２倍のグラフを考えます。このとき、元のグラフで a, b間に辺があるとき、 新しいグラフで a_0, b_1間および a_1, b_0間に辺を張ります。このとき、スタートを s, ゴールを tとして s_0, t_1間の最短距離がスタートからゴールまでの最短の奇数長の路になります。

頂点 aについて、 a_0がスタートから偶数長でたどり着ける頂点、 a_1がスタートから奇数長でたどり着ける頂点だと考えると 納得できると思います。

一般化

今回の問題では奇数長か偶数長かに注目すればいいですが、一般に kの倍数長の最短路を考えるならば、頂点の数を k倍に増やしたような グラフを考えればいいことがわかります。元のグラフの辺 (a, b)に対応して、新しいグラフで k本の辺 (a_0, b_{k - 1}), \ldots, (a_i, a_{(i + 1) \% k}), \ldotsを張ってあげればいいですね。

E - Self-contained

AtCoder

原題はE - Self-containedですが、問題の本質は以下のとおりです。

問題

0以上 n \ (0 \lt n \le 500000)未満の整数からなる集合が与えられる。この中の相異なる3要素 (a, b, c)で、 a + b = cとなるものはあるか。

知識

今回は要素の大きさに制限がありますが、制限がない場合、 O(n^2)のアルゴリズムが限界だと思われているようです。2018年度の東京大学情報理工学系研究科コンピュータ科学専攻の院試に似たような話がありました。

解法

まず、話をわかりやすくするために配列 a[500000]を定義します。 a[i]は整数 iが集合に含まれるとき1, そうでないとき0とします。

さて、集合の中の相異なる2要素 a, bを考えたときに、これらの和は999999未満となりますね。

では、和が mとなるような a, bの組み合わせを考えてみましょう。

そのような組み合わせが存在するとしたら、 (a, b)は (0, m), (1, m - 1), \ldots, (m, 0)のいずれかとなっているはずです。

そこで \sum_{i = 0}^m a[i]a[m - i]を考えます。

もしも (0, m), (1, m - 1), \ldots, (m, 0)の組み合わせの中で、実際に集合の要素で構築可能なものがあったとしたら \sum_{i = 0}^m a[i]a[m - i]は1以上になります。逆にそのようなものがなかったとしたらsumのすべての項は0となります。

すでにピンときた方は多いでしょうが、これは離散フーリエ変換そのものです。 具体的には a[500000]と a[500000]を畳み込んで得られる長さ 999999の配列のうち、前 500000個を新たに b[500000]と呼ぶことにすると、 a[500000], b[500000]のelementwise ANDがすべて0ならば、問題の条件を満たすtripletが存在しなく、1以上になるものがあれば存在します。

このアルゴリズムの計算量は O(n\log n)です。

Codeforces Round #510 (Div. 2)

595位でした。前日に比べればかなりマシですが、AとCをHackされ、 さらにEよりCを優先したためさほど難しくないEを捨ててしまうという散々な結果でした。

追記）Eやっぱむずかったです。じゃあまあいつも通りの結果という感じですかね

C - Array Product

0の個数と負の個数に注目して場合分けするだけだと思うんですが、、、(6WA)

D - Petya and Array

セグ木を使って、配列にあるhoge以下の要素を O((\log n)^2)で数えるやつを使います。これは非常に便利でライブラリ化していたので貼るだけでほぼ終了しました（1800点とれました！）。

具体的には累積和をとり、 l, rの lを固定したときに、右はしまでに t + \textrm{sum}[l - 1]未満の要素( r)がいくつあるかカウントすればいいですね。

Codeforces Round #509 (Div. 2)

Codeforces

散々な成績でした。C, 正解者数的にも絶対シンプルなアルゴリズムがあるのに思考を切り替えられなかったです。

codeforces.com

C - Coffee Break

1日目には、 a_iが最小なものから、差を dより大きくして、選べるだけ選びます。選んだものはその都度、setから削除します。 2日目には、残った要素のなかから、同様に差を dより大きくして選べるだけ選びます。 これを繰り返すとできるのですが、set.upper_boundが O(\log n)で動くことを知らなかったため、自らAVL木を実装する羽目に、、、

後日、気合のACです。

Submission #42969399 - Codeforces

冷静に、想定解なわけがなく、 a_iが小さい順に見ていったとき、追加できる日付を順に割り当ててやるとよいです。各日付にすでに割り当てられている最大の a_iを保存しておくだけでいいですね（それが最小な日付に追加すればいいです）。

D - Glider

各上昇気流のスタートから飛び始めるときの答えをそれぞれ計算し、その最大値を取ります。

次以降に通過する各上昇気流のスタートまでにどれだけ下降するかは累積和を用いると O(1)で求められ、さらに着地するまでにどこまで進めるかは二分探索で O(\log n)で求められます。

合わせて O(n\log n)で解けました。

No.732 3PrimeCounting

yukicoder

問題

N \ (5 \le N \le 100000)以下の相異なる3つの素数の組 (a, b, c) \ (2 \le a \lt b \lt c \le N)のうち、 a + b + cが素数になるものはいくつあるか。

No.732 3PrimeCounting - yukicoder

解法

100000以下の素数の個数は10000個ぐらいなので、 O(\pi(N)^2)で間に合う。ただし \pi(N)は N以下の素数の個数。この問題の場合、自明な O(\pi(N)^3)解が10分ぐらい待てば動くので、答えを埋め込むのも手ですが、ここでは正攻法を解説します。

triplet系の問題は一つ固定して考えるのがあまりに定石ですが、今回は cと a + b + cを固定します。このとき、 cより小さい素数の組 a, bで和がhogeになるものが何通りあるかを、あらゆるhogeについてすぐに答えられるといいです。

これを求めるのには、（ cに関するforループ内で） a, bに関する2重ループを回して可能な和をすべて調べればできますが、合わせて3重ループになるのでTLEしてしまいます。しかし、数え上げに注目すると、 cが次のものに変わるとき、ひとつ前に数えたものはすべて重複して数えられています。 cが次のものに変わるとき、新しくカウントされる組み合わせは b = (\textrm{previous} \ c)となっているものに限られることに注目すると、オーダーが一つ落ち、間に合います。

実装

エラトステネスの篩の部分は省略しています。

bool is_prime[303030];
int cnt[303030];
vi primes;

int main() {
    init();
    int n;
    cin >> n;
    i64 ans = 0;
    for (int i = 1; i < primes.size(); i++) {
        int c = primes[i];
        if (c > n) break;
        int b = primes[i - 1];
        for (int j = 0; j < i - 1; j++) {
            int a = primes[j];
            cnt[a + b]++;
        }
        for (int j = 0; j < primes.size(); j++) {
            int sum = primes[j];
            if (sum - c >= 0) {
                ans += cnt[sum - c];
            }
        }
    }
    cout << ans << endl;
}

感想

大小関係があるtripletの数え上げは、今回のように一番大きいものを固定すると差分だけを数えられるようになってオーダーが落ちますね。典型か？