差分
このページの2つのバージョン間の差分を表示します。
次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2020:0802_abc174 [2020/08/02] – 作成 ikatakos | programming_algorithm:contest_history:atcoder:2020:0802_abc174 [2020/08/04] – [解法2] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======AtCoder Beginner Contest 174 D, | + | ======AtCoder Beginner Contest 174 C,D, |
[[https:// | [[https:// | ||
行 5: | 行 5: | ||
F問題は問題文もシンプルだし、いかにも過去にどこかで出題されてそう。 \\ | F問題は問題文もシンプルだし、いかにも過去にどこかで出題されてそう。 \\ | ||
こういうのは解法を知っているか知らないかに左右される部分はあるが、知らなかったなら次までに覚えておけばよし。 | こういうのは解法を知っているか知らないかに左右される部分はあるが、知らなかったなら次までに覚えておけばよし。 | ||
+ | |||
+ | ===== C - Repsept ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * $7, | ||
+ | * $1 \le K \le 10^6$ | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | 解法の思いつきにくさはDより上かも知れない。 | ||
+ | |||
+ | 数列を素因数分解してもパターンが見えてくるわけでも無く、順番に試し割るのが速そう。 \\ | ||
+ | だが、$K$ が大きくなると急激に数値が大きくなっていくため、そのままの計算は無理。 | ||
+ | |||
+ | 割り算の筆算のように、頭の桁からの計算をシミュレートすると、桁数が大きくなっても大丈夫。 | ||
+ | |||
+ | | ||
+ | K = 29 ) 7 7 7 7 7 7 ... | ||
+ | _5_8_ | ||
+ | 1 9 7 | ||
+ | _1_7_4_ | ||
+ | 2 3 7 | ||
+ | ... | ||
+ | |||
+ | 77を29で割った余りは19で、割り切れていない。 | ||
+ | |||
+ | 筆算では、この' | ||
+ | これは、プログラム的には $19 \times 10 + 7$ となる。 | ||
+ | |||
+ | 続いて197を29で割ると23余り、まだ割り切れてないので237として……と繰り返す。 | ||
+ | |||
+ | 割り切れたらその時点での '' | ||
+ | |||
+ | 永遠に割り切れないこともあるのが厄介だが、処理の性質上、余りが過去に出てきたのと被ったら、そこからはループするので割り切れないと分かる。 | ||
+ | たとえば上記なら $7, | ||
+ | |||
+ | $K$ で割った余りの取りうる値は、$0~K-1$ しかない。 \\ | ||
+ | せいぜい $K$ 回まで調べれば、必ず、ループするか割り切れるかのどちらかには行き着く。 | ||
+ | |||
+ | ところで、1をずらっと並べた数を、[[wpjp> | ||
+ | 今回は7(septem)を並べているので rep-sept。 | ||
+ | |||
+ | <sxh python> | ||
+ | def solve(k): | ||
+ | x = 7 | ||
+ | checked = set() | ||
+ | ans = 1 | ||
+ | while True: | ||
+ | x %= k | ||
+ | if x == 0: | ||
+ | return ans | ||
+ | if x in checked: | ||
+ | return -1 | ||
+ | checked.add(x) | ||
+ | x = x * 10 + 7 | ||
+ | ans += 1 | ||
+ | |||
+ | |||
+ | k = int(input()) | ||
+ | print(solve(k)) | ||
+ | </ | ||
+ | |||
===== D - Alter Altar ===== | ===== D - Alter Altar ===== | ||
行 24: | 行 89: | ||
''' | ''' | ||
- | ''' | + | ''' |
初期状態 | 初期状態 | ||
- | | + | 目標状態 |
| | ||
- | | + | |
+ | |||
+ | ここでR陣営とW陣営から、初期状態と目標状態が異なる文字を1つずつ選んで交換すると、必ず互いに目標状態と一致する。 | ||
+ | |||
+ | 目標状態 | ||
+ | 初期状態 | ||
+ | ~ | ~ | ||
+ | R R W|W R W W R | ||
- | ここで左陣営と右陣営から矛盾している文字を1つずつ選んで交換すると、必ず互いに解消される。 | + | つまり、初期状態と目標状態が異なる(=何らかの操作をしなければならない)要素が $2+3$ 個あって、 |
- | * 2つの文字を入れ替える操作をおこなうと、合計2解消される | + | * 2つの文字を入れ替える操作をおこなうと、合計2、解決する |
- | * 1つの文字を書き換える操作を行うと、1だけ解消される | + | * 1つの文字を書き換える操作を行うと、1だけ解決する |
なので、できるだけ2文字の入れ替えをおこない、余った分は1文字の書き換えを行うのがよい。 | なので、できるだけ2文字の入れ替えをおこない、余った分は1文字の書き換えを行うのがよい。 | ||
行 79: | 行 151: | ||
print(min(map(max, | print(min(map(max, | ||
</ | </ | ||
+ | |||
+ | 「常に最も左にある''' | ||
+ | |||
+ | この場合は ''' | ||
+ | |||
行 96: | 行 173: | ||
==== 解法 ==== | ==== 解法 ==== | ||
- | 答えを決め打てば必要な切断回数は簡単に求まるので、二分探索の出番。 | + | * 答えを決め打てば必要な切断回数は簡単に求まる |
+ | * 長さ $L$ が実現可能なら、$L$ 以上の長さは必ず実現可能 | ||
+ | |||
+ | ので、二分探索の出番。 | ||
- | 答えの言い方がまどろっこしいが、要は「$L-1$ が実現不可能で、$L$ が実現可能」な整数値 $L$ を求めればよい。 \\ | + | 答えの言い方がまどろっこしいが、要は「$L-1$ が実現不可能で、$L$ が実現可能な整数値 $L$」を求めればよい。 \\ |
なので、調べる $L$ は整数のみでよい。 | なので、調べる $L$ は整数のみでよい。 | ||
行 124: | 行 204: | ||
</ | </ | ||
+ | 仮に長さが実数も取り得るなら、演算誤差が生じるので難しくなる。 | ||
+ | 二分探索は2でしか割らないので、1回ごとに全体を2倍していって、整数比較できる状態を保つとよいかな。 | ||
===== F - Range Set Query ===== | ===== F - Range Set Query ===== | ||
行 135: | 行 216: | ||
* クエリ | * クエリ | ||
* $C_{L_i}~C_{R_i}$ にある数字の種類数を求めよ | * $C_{L_i}~C_{R_i}$ にある数字の種類数を求めよ | ||
- | * $$ | + | * $1 \le N,Q \le 5 \times 10^5$ |
- | ==== 解法 ==== | + | ==== 解法1 ==== |
* [[https:// | * [[https:// | ||
+ | * [[https:// | ||
コンテスト中に上記の記事とかのアクセス数が謎の伸びを示してそう。 | コンテスト中に上記の記事とかのアクセス数が謎の伸びを示してそう。 | ||
行 149: | 行 231: | ||
区間クエリというとセグメント木を使った解法が多いが、今回の場合は無理そうというのはわかる。 | 区間クエリというとセグメント木を使った解法が多いが、今回の場合は無理そうというのはわかる。 | ||
- | たとえばノードに「そのノードが表す区間での種類数」などを持たせるにしても、左右のマージ時には、左右の間で被ってる要素が分からないと答えが求められない。 | + | たとえばノードに「そのノードが表す区間での種類数」などを持たせるにしても、左右のマージ時には、左右の間で被ってる具体的な要素が分からないと答えが求められない。 |
bitフラグなんかで集合を管理すれば可能だが、それには1回の操作に $O(N)$ の計算量がかかるので、間に合わない。 | bitフラグなんかで集合を管理すれば可能だが、それには1回の操作に $O(N)$ の計算量がかかるので、間に合わない。 | ||
- | $C_i$ の種類毎にセグメント木を作れば一定区間にある同じ数字の個数が分かるので答えが求まるが、それも1回のクエリに $O(N \log{N})$ の計算がかかる。 | + | $C_i$ の種類毎に出現個数の累積和を作れば任意区間にある同じ数字の個数が分かるが、1回のクエリごとに全ての $C_i$ についてチェックしなければならず |
- | + | ||
- | 複数個ある数字のみセグメント木を作る? しかし全ての数字が2個ずつある場合などにTLEするのは変わらない。 | + | |
- | === $C_i$ の区間への言い換え === | + | === 「同じ数字を含むこと」の区間への言い換え === |
要は上記記事の解法3なのだが。 | 要は上記記事の解法3なのだが。 | ||
- | 「$C_i$ の、もっとも近い同じ数字同士を1対象区間とする」と、「クエリ区間に完全に含まれる対象区間の個数」が、被る数字の個数となる。 | + | $C_i$ を「もっとも近い同じ数字同士を、1つの対象区間とする」と変換すると上手くいく。 |
i | i | ||
Ci 2 5 6 5 2 1 7 9 7 2 | Ci 2 5 6 5 2 1 7 9 7 2 | ||
対象区間 | 対象区間 | ||
- | | + | |
- | [1 3] | + | [1 |
- | | + | |
- | | + | |
クエリ区間 | クエリ区間 | ||
[1 | [1 | ||
| | ||
+ | |||
+ | 上図のように、「クエリ区間に同じ数字が2つ入ってしまう」というのは、「クエリ区間に対象区間が完全に含まれる」と言い換えられる。 \\ | ||
+ | 同じ数字が3つなら2個、4つなら3個の対象区間が含まれることになる。 | ||
+ | |||
+ | つまり、「クエリ区間に完全に含まれる対象区間の個数」=「重複する数字の個数」なので、クエリ区間の長さから重複数を引いたものが種類数となる。 | ||
+ | |||
* [[https:// | * [[https:// | ||
- | これを求めるには、対象区間もクエリ区間もまとめて(区間を $[L_i,R_i]$ と表現して) $R_i$ を基準にソートする。 | + | これを求めるには、区間を $[L_i,R_i]$ と表現するとして、対象区間もクエリ区間もまとめて |
- | ソートした区間を順番に処理する。ただし | + | ソートした区間を順番に処理する。$R_i$ が同じものは対象区間を優先的に処理する。 \\ |
状態管理に、長さ $N$ の配列 $T$ を用意しておく。 | 状態管理に、長さ $N$ の配列 $T$ を用意しておく。 | ||
行 184: | 行 270: | ||
* $T[L_i]$ に、1加算する | * $T[L_i]$ に、1加算する | ||
* クエリ区間の場合 | * クエリ区間の場合 | ||
- | * $T$ の $L_i~R_i$ の合計値が求める値となる | + | * $T[L_i]~T[R_i]$ の合計値が求める値となる |
区間和なので、$T$ はFenwick Treeなどで実装すればよい。 | 区間和なので、$T$ はFenwick Treeなどで実装すればよい。 | ||
- | 計算量は、対象区間が $O(N)$ 生成され、クエリ区間と合わせてソートする部分が最もかかり、$O((N+Q) \log{(N+Q)})$ となる。 | + | 計算量は、対象区間が $O(N)$ 生成され、$Q$ 個のクエリ区間と一緒にソートする部分が最もかかり、$O((N+Q) \log{(N+Q)})$ となる。 \\ |
+ | 制約の最大値の代入で $2 \times 10^7$ くらいになるため、PythonではNumbaでないと通らなかった。 | ||
<sxh python> | <sxh python> | ||
行 262: | 行 349: | ||
</ | </ | ||
+ | ==== 解法2 ==== | ||
+ | より計算量の少ない解説pdfの方法。 | ||
+ | |||
+ | 右端が $R_i$ のクエリを処理する段階では、「$R_i$ までに登場する中で、各要素が最後に登場した箇所のみ1、他は0の配列 $T$」があれば、 | ||
+ | そのクエリの答えは $T[L_i]~T[R_i]$ の和で求められる。 \\ | ||
+ | $T$ は解法1と同様Fenwick Treeなどで実装すればよい。 | ||
+ | |||
+ | Ri | ||
+ | i | ||
+ | Ci 2 5 6 5 2 5 7 (9 7 2) | ||
+ | | ||
+ | Ti 0 0 1 0 1 1 1 (0 0 0) | ||
+ | |||
+ | 後で気付いたが、$T$ は解法1で作るやつの0-1を反転させたものだ。解法1は、不要になったものに1を立てていくという操作をしていた。 | ||
+ | |||
+ | さて、$T$ をどうやって管理するか。毎クエリ、ゼロから作るわけにもいかないので、順次更新する方法を考える。 | ||
+ | |||
+ | クエリ $[L_i, R_i]$ を $R$ 順にソートしておき、その順に処理することにする。 | ||
+ | |||
+ | $T$ の他、以下の情報を管理しておく。 | ||
+ | |||
+ | * 現在、要素 $c$ が最後に登場した $i$ の位置 $last[c] = i$ | ||
+ | |||
+ | c 1 2 3 4 5 6 7 | ||
+ | last[c] | ||
+ | |||
+ | $R=6$ のクエリの次に、$R=8$ のクエリが来たとする。 \\ | ||
+ | 現在、$T$ には $i=6$ までの状態を反映しているのを、$i=7, | ||
+ | |||
+ | i | ||
+ | Ci 2 5 6 5 2 5 7 9 7 | ||
+ | | ||
+ | Ti 0 0 1 0 1 1 1 0 0 (R=6 まで) | ||
+ | |||
+ | $C_7=9$ は、過去にまだ登場したことがないので、$T[7]=1$ とするのみ。$last[9]=7$ としておく。 | ||
+ | |||
+ | Ti 0 0 1 0 1 1 1 [1] 0 (R=7 まで) | ||
+ | |||
+ | $C_8=7$ は $last[7]$ を参照すると $i=6$ で出てきていて、新たに右端となる位置が変わるので $T[6]=0$、$T[8]=1$ とする。 \\ | ||
+ | また、$last[7]=8$ に更新しておく。 | ||
+ | |||
+ | Ti 0 0 1 0 1 1 [0] 1 [1] | ||
+ | |||
+ | これで状態の更新ができたので、$R=8$ であるクエリはこの $T$ を元に $T[L_i]~T[R_i]$ を合計すればよい。 | ||
+ | |||
+ | 解法1はPyPyでも間に合わなかったが、こちらならソートするのがクエリだけで済むため計算量は $O(N+Q(\log{N}+\log{Q}))$ で、PyPyでも間に合う。 \\ | ||
+ | ただしそこまで余裕はないので、PyPyで高速化されにくい書き方をするとオーバーするかも。 | ||
+ | |||
+ | 本質的ではないが、解法1でも2でも $(R_i, | ||
+ | |||
+ | <sxh python> | ||
+ | import sys | ||
+ | |||
+ | |||
+ | def bit_add(arr, | ||
+ | while i <= n: | ||
+ | arr[i] += x | ||
+ | i += i & -i | ||
+ | |||
+ | |||
+ | def bit_sum(arr, | ||
+ | result = 0 | ||
+ | while i > 0: | ||
+ | result += arr[i] | ||
+ | i ^= i & -i | ||
+ | return result | ||
+ | |||
+ | |||
+ | n, q = map(int, sys.stdin.buffer.readline().split()) | ||
+ | ccc = list(map(int, | ||
+ | |||
+ | mp = map(int, sys.stdin.buffer.read().split()) | ||
+ | itr = zip(mp, mp) | ||
+ | rli = [0] * q | ||
+ | for i in range(q): | ||
+ | l, r = next(itr) | ||
+ | rli[i] = (r << 40) + (l << 20) + i | ||
+ | rli.sort() | ||
+ | mask = (1 << 20) - 1 | ||
+ | |||
+ | bn = n + 2 | ||
+ | bit = [0] * (bn + 1) | ||
+ | ans = [0] * q | ||
+ | appeared = [-1] * (n + 1) | ||
+ | p = 0 | ||
+ | |||
+ | for j in range(q): | ||
+ | k = rli[j] | ||
+ | r = k >> 40 | ||
+ | l = (k >> 20) & mask | ||
+ | i = k & mask | ||
+ | while p < r: | ||
+ | c = ccc[p] | ||
+ | before_appeared = appeared[c] | ||
+ | if before_appeared != -1: | ||
+ | bit_add(bit, | ||
+ | bit_add(bit, | ||
+ | appeared[c] = p | ||
+ | p += 1 | ||
+ | |||
+ | ans[i] = bit_sum(bit, | ||
+ | |||
+ | print(' | ||
+ | </ | ||