差分
このページの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の長さが答え。 | 最終的に、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 ===== | ||
行 159: | 行 219: | ||
変な読み違いをして時間をかけてしまった。速度だけでなく、時間周期 $T_1,T_2$ も、AさんとBさんで別々だと思い込んでしまった。(まぁそれでも変曲点ごとに分解すれば解ける。実装がやたら面倒くさいが) | 変な読み違いをして時間をかけてしまった。速度だけでなく、時間周期 $T_1,T_2$ も、AさんとBさんで別々だと思い込んでしまった。(まぁそれでも変曲点ごとに分解すれば解ける。実装がやたら面倒くさいが) | ||
- | 場合分け。F問題にしては簡単。速度と距離のグラフを書くと理解の整理になる。 | + | 場合分け。F問題にしては簡単? 速度と距離のグラフを書くと理解の整理になる。 |
周期が $T_1+T_2$ で共通(これを $\lambda$ とする)なので、$\lambda$ で進む距離が等しければ、$\lambda$ ごとに必ず出会い続けるので、infinity。 | 周期が $T_1+T_2$ で共通(これを $\lambda$ とする)なので、$\lambda$ で進む距離が等しければ、$\lambda$ ごとに必ず出会い続けるので、infinity。 | ||
行 175: | 行 235: | ||
Aさんが先行するが、$T_2$ の領域で抜かされる。 | Aさんが先行するが、$T_2$ の領域で抜かされる。 | ||
- | ここで、$T_1,T_2$ の各領域で「何周期先まで、この領域で交わり続けるか?」を考える。 | + | $T_1,T_2$ の各領域で「何周期先まで、この領域で交わり続けるか?」を考える。 |
- | + | 2周期目では、Bさんは $D_d$ だけ進んだ位置からスタートしていると見なせる。3周期目では $2D_d$、4周期目では $3D_d$。。。 | |
- | | / | + | |
- | | / | | | + | |
- | | __-/ | + | |
- | | A / / | A /| ↑d | / | | + | |
- | | / / | + | |
- | |/_--~~ | + | |
- | |------|------| | + | |
- | | + | |
- | 2周期目では、Bは $D_d$ だけ進んだ位置からスタートしていると見なせる。3周期目では $2D_d$、4周期目では $3D_d$。。。 | + | 距離 |
+ | | / | ||
+ | | / | | | / | | ||
+ | | __-/ | ||
+ | | A / / | A /| ↑d | / | | ||
+ | | / / | ||
+ | |/_--~~ | ||
+ | |------|------|時間 | ||
+ | | ||
ここで $T_1$ 終了時点の両者の差を $d$ とすると、 | ここで $T_1$ 終了時点の両者の差を $d$ とすると、 | ||
行 196: | 行 256: | ||
ただし、$T_2$ 領域では1周期目でも交わっているので、$+1$ される。 | ただし、$T_2$ 領域では1周期目でも交わっているので、$+1$ される。 | ||
- | また、$d$ がちょうど $D_d$ で割り切れる場合、1回の接触が領域1と2で重複して数えられてしまうので、注意する。 | + | また、$d$ がちょうど $D_d$ で割り切れる場合、最後の1回の接触が領域1と2で重複して数えられてしまうので、注意する。 |
<sxh python> | <sxh python> |