差分

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

--- programming_algorithm:contest_history:atcoder:2019:1201_sumitrust2019 [2019/12/02] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:1201_sumitrust2019 [2019/12/03] – [解法] ikatakos
@@ 行 72: / 行 72: @@
 最終的に、L3の長さが答え。
+L2からL3へ移すところが計算量的にボトルネックとなる。
+文字の種類（今回は10種）を  $D$  とすると、計算量は  $O(D^2N)$ 。
@@ 行 90: / 行 93: @@
 </sxh>
+====解法2====
+'000'～'999' それぞれについて可能か調べる。解説pdf1個目の解法。
+'312' が可能か調べたければ、以下のようにする。各過程で、目標の数字が存在しなければ'312'は不可能。
+  * 先頭から最初に出現する'3'の位置を得る
+  * それ以降で次に最もはやく出現する'1'の位置を得る
+  * それ以降に'2'が存在したら、OK
+これを高速に実装するには、各数字につき、何番目に出現するかのindexリストをまず作成しておく。
+  * 数字  $k$  に対してのindexリストを  $loc_k$  とする
+  * 数字  $k$  に対して最後に出現するindexを  $last_k$  とする
+  S  123123
+  ↓
+  loc1: [0, 3]    last1: 3
+  loc2: [1, 4]    last2: 4
+  loc3: [2, 5]    last3: 5
+  * 1桁目の数字  $x$  を10通り試す
+    *  $i=loc_x[0]$  が最初のindex
+    * 2桁目の数字  $y$  を10通り試す
+      *  $i+1$  以降で最小のindexを  $loc_y$  から二分探索で得る。これを  $j$  とする
+      * 3桁目の数字  $z$  を10通り試す
+        *  $j \lt last_z$  なら、部分列 'xyz' は作れる
+計算量は、 $O(N+D^2(D+\log{N}))$  となる。 $N$  が大きければ、だいたい最初の  $O(N)$  のindexリストの作成が一番時間のかかる処理となる。
+<sxh python>
+from bisect import bisect
+n = int(input())
+s = input()
+location = [[] for _ in range(10)]
+for i, c in enumerate(map(int, s)):
+    location[c].append(i)
+last_indices = [loc[-1] if loc else -1 for loc in location]
+ans = 0
+for loc_x in location:
+    if not loc_x:
+        continue
+    i = loc_x[0]
+    for loc_y in location:
+        ji = bisect(loc_y, i)
+        if ji >= len(loc_y):
+            continue
+        j = loc_y[ji]
+        ans += sum(j < li for li in last_indices)
+print(ans)
+</sxh>
+あと、Pythonでは文字列検索が十分速いため、下手にindexを前計算するより、1文字ずつ検索する方が、この制約下では速かったりする。
 ===== E - Colorful Hats 2 =====
@@ 行 175: / 行 235: @@
 Aさんが先行するが、 $T_2$  の領域で抜かされる。
-ここで、 $T_1,T_2$  の各領域で「何周期先まで、この領域で交わり続けるか？」を考える。
+ $T_1,T_2$  の各領域で「何周期先まで、この領域で交わり続けるか？」を考える。
+周期目では、Bさんは  $D_d$  だけ進んだ位置からスタートしていると見なせる。3周期目では  $2D_d$ 、4周期目では  $3D_d$ 。。。
-  |           /       |      |     |    /|
-  |          /        |      |     |   / |
-  |      __-/~~       |      | __  |_-/~~|
-  |  A ／  /          |  A ／| ↑d | /   |
-  |  ／   / B         |  ／ B| ↓  |/    |
-  |／_--~~            |／_--~| ~~  |     |
-  |------|------|     |------|     |-----|
-     T1     T2           T1           T2
-周期目では、Bは  $D_d$  だけ進んだ位置からスタートしていると見なせる。3周期目では  $2D_d$ 、4周期目では  $3D_d$ 。。。
+  距離
+  |           /           |      |      |    /|
+  |          /            |      |      |   / |
+  |      __-/~~           |      |  __  |_-/~~|
+  |  A ／  /              |  A ／|  ↑d | /   |
+  |  ／   / B             |  ／ B|  ↓  |/    |
+  |／_--~~                |／_--~|  ~~  |     |
+  |------|------|時間     |------|      |-----|
+     T1     T2           T1           T2
 ここで  $T_1$  終了時点の両者の差を  $d$  とすると、
@@ 行 196: / 行 256: @@
 ただし、 $T_2$  領域では1周期目でも交わっているので、 $+1$  される。
-また、 $d$  がちょうど  $D_d$  で割り切れる場合、1回の接触が領域1と2で重複して数えられてしまうので、注意する。
+また、 $d$  がちょうど  $D_d$  で割り切れる場合、最後の1回の接触が領域1と2で重複して数えられてしまうので、注意する。
 <sxh python>