裏紙

ほぼ競プロ、たまに日記

WUPC 2019 H - Doki Doki Programming Clubs!

問題

H - Doki Doki Programming Clubs!

問題概要

N個の数列が与えられる。 i番目の数列A_iの長さはK_iである。 クエリ(X,Y)とは以下の通り:

  • 数列A_X, A_Yについて、 \displaystyle \sum_{i=0}^{\max (K_X, K_Y)-1} A_{X, \ i \  \% \  K_X} \times A_{Y,\ i \  \% \  K_Y}10^9 + 7で割った余りを答える

上記のクエリがQ個与えられるので、各クエリについて答えよ。

  •  2 \le N \le 200000
  •  1 \le K_i
  •  \sum K_i \le 200000
  •  1 \le A_{i,j} \le 10^9
  •  1 \le Q \le 200000
  •  0 \le X_i , Y_i \le N-1
  •  X_i \neq Y_i

イデア

まず、クエリについて、どのような処理になっているかを観察してみる。 以下では、クエリ(x,y)について、K_x \le K_yを仮定する。 数列A_yの方が長いので、短い方の数列A_xを長い方に揃えることになる。 例えば、K_x = 3, K_y = 8ならこんな感じ。

f:id:imulan:20190312214500p:plain

短い方の数列A_xを長い方に周期的に揃えて、積の和について考える。

f:id:imulan:20190312214716p:plain

ここで、問題で与えられた通りに短い方を長い方に毎回揃えて計算してしまうとTLEするので、短い方に揃えて計算出来ないかを考える。 長い方のindexに注目してみると、短い方の長さK_xの剰余によって、どの要素との積になっているかが決定している:

f:id:imulan:20190312215153p:plain

よって、クエリに対して O( \min (K_x, K_y))で計算したい時、数列A_yを周期K_xで分類した和(上の例で言うと、数列A_yに関する赤の和と青の和と緑の和)を用意しておけば良いことになる。

以上の考察から、短い方の数列に揃えてクエリを処理するためには、前計算として各数列A_iについて、自分より短い周期について、その剰余で分類した和を用意しておく必要がある。

以下では、 \sum K_i = Sとする。 この前計算は O(S \sqrt{S})で実現することができる。 その理由については、実際に前計算のコードを見てみるとわかりやすい:

// 前計算
// k[i] のdistinctな要素を列挙
vector<int> uk(k);
sort(uk.begin(), uk.end());
uk.erase(unique(uk.begin(), uk.end()), uk.end());
int UK = uk.size();

// 各数列 a[i] について、自分以下の周期の和を前計算
vector<vector<vector<long>>> sum(n, vector<vector<long>>(UK));
for(int i=0; i<n; ++i){
    for(int j=0; j<UK; ++j){
        int L = uk[j];
        if(L > k[i]) break;

        sum[i][j] = vector<long>(L);
        for(int l=0; l<k[i]; ++l){
            sum[i][j][l%L] += a[i][l];
            sum[i][j][l%L] %= mod;
        }
    }
}

iのループとlのループを合わせて、ちょうどS回のループになっているので、ループが回る回数はO(S \times UK)となっている。 ここで、UKとは、K_iの種類数となっているが、数列の長さK_iの種類数はたかだかO( \sqrt{S})である。

できるだけ種類数が多くなるような状況を考えてみると、数列の長さは1,2,3,4, \ldotsと、長さを1ずつ増やしながら1つずつ数列を用意する、という状況になる。 これを長さtまでもれなく揃えたとすると、長さの合計は1+2+ \ldots + t = \frac{t(t+1)}{2}となり、\frac{t(t+1)}{2} \le Sなので、種類数はO( \sqrt{S})で抑えられていることが分かる。

以上で、前計算は O(S \sqrt{S})であることが確認できた。 以下ではクエリ処理について確認する。

一度来たクエリについてはメモ化して答えることにし、新しいクエリについては O( \min (K_x, K_y)) で計算することにすると、計算量は O( (S+Q) \sqrt{S} ) となっている。 これを示すために、2つの場合に分けて考える:

 \min (K_x, K_y) \lt \sqrt{S}のとき

1クエリに対して O( \min (K_x, K_y)) = O(\sqrt{S})で処理できるので、クエリ全体についてO(Q \sqrt{S})で処理できる。

 \min (K_x, K_y) \ge \sqrt{S}のとき

この場合は、K_i \ge \sqrt{S}となるような数列はたかだか\sqrt{S}個しか存在しない。 この条件を満たす数列A_iに対して、i以外の数列とのクエリが全部与えられたとしても、そのクエリ合計でO(S)で抑えられているのは明らか。 以上のことから、クエリ全体についてO(S \sqrt{S})で処理できる。

以上より、計算量は全体で O((S+Q) \sqrt{S})となり、これは十分に高速である。

実装(C++)

続きを読む

BAPC 2018 D - Driver Disagreement

問題

Dashboard - 2018 Benelux Algorithm Programming Contest (BAPC 18) - Codeforces

問題概要

n個の交差点がある。交差点iは道が二手に分かれており、左に行くと交差点l_iに、右に行くと交差点r_iに辿り着くことが分かっている。また、交差点iからピサの斜塔が見える時はt_i = 1、見えない時はt_i = 0という情報がある。

今、自分が交差点ABのどちらかにいることが分かっている。そこから左右の選択を適切にすることによって、ピサの斜塔が見えるかどうかの情報から最初に自分がABのどちらにいたのかを特定することは可能か。不可能ならばindistinguishableと答え、可能ならば最短の操作回数を答えよ。

  •  2 \le n \le 10^5
  •  0 \le A,B \le n-1 , A \neq B
  •  0 \le l_i , r_i \le n-1
  •  t_i = 0, 1

イデア

一番素直な方法として思いつくのが今いる位置のペアを管理しながらBFSをするというものだが、これは状態がO(n^2)個あるので、TLEしてしまう。 簡単のために、まずindistinguishableなのかどうかだけを考えてみる。

以下では、問題をグラフとして置き換え、ピサの斜塔が見える頂点を黒、見えない頂点を白と呼ぶことにする。

頂点xyindistinguishableであることの意味について考えてみると、どのように移動してもそのペアの頂点の色は等しいということになる。 つまり、仮想的には同じ頂点にいると考えてしまってもいいと言える。

今、xyindistinguishable、かつyzindistinguishableであるということが分かっているとすると、xzの関係に注目したとき、直感的にはわざわざチェックするまでもなくindistinguishableなのでは?と思える。

実際にこれは正しい。 xzindistinguishableではないとすると、ある操作(例えば、LLRLRみたいな)によって、xの方は黒、zの方は白の頂点にいるという状況が発生しうる。 しかし、上の2つの仮定から、yは黒でもあり白でもあるということになってしまうが、これはあり得ない。

この同値関係が成り立つことを利用して、BFSの状態を減らすことを考える。 以下のBFSではindistinguishableでないペアが見つかり次第ストップするということを前提とする。 「既に2つの状態:(x,y)(y,z) をチェック済みである場合は(x,z)indistinguishableであるとしてそれ以降はチェックしない」というBFSを行う。

これはちゃんと機能するBFSとなる。 もし、本当にx,y,zindistinguishableなのであればやっていることは正しいし、 (x,z)が本当は区別可能だったとすると、BFSが(x,y)(y,z)の両方をパスしてしまっていることに反してしまうからである。

このような状態を効率よく管理するためには、UnionFindなどのデータ構造を使えば良い。 この状態のマージによって、BFS内で訪れる状態はO(n)個となり、十分に速い。 元の問題に戻ると、区別可能な時は最短の回数が必要になるので、BFS内で同時に回数も管理する。

実装(C++)

続きを読む