差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:1201_sumitrust2019 [2019/12/02] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:1201_sumitrust2019 [2019/12/03] – [解法2] ikatakos | ||
|---|---|---|---|
| 行 72: | 行 72: | ||
| 最終的に、L3の長さが答え。 | 最終的に、L3の長さが答え。 | ||
| + | |||
| + | L2からL3へ移すところが計算量的にボトルネックとなる。 | ||
| + | 文字の種類（今回は10種）を $D$ とすると、計算量は $O(D^2N)$。 | ||
| 行 90: | 行 93: | ||
| </ | </ | ||
| + | ====解法2==== | ||
| + | |||
| + | ' | ||
| + | |||
| + | ' | ||
| + | |||
| + | * 先頭から最初に出現する' | ||
| + | * それ以降で次に最もはやく出現する' | ||
| + | * それ以降に' | ||
| + | |||
| + | これを高速に実装するには、各数字につき、何番目に出現するかの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$ なら、部分列 ' | ||
| + | |||
| + | 計算量は、$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, | ||
| + | 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, | ||
| + | if ji >= len(loc_y): | ||
| + | continue | ||
| + | j = loc_y[ji] | ||
| + | ans += sum(j < li for li in last_indices) | ||
| + | print(ans) | ||
| + | |||
| + | </ | ||
| + | |||
| + | |||
| + | あと、Pythonでは文字列検索が十分速いため、下手にindexを前計算するより、1文字ずつ検索する方が、この制約下では速かったりする。 | ||
| ===== E - Colorful Hats 2 ===== | ===== E - Colorful Hats 2 ===== | ||
