2018-10-08

Hello Barcelona Day4

その他コンテスト

Day3はLink-Cut木コンテストだったんですが、むずすぎたのでもうちょっと理解してから記事にしようと思います。 Day4はstereometry（空間の幾何？）コンテスト

A - Elementary

問題

4点与えられるのでそれらを頂点とする四面体の体積を求めて、という問題

解法

三重積を計算して6で割るだけ

B - Cross Spider

問題

$1 \le n \le 100000$ 点が与えられるので同一平面上にあるか判定せよ。XYZ座標はそれぞれ絶対値が1000000以下。

解法

座標が大きく、内積や外積の演算をするとdoubleでは誤差が心配（ギリギリいけそうだけど）なのでlong longで計算する。平面の法線ベクトルが確定したらあとはそれと直交するかをみればいいだけ。

C - Line Teleportation

@kenshinが知らない間に通してた。

D - Segment Distance in 3D

この前まとめました。

xuzijian629.hatenablog.com

E - 3D Printing

問題

30面程度の凸な多面体が与えられるので体積を求めよ、という問題

解法

@oginginが通してくれた。

H - Connected Rings

リングが2つ与えられるので、鎖状につながっているか判定せよ。リング同士が交点をもつことはない。

解法

@kenshinが気合で座標計算し、通してくれた。プロすぎる。

感想

この日は自明問題しか貢献できなくて厳しい気持ちになった。

2018-10-08

Hello Barcelona Day2

その他コンテスト

Day1の内容はJAG合宿Day3と全く同じだったようです。なので記事はDay2からにしようと思います。

beta.atcoder.jp

A - Alice and Maze

問題

$n$ 頂点 $m$ 辺の無向グラフが与えられる。各頂点に報酬、各辺にコストが設定されている。頂点を訪れるたび、その報酬が貰え、辺を通るには、そのコストを支払わなければならない。スタートは頂点1でゴールは頂点 $n$ とする。Aliceはスタート時点で $k$ 円持っており、お金を最大化した後ゴールから出たい。スタートとゴールの頂点を含め、同じ頂点や辺は複数回通ってもよい。そもそもゴールにたどり着けない場合は-2, いくらでもお金を増やせる場合は-1, 有限のお金まで増やせる場合は、その金額を出力せよ。

制約

4秒
10テストケース
$2 \le n \le 1000$
$2 \le m \le 100000$
初期のお金、報酬、コストはそれぞれ1円以上 $10^7$ 円以下

解法

問題は無向グラフで与えられているが、進む方向によって実質かかる費用は異なるので、辺数を2倍にした有向グラフで考える。ベルマンフォードをやるだけだが、更新時に、現在の所持金が辺のコスト以上かどうかをチェックし、その場合のみ更新するようにする。

さらに無限大に発散するループが存在する場合、 $n$ （頂点数）回目のループで更新された頂点を列挙し、これらのうち1つ以上がゴールから到達可能な場合、いくらでも所持金を多くしてゴールに到達可能であることがわかる。

計算量はベルマンフォードは本質で $O(nm)$ かなりギリギリ（テストケースを考慮すると $10^9$ オーダーだし）だけど想定解だった。最初、無限ループ検出のときに、 $n$ 回目のループだけではなく、 $n$ から $2n$ 回目までのループで更新された頂点を全列挙していたが、この場合TLEした。 @oginginがそれ $n$ 回目だけでよくね？と言ってくれてプロだった。

B - Buggy Stack Machine

問題

PUSH, POP, ADD, EMPTYの命令（ADDは、上2つPOPし、それらをADDしたものをPUSHする命令）があるスタックがあるが、上からk個の数の2進数での1の位を並べたものが $b_1b_2\ldots b_k$ となった瞬間、これらk個の数がすべて消えてしまう、というバグを持っている。クエリが与えられるので、それぞれのPOPクエリに対して、POPされる値を答えよ。しかし、それまでに不可能な操作（たとえば空のスタックに対するPOPや、要素が1以下のスタックに対するADD）が呼ばれた場合には、ERRORを答えよ。

制約

5秒
50テストケース
クエリの数は100000以下
$1 \le k \le 10000$
入力文字列は60 mebibytes以下

解法

@kenshinが最初これを担当していて、bitsetを使って1の位を覚えておくのは間に合う？と聞いてきた。見積もってみるとかなりギリギリだったけど、まあいけそうかなと言って実装する。 C++の標準のbitsetでは、大きさが異なるbitset同士を比較できないのでかなり困った。大きい方のbitsetに合わせてコンストラクトし直して比較するとTLEするので（定数倍で10倍かかる）、頑張って比較を実装する。@kenshinが終了間際にWAで苦しんでいたのでソースコードを読んでみると、if (s.size() - (9999 - j) >= 0)というヤバそうな部分を見つける。intにキャストしたらACした。残り4分だった。

感想

さすがに想定解じゃなかった。他チームでもbitsetで書いたところが多かったみたいだが、ほとんどがTLEしてたらしい。想定解はKMP法だったが、チームメイトは誰もKMP法を実装したことがなかったのでかなり厳しかった。

C - Constellation

読んでない。@oginginが知らない間に通してた。

D - Domination

読んでない。 @kenshinが知らない間に通してた。

E - Elevator

問題

202階のビルがあってエレベーターに $n$ 人が1階から乗る。それぞれの人には行きたい階があるが、ちょうどその階に止まらなくても、1階分だけなら階段を使って下に降りることができる。エレベーターは1階を除いて最小でいくつの階に止まるか。

制約

1秒
100テストケース
$1 \le n \le 10000$

解法

貪欲にやるだけ。202階が謎制約すぎる。

G - Good Substring

問題

ある文字列がgoodであるとは、そのいかなる部分文字列も長さ2以上の回文を含まないことである。文字列と、クエリ（ $i$ 番目の文字を $c$ に変えるというもの）が与えられるので、各クエリ後の最長のgoodな部分文字列の長さを答えよ。

制約

2秒
1テストケース
文字列の長さ、クエリの数ともに $10^5$ 以下

解法

ある文字列が部分文字列に回文を含む必要十分条件はaaもしくはaba型の部分文字列を含むこと（お　な　じ　み）なので、クエリのたびに、この位置を更新し、これらの位置の間隔で最長のものを答えればいい。問題を言われてhoge秒で解法がわかったが、コンテスト中に読んでなかったので通せなかった。本当にもったいない

2018-09-26

蟻本リーディング組み合わせ編

蟻本

飛行機の移動が暇なので蟻本を読んでまとめることにしました。

今回は組み合わせ問題編です。

分割数

問題

$1 \le n \le 1000$ 個の互いに区別できない品物を $1 \le m \le n$ 個以下に分割する方法の場合の数を $2 \le mod \le 10000$ で割ったあまりを求めよ。たとえば、4つの品物を(1, 1, 2)と分割するのと(1, 2, 1)と分割するのは同じ分割だと数えます。

解法

mod素数の場合、combinationが $O(1)$ で求められることにより、事前計算も込みで $O(n + m)$ で解くことができます。 modが素数でない場合は、コンビネーション計算時に逆元が求まらないので、DPをします。

$dp[i][j] = i$ 番目までの品物をちょうど $j$ 個に分割する分割数とします。

ちょうど $j$ 個に分割する方法は、 $i - 1$ 番目までの品物が $j - 1$ 個に分割されていて $i$ 番目の品物を別の1グループとする場合と、 $i - 1$ 番目までの品物が $j$ グループに分割されていて、i番目の品物をどれかに追加する、という場合になります。

したがって、 $dp[i][j] = dp[i][j - 1] + dp[i - 1][j]$ となります。こうして $O(nm)$ でこの問題が解けました。

重複組合せ

$(1 \le n \le 1000)$ 種類の品物があり、 $i$ 番目の品物は $1 \le a_i \le 1000$ 個あります。異なる種類の品物は区別できますが、同じ種類の品物は区別できません。これらの品物の中から $1 \le m \le 1000$ 個選ぶ組み合わせの総数を $1 \le mod \le 10000$ で割った値を答えなさい。

解法

$dp[i][j] = i$ 種類目までから $j$ 個選ぶ組み合わせというDPを考えます。この数え上げを、 $i$ 種類目のものを選ぶ場合とそうでない場合に分けて考えます。 $i$ 種類目のものを選ばない場合は $dp[i - 1][j]$ 通りですね。 $i$ 種類目のものを1つ以上選ぶ場合、 $dp[i - 1][j - 1] + dp[i - 1][j - 2] + \ldots + dp[i - 1][max(0, j - a[i])]$ 通りです。これは累積和を同時に求めながら計算すると $O(nm)$ で計算できます（蟻本にはp.67にはこれを上手く変形して累積和なしで計算する方法も載ってあります）。

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