差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2020:0802_abc174 [2020/08/02]
ikatakos [解法]
+++ programming_algorithm:contest_history:atcoder:2020:0802_abc174 [2020/08/05] (現在)
ikatakos [解法]
@@ 行 1: / 行 1: @@
-======AtCoder Beginner Contest 174 D,E,F問題メモ======
+======AtCoder Beginner Contest 174 C,D,E,F問題メモ======
 [[https://atcoder.jp/contests/abc174|AtCoder Beginner Contest 174]]
@@ 行 5: / 行 5: @@
 F問題は問題文もシンプルだし、いかにも過去にどこかで出題されてそう。 \\
 こういうのは解法を知っているか知らないかに左右される部分はあるが、知らなかったなら次までに覚えておけばよし。
+===== C - Repsept =====
+[[https://atcoder.jp/contests/abc174/tasks/abc174_c|C - Repsept]]
+==== 問題 ====
+  * $7,77,777,...$ と無限に続く数列の中で、$K$ の倍数が登場するか判定し、登場するなら最初は何番目か答えよ
+  * $1 \le K \le 10^6$
+==== 解法 ====
+解法の思いつきにくさはDより上かも知れない。
+数列を素因数分解してもパターンが見えてくるわけでも無く、順番に試し割るのが速そう。 \\
+だが、$K$ が大きくなると急激に数値が大きくなっていくため、そのままの計算は無理。
+割り算の筆算のように、頭の桁からの計算をシミュレートすると、桁数が大きくなっても大丈夫。
+         ____2_6__________
+  K = 29 ) 7 7 7 7 7 7 ...  (無限に供給される7)
+          _5_8_
+9 7
+          _1_7_4_
+3 7
+             ...
+を29で割った余りは19で、割り切れていない。
+筆算では、この'19'に次の桁の'7'を下ろして197とする。 \\
+プログラム的には $19 \times 10 + 7$ となる。
+続いて197を29で割ると23余り、まだ割り切れてないので237として……と繰り返す。
+割り切れたらその時点での ''777...'' の桁数が最初に割り切れる要素となる。1桁の'7'から数えて何回割ったかを数えておけばよい。
+永遠に割り切れないこともあるのが厄介だが、処理の性質上、余りが過去に出てきたのと被ったら、そこからは全く同じ展開がループするので割り切れないと分かる。
+たとえば上記なら $7,19,23,...$ などが再度余りとして出てきたら、ループすることになる。
+$K$ で割った余りの取りうる値は、$0～K-1$ しかない。 \\
+せいぜい $K$ 回まで調べれば、必ず、ループするか割り切れるかのどちらかには行き着く。
+ところで、1をずらっと並べた数を、[[wpjp>レピュニット]] という（rep-unit）。
+今回は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))
+</sxh>
 ===== D - Alter Altar =====
@@ 行 24: / 行 89: @@
 '''R''' の左隣に '''W''' が存在しないというのは、''RRRR...RRWWWW...WW'' という状態になっているということ。
-'''R''' と '''W''' の境界はどこか？ を $0～N$ で全探索するとよい。
+'''R''' と '''W''' の境界はどこか？ を $0～N$ で全探索する。
   初期状態  W R W W R W R R
-            R R R W W W W W    仮に'R'が3文字続く状態の答えを調べる
+  目標状態  R R R W W W W W    仮に、この目標状態にするのに必要な操作数を調べる
-           |--2--|----3----|   それぞれの陣営で矛盾している個数
+           |--2--|----3----|   それぞれの陣営で初期状態と異なる個数
+ここでR陣営とW陣営から、初期状態と目標状態が異なる文字を1つずつ選んで交換すると、必ず互いに目標状態と一致する。
+  目標状態  R R R|W W W W W
+  初期状態  W R W|W R W R R
+            ~    |      ~
+            R R W|W R W W R
-ここで左陣営と右陣営から矛盾している文字を1つずつ選んで交換すると、必ず互いに解消される。
+つまり、初期状態と目標状態が異なる（＝何らかの操作をしなければならない）要素が $2+3$ 個あって、
-  * 2つの文字を入れ替える操作をおこなうと、合計2解消される
+  * 2つの文字を入れ替える操作をおこなうと、合計2、解決する
-  * 1つの文字を書き換える操作を行うと、1だけ解消される
+  * 1つの文字を書き換える操作を行うと、1だけ解決する
 なので、できるだけ2文字の入れ替えをおこない、余った分は1文字の書き換えを行うのがよい。
@@ 行 49: / 行 121: @@
   初期状態  W R W W R W R R
-1 1 2 3 3 4 4 4
+1 1 2 3 3 4 4 4    仮にそこに境界を置いたときに、境界より左の'W'の個数
-4 3 3 3 2 2 1 0
+4 3 3 3 2 2 1 0    仮にそこに境界を置いたときに、境界より右の'R'の個数
           -------------------
   MAX      4 4 3 3 3 3 4 4 4    → このMINが答え
@@ 行 79: / 行 151: @@
 print(min(map(max, zip(left_w, right_r))))
 </sxh>
+もっと単純に、「常に最も左にある'''W'''と最も右にある'''R'''を入れ替える操作のみを行い、書き換えは行わない」でも最小を達成できるみたい。たしかに。
+この場合は '''R''' の個数が初期状態と最終状態で変わらないので、最終状態が一意に決まり、それのみ調べればよい。
@@ 行 104: / 行 181: @@
 なので、調べる $L$ は整数のみでよい。
-仮に最長の長さを $L=3$ にしようと思えば、必要な切る回数は
+仮に最長の長さを $L=3$ として切る回数を少なく抑えようと思えば、なるべく1本ずつを長く、つまり $L$ ごとに切ればよい。
-  Ai    1  2  3  4  5  6  7  8  9 10  ...
+ちょうど割り切れる境界あたりが混乱しやすいので詳しく見ていくと、
-  回数  0  0  0  1  1  1  2  2  2  3  ...
-なので、$(A_i-1)//L$ を計算すればよいと分かる。
+  L = 3
+  Ai        1  2  3  4  5  6  7  8  9 10  ...
+  切る回数  0  0  0  1  1  1  2  2  2  3  ...
+なので、$\dfrac{(A_i-1)}{L}$（切り捨て）を計算すればよいと分かる。
 <sxh python>
@@ 行 127: / 行 207: @@
 </sxh>
+仮に長さが実数も取り得るなら、演算誤差が生じるので難しくなる。
+二分探索は2でしか割らないので、1回ごとに全体を2倍していって、整数比較できる状態を保つとよいかな。
+それとも、入力が整数なら必ず2の冪乗分の○○と表現できる数になるので、意外とそのまま計算しても大丈夫だったりする？
 ===== F - Range Set Query =====
@@ 行 142: / 行 225: @@
-==== 解法 ====
+==== 解法1 ====
   * [[https://hama-du-competitive.hatenablog.com/entry/2016/10/01/001418|与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい - 問題解決の宝石箱]]
+  * [[https://drken1215.hatenablog.com/entry/2019/01/01/234400|SPOJ DQUERY - D-query - けんちょんの競プロ精進記録]]
 コンテスト中に上記の記事とかのアクセス数が謎の伸びを示してそう。
@@ 行 152: / 行 236: @@
 区間クエリというとセグメント木を使った解法が多いが、今回の場合は無理そうというのはわかる。
-たとえばノードに「そのノードが表す区間での種類数」などを持たせるにしても、左右のマージ時には、左右の間で被ってる要素が分からないと答えが求められない。
+たとえばノードに「そのノードが表す区間での種類数」などを持たせるにしても、左右のマージ時には、左右の間で被ってる具体的な要素が分からないと答えが求められない。
 bitフラグなんかで集合を管理すれば可能だが、それには1回の操作に $O(N)$ の計算量がかかるので、間に合わない。
-$C_i$ の種類毎にセグメント木を作れば一定区間にある同じ数字の個数が分かるので答えが求まるが、それも1回のクエリに $O(N \log{N})$ の計算がかかる。
+$C_i$ の種類毎に出現個数の累積和を作れば任意区間にある同じ数字の個数が分かるが、1回のクエリごとに全ての $C_i$ についてチェックしなければならず $O(N)$ の計算がかかり、やはり無理。
-複数個ある数字のみセグメント木を作る？ しかし全ての数字が2個ずつある場合などにTLEするのは変わらない。
-=== $C_i$ の区間への言い換え ===
+=== 「同じ数字を含むこと」の区間への言い換え ===
 要は上記記事の解法3なのだが。
-「$C_i$ の、もっとも近い同じ数字同士を1対象区間とする」と、「クエリ区間に完全に含まれる対象区間の個数」が、被る数字の個数となる。
+$C_i$ を「もっとも近い同じ数字同士を、1つの対象区間とする」と変換すると上手くいく。
   i   0  1  2  3  4  5  6  7  8  9
   Ci  2  5  6  5  2  1  7  9  7  2
   対象区間
-     [0           4]
+     [0           4]                  最も近い2同士
-        [1     3]
+        [1     3]                     最も近い5同士
-                 [4              9]
+                 [4              9]   最も近い2同士
-                       [6     8]
+                       [6     8]      最も近い7同士
   クエリ区間
         [1           5]               →  [1 3] が含まれる = かぶる数字は1個
      [0                       8]      →  [0 4][1 3][6 8] が含まれる = かぶる数字は3個
+上図のように、「クエリ区間に同じ数字が2つ入ってしまう」というのは、「クエリ区間に対象区間が完全に含まれる」と言い換えられる。 \\
+同じ数字が3つなら2個、4つなら3個の対象区間が含まれることになる。
+つまり、「クエリ区間に完全に含まれる対象区間の個数」＝「重複する数字の個数」なので、クエリ区間の長さから重複数を引いたものが種類数となる。
   * [[https://hama-du-competitive.hatenablog.com/entry/2017/04/22/185540|区間に含まれる区間の数をカウントするクエリにたくさん答えたい - 問題解決の宝石箱]]
-これを求めるには、対象区間もクエリ区間もまとめて（区間を $[L_i,R_i]$ と表現して） $R_i$ を基準にソートする。
+これを求めるには、区間を $[L_i,R_i]$ と表現するとして、対象区間もクエリ区間もまとめて $R_i$ を基準にソートする。
-ソートした区間を順番に処理する。ただし $R_i$ が同じものは対象区間を優先的に処理する。 \\
+ソートした区間を順番に処理する。$R_i$ が同じものは対象区間を優先的に処理する。 \\
 状態管理に、長さ $N$ の配列 $T$ を用意しておく。
@@ 行 191: / 行 279: @@
 区間和なので、$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を使った。
+制約の最大値の代入で $2 \times 10^7$ くらいになるため、PythonではNumbaでないと通らなかった。
 <sxh python>
@@ 行 266: / 行 354: @@
 </sxh>
+==== 解法2 ====
+より計算量の少ない解説pdfの方法。
+右端が $R_i$ のクエリを処理する段階では、「$R_i$ までに登場する中で、各要素が最後に登場した箇所のみ1、他は0の配列 $T$」があれば、
+そのクエリの答えは $T[L_i]～T[R_i]$ の和で求められる。 \\
+$T$ は解法1と同様Fenwick Treeなどで実装すればよい。
+                        Ri    未反映
+  i   0  1  2  3  4  5  6    (7  8  9)
+  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  8  9
+  last[c]  -  4  -  -  5  2  6  -  -
+$R=6$ のクエリの次に、$R=8$ のクエリが来たとする。 \\
+現在、$T$ には $i=6$ までの状態を反映しているのを、$i=7,8$ について更新する。
+  i   0  1  2  3  4  5  6  7  8
+  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 まで）
+これで状態の更新ができたので、$R=8$ であるクエリはこの $T$ を元に $T[L_i]～T[R_i]$ を合計すればよい。
+解法1はPyPyでも間に合わなかったが、こちらならソートするのがクエリだけで済むため計算量は $O(N+Q(\log{N}+\log{Q}))$ で、PyPyでも間に合う。
+本質的ではないが、解法1でも2でも $(R_i,L_i,i)$ などのタプルのソートが必要となるが、これをビットシフトして1つの整数にまとめてソートさせると、その部分は数倍高速化される。
+<sxh python>
+import sys
+def bit_add(arr, n, i, x):
+    while i <= n:
+        arr[i] += x
+        i += i & -i
+def bit_sum(arr, i):
+    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, sys.stdin.buffer.readline().split()))
+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, bn, before_appeared + 2, -1)
+        bit_add(bit, bn, p + 2, 1)
+        appeared[c] = p
+        p += 1
+    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
+print('\n'.join(map(str, ans)))
+</sxh>