WUPC 2019 H - Doki Doki Programming Clubs!
問題
H - Doki Doki Programming Clubs!
問題概要
個の数列が与えられる。 番目の数列の長さはである。 クエリとは以下の通り:
- 数列について、をで割った余りを答える
上記のクエリが個与えられるので、各クエリについて答えよ。
アイデア
まず、クエリについて、どのような処理になっているかを観察してみる。 以下では、クエリについて、を仮定する。 数列の方が長いので、短い方の数列を長い方に揃えることになる。 例えば、ならこんな感じ。
短い方の数列を長い方に周期的に揃えて、積の和について考える。
ここで、問題で与えられた通りに短い方を長い方に毎回揃えて計算してしまうとTLEするので、短い方に揃えて計算出来ないかを考える。 長い方のindexに注目してみると、短い方の長さの剰余によって、どの要素との積になっているかが決定している:
よって、クエリに対してで計算したい時、数列を周期で分類した和(上の例で言うと、数列に関する赤の和と青の和と緑の和)を用意しておけば良いことになる。
以上の考察から、短い方の数列に揃えてクエリを処理するためには、前計算として各数列について、自分より短い周期について、その剰余で分類した和を用意しておく必要がある。
以下では、とする。 この前計算はで実現することができる。 その理由については、実際に前計算のコードを見てみるとわかりやすい:
// 前計算 // 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; } } }
のループとのループを合わせて、ちょうど回のループになっているので、ループが回る回数はとなっている。 ここで、とは、の種類数となっているが、数列の長さの種類数はたかだかである。
できるだけ種類数が多くなるような状況を考えてみると、数列の長さはと、長さを1ずつ増やしながら1つずつ数列を用意する、という状況になる。 これを長さまでもれなく揃えたとすると、長さの合計はとなり、なので、種類数はで抑えられていることが分かる。
以上で、前計算はであることが確認できた。 以下ではクエリ処理について確認する。
一度来たクエリについてはメモ化して答えることにし、新しいクエリについてはで計算することにすると、計算量はとなっている。 これを示すために、2つの場合に分けて考える:
のとき
1クエリに対してで処理できるので、クエリ全体についてで処理できる。
のとき
この場合は、となるような数列はたかだか個しか存在しない。 この条件を満たす数列に対して、以外の数列とのクエリが全部与えられたとしても、そのクエリ合計でで抑えられているのは明らか。 以上のことから、クエリ全体についてで処理できる。
以上より、計算量は全体でとなり、これは十分に高速である。
実装(C++)
続きを読むBAPC 2018 D - Driver Disagreement
問題
Dashboard - 2018 Benelux Algorithm Programming Contest (BAPC 18) - Codeforces
問題概要
個の交差点がある。交差点は道が二手に分かれており、左に行くと交差点に、右に行くと交差点に辿り着くことが分かっている。また、交差点からピサの斜塔が見える時は、見えない時はという情報がある。
今、自分が交差点かのどちらかにいることが分かっている。そこから左右の選択を適切にすることによって、ピサの斜塔が見えるかどうかの情報から最初に自分がかのどちらにいたのかを特定することは可能か。不可能ならばindistinguishable
と答え、可能ならば最短の操作回数を答えよ。
アイデア
一番素直な方法として思いつくのが今いる位置のペアを管理しながらBFSをするというものだが、これは状態が個あるので、TLEしてしまう。
簡単のために、まずindistinguishable
なのかどうかだけを考えてみる。
以下では、問題をグラフとして置き換え、ピサの斜塔が見える頂点を黒、見えない頂点を白と呼ぶことにする。
頂点とがindistinguishable
であることの意味について考えてみると、どのように移動してもそのペアの頂点の色は等しいということになる。
つまり、仮想的には同じ頂点にいると考えてしまってもいいと言える。
今、とがindistinguishable
、かつとがindistinguishable
であるということが分かっているとすると、との関係に注目したとき、直感的にはわざわざチェックするまでもなくindistinguishable
なのでは?と思える。
実際にこれは正しい。
とがindistinguishable
ではないとすると、ある操作(例えば、LLRLR
みたいな)によって、の方は黒、の方は白の頂点にいるという状況が発生しうる。
しかし、上の2つの仮定から、は黒でもあり白でもあるということになってしまうが、これはあり得ない。
この同値関係が成り立つことを利用して、BFSの状態を減らすことを考える。
以下のBFSではindistinguishable
でないペアが見つかり次第ストップするということを前提とする。
「既に2つの状態:と をチェック済みである場合はをindistinguishable
であるとしてそれ以降はチェックしない」というBFSを行う。
これはちゃんと機能するBFSとなる。
もし、本当にがindistinguishable
なのであればやっていることは正しいし、
が本当は区別可能だったとすると、BFSがとの両方をパスしてしまっていることに反してしまうからである。
このような状態を効率よく管理するためには、UnionFindなどのデータ構造を使えば良い。 この状態のマージによって、BFS内で訪れる状態は個となり、十分に速い。 元の問題に戻ると、区別可能な時は最短の回数が必要になるので、BFS内で同時に回数も管理する。