2018-09-26

D - Factorization

AtCoder

D - Factorization

長さ $n$ の正整数の配列で、各要素の積が正整数 $m$ となるようなものが何通りなるか、という問題。

解法

$m$ の素因数分解を考え、 $m = p_1^{a_1}\ldots p_k^{a_k}$ とします。今の問題は次のように言い換えることができます。

$n$ 個の箱があり、 $a_i$ 個の $p_i$ を重複を許して入れます。それぞれの $p_i \ (1 \le i \le k)$ についてこの作業をする場合の、入れ方の場合の数はいくらか。

この言い換えが問題の本質です。たとえば $n = 3, m = 8$ としたときに[1,1,8]も[1,2,4]も[2,2,2]も全部今の方法でもれなく数え上げられていることを確認してみてください。

このときの場合の数は、 $i$ について独立に考えることができます。そこで以下の問題を考えます。

$n$ 個の箱があり、 $a$ 個の $p$ を重複を許して入れる場合の数はいくらか。

これは重複組合せの計算であり、 $dp[i][j] = i$ 番目までのアイテムから $j$ 個重複を許して入れる場合の数、とした動的計画法を考えることで解けます。

2018-09-26

F. The Shortest Statement

Codeforces

F - The Shortest Statement

問題概要

$1 \le n \le 10^5$ 頂点 $m \ (m - n \le 20)$ 辺の連結な重み付き無向グラフが与えられる。 $(1 \le q \le 10^5)$ 個のクエリに答えよ。 $i$ 番目のクエリでは頂点 $u_i, v_i$ 間の最短距離を答えよ。

考えたこと

木っぽいグラフが与えられるということなので、とりあえず木に場合について考えてみることにする。木の場合はまんまLCAを使うことができます。具体的には

適当な1頂点を根として、根付き木を考える。この根から各頂点への最短距離をbfsでもして求めておく。
$u_i, v_i$ に対して、これらのLCAを $O(\log n)$ で求め、それを $w_i$ とおく。
$u_i, v_i$ 間の最短距離は、 $d[u_i] - d[w_i] + d[v_i] - d[w_i]$ である。

次はこれをいまのグラフに拡張してみましょう。グラフから適切に辺を $k = m - n + 1$ 本削除すると木になります。削除された辺につながっている頂点の集合を $V$ とします。

元のグラフ上での2頂点間の最短経路はもちろん削除された辺を通る場合があります。そこで、削除された辺も含めた $V$ の中の任意の2頂点間の距離をワーシャルフロイドで事前計算しておきます。

このとき、 $u_i, v_i$ 間の最短距離は次のように計算することができます。

最短距離を木上での最短距離で初期化します。
$u_i$ から木上を通って $w_j \in V$ までいき、そこから $w_k \in V$ に抜けて、 $w_k$ から木上を通って $v_i$ に行く経路をすべての $j, k$ の組み合わせについて計算し、最短距離を更新する

定数倍が重めですが、 $O(q\log n)$ でこの問題を解くことができました。

2018-09-26

Codeforces Round #512

Codeforces

CでWAを引きすぎて飛ばしてしまい、Dから解いたので574位になってしまいました、、、

C - Vasya and Golden Ticket

0を除いて考えても同じなのではじめに0を除去しておきます。除去後の文字列が空列なら、これは"0...0"という入力に対する場合であり、"YES"を返します。

そうでない場合、 $i$ 番目の桁までの桁和（累積和）をとり、 $S[i]$ とします。1ブロックの桁和としてありえるのは、 $S[1], S[2], \ldots, S[n - 1]$ なので、それぞれに対し可能かどうか判定していきます。なお、ここでの文字列の長さ、 $n$ はトリミング後の長さとします。

可能かどうかの判定は左から貪欲に見ていけばいいです。事前に0を削除しておかないと、貪欲で判定していくときに、可能な最長の部分列を見たり、特別処理をしたりする必要が出てきて多少バグらせやすくなると思います。

たとえば、"1100000"は、明らかに可能ですが、"1" + "1" + "00..."に分けようとするとダメで、"1" + "100..."に分けないとだめです。もしくは最後に"00.."が続いた場合は特別処理するとかしないとダメですね。

D - Vasya and Triangle

1以上の整数 $n, m$ と整数 $k$ が与えられるので、長方形 $(0, 0), (n, 0), (0, m), (n, m)$ に収まっているような格子点3点からなる三角形で面積が $\frac{nm}{k}$ となるものを一つ構成せよ、という問題

考えたことと解法

格子点からなる三角形の面積が0.5刻みであることは知っていたので、とりあえず、 $\frac{nm}{k}$ が半整数じゃない場合は"NO"を返して、半整数の場合にどうなるかを考えました。

いくつか試してみると、作れるなあという気分になって構成を試みます（後述しますが、長方形内に収まる三角形の面積は、実は0.5から $\frac{nm}{2}$ までの0.5刻みのものがすべて構築可能です。）。

面積が半整数となる場合を考えましょう。このとき $2S = \frac{2nm}{k}$ は整数です。

うまく約分するとこれが整数になることから、 $k = k_1k_2$ となるような1以上の整数 $k_1, k_2$ が存在し、これらを使って2整数 $a, b$ を $a = \frac{2n}{k_1}, b = \frac{m}{k_2}$ または $a = \frac{n}{k_1}, b = \frac{2m}{k_2}$ となるように作ることができます。このどちらかは、 $a, b$ がそれぞれ $n, m$ 以下になっているはずです $\max(k_1, k_2) \ge 2$ なので）。よって3点 $(0, 0), (a, 0), (0, b)$ を選べば、面積が $\frac{ab}{2} = 2S / 2 = S$ の面積が得られます。

$k_1$ としては、 $nとk$ のgcdを考えればいいですね。

もっと良い方法

いま、面積が $k \ (1 \le 2k \le nm)$ となるような面積の三角形を構成することを考えます。三点、 $(0, 0), (x_1, y_1), (x_2, y_2)$ からなる三角形の面積が、 $\frac{1}{2}|x_1y_2 - x_2 y_1|$ となることを用います。いま、とりあえず絶対値の中身が正になる場合を考えると、 $2k = x_1y_2 - x_2 y_1$ です。このとき、 $x_1$ を $n$ に固定し、 $y_2 = \lceil \frac{2k}{n}\rceil$ として、残りの項で、面積を調整することを考えます。このとき、 $x_2y_1 \lt n$ となります。さて、ここまで来ると $y_1 = 1, x_2 = 2k - x_1y_2$ とすればいいことがわかります。

こうして構築した、 $(x_1, y_1), (x_2, y_2)$ が長方形内に入っていることを確認してみましょう。 $x_1, y_1$ は明らかに大丈夫ですね。 $y_2$ は $2k \le nm$ であることから $m$ 以下です。いま、 $x_2y_1 \lt n$ ですから $x_2 \lt n$ が示せ、結局三角形が長方形に収まっていることがわかりました。

E - Vasya and Good Sequences

考えたこと

popcountが同じ数字は作ることができるので、数字そのものは重要ではなく、数字のpopcountのみが重要です。そこで、 $a_1, \ldots, a_n$ の代わりに、対応する要素のpopcountの配列 $p_1, \ldots, p_n$ を考えることにします。連続部分列 $a_l, \ldots, a_r$ がGood Sequenceになる必要十分条件は、それに含まれる $p_i$ の和が偶数で、かつ、そのうち最大の $p_i$ を $p_m$ として $p_l + \ldots + p_r \ge 2p_m$ が成り立つことです。

これをセグ木でも使って高速に数え上げるんだろう、と考えましたがお手上げでした。実は、問題文の条件にあった $a_i \ge 1$ という条件が本質でした。

まず、popcountの和が偶数になる条件を考えましょう。これのみを満たす連続部分列を数えることは、累積和などを使うことによって簡単にできるので省略します。

2つ目の条件 $p_l + \ldots + p_r \ge 2p_m$ が成り立たないようなものを数え上げることにしましょう。これが成り立たないのは $p_l + \ldots + p_r \lt 2p_m$ の場合ですが、 $2p_m$ が高々30程度で、 $p_i \ge 1$ であることに注目すると、連続部分列の長さは長くても30程度です。なので、それぞれの $p_i$ を $p_m$ とした場合を考え、数え上げれば大丈夫です。こうしてこの問題が $O(n)$ で解けました。

2018-09-22

Educational Codeforces Round 51

Codeforces

ABCD解いて443位でした。可もなく不可もなくといった感じ。Fの解法がめっちゃ気になっているので別記事にします。

C - Vasya and Multisets

1回だけ現れる要素が偶数種類だったら同じ種類ずつ振り分けて、複数回現れる要素を片方にまとめる。

1回だけ現れる要素の種類が奇数だったら3回以上の現れるものから1個だけもらってきて、残りは↑と同様に振り分ける。

D - Bicolorings

$dp[i][j][k] = i$ 列まで見て、 $j$ 個のcomponentがあって右端がBB/BW/WB/WW

int main() {
    i64 n, K;
    cin >> n >> K;
    
    if (n == 1) {
        cout << 2 << endl;
        return 0;
    }
    
    vvvi dp(n + 1, vvi(2 * n + 1, vi(4)));
    dp[1][1][0] = 1;
    dp[1][1][3] = 1;
    dp[1][2][1] = 1;
    dp[1][2][2] = 1;
    
    for (int i = 1; i < n; i++) {
        for (int k = 1; k <= 2 * n; k++) {
            dp[i + 1][k][0] = dp[i][k][0] + dp[i][k][1] + dp[i][k][2] + dp[i][k - 1][3];
            dp[i + 1][k][0] %= MOD;
            dp[i + 1][k][3] = dp[i][k - 1][0] + dp[i][k][1] + dp[i][k][2] + dp[i][k][3];
            dp[i + 1][k][3] %= MOD;
            if (k >= 2) {
                dp[i + 1][k][1] = dp[i][k - 1][0] + dp[i][k][1] + dp[i][k - 2][2] + dp[i][k - 1][3];
                dp[i + 1][k][1] %= MOD;
                dp[i + 1][k][2] = dp[i][k - 1][0] + dp[i][k - 2][1] + dp[i][k][2] + dp[i][k - 1][3];
                dp[i + 1][k][2] %= MOD;
            }
        }
    }
    
    i64 ans = (dp[n][K][0] + dp[n][K][1] + dp[n][K][2] + dp[n][K][3]) % MOD;
    cout << ans << endl;
}

2018-09-22

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;
}

感想

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

2018-09-20

C - Chokutter

AtCoder

C - Chokutter

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

問題概要

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

tweet $u$ : 頂点 $u$ および隣接する頂点のポイントを1増やす
follow $u, v$ : 辺 $(u, v)$ を張る
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;
}

感想

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

2018-09-19

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$ を張ってあげればいいですね。

D - Factorization

解法

F - The Shortest Statement

問題概要

考えたこと

C - Vasya and Golden Ticket

D - Vasya and Triangle

考えたことと解法

もっと良い方法

E - Vasya and Good Sequences

考えたこと

C - Vasya and Multisets

D - Bicolorings

C - Enlarge GCD

D - Little C Loves 3 II

証明

のとき

またはが6の倍数のとき

のとき

がどちらも偶数の場合

が奇数、が偶数の場合

が偶数、が奇数の場合

が奇数、が奇数の場合

感想

問題概要

解説

実装

感想

問題

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

解答

一般化

$n = 1$ のとき

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

$n = 2$ のとき

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

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

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

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