変なタイトルですみません。要は A = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 }という配列があった場合、9よりも左側だと1が2個あるとか右側だと2や3や6が1個あるといった情報をすばやく取得できるようにしたいわけです。
問題の趣旨
最大長20万文字の文字列がひとつ与えられる。
ここから3文字抜き出して回文をつくりたい。
回文は文字を抜き出す位置が異なれば別物とみなす。
3つの要素を取り出す場合は真ん中の要素に着目するとよさそうです。するとS[i]とS[k]が同じになるような組み合わせの数を数えればよいということになります。
配列のi番目よりも左（右）にある要素のうち特定の値をもつ要素の個数を取得する
これで解を得ることができます。
その都度数えていては時間がかかるので文字列が与えられたらまとめて処理をすることで処理にかかる時間を短縮します。また他のケースでも使えるような汎用性のあるクラスとして実装します。その結果、多少実行時間が長くなっても気にしないことにします。AtCoderでは時間内に正しい解を出力すればそれが正義です。
Contents
CountLeftRightクラスを実装する
まず引数に使われている要素の種類数を調べて各要素をint型に変換します。問題では英大文字のみしか与えられないので最大で26種類です。変なことをしないで要素数26の配列にしてもよいのですが、引数がlong型の配列であっても対応できるようなものを実装したいのでこのようにします。
引数の配列を先頭と最後尾から見ていって、どの要素が何回現れるかを数えて、その結果をLeftsとRightsに記録していきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
public class CountLeftRight<T> { T[] A; int N; int[][] Lefts; int[][] Rights; Dictionary<T, int> ToInt = new Dictionary<T, int>(); public CountLeftRight(IEnumerable<T> vs) { A = vs.ToArray(); N = vs.ToArray().Length; HashSet<T> set = new HashSet<T>(); foreach (T c in vs) set.Add(c); var arr = set.ToArray(); for (int i = 0; i < arr.Length; i++) ToInt.Add(arr[i], i); int[] counts = new int[ToInt.Count]; Lefts = new int[N][]; for (int i = 0; i < N; i++) { Lefts[i] = (int[])counts.Clone(); T t = A[i]; int v = ToInt[t]; counts[v]++; } counts = new int[ToInt.Count]; Rights = new int[N][]; for (int i = N - 1; i >= 0; i--) { Rights[i] = (int[])counts.Clone(); T t = A[i]; int v = ToInt[t]; counts[v]++; } } } |
第一引数で指定された位置よりも左または右に第二引数で指定された要素が何個あるかを取得する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class CountLeftRight<T> { public int LeftCount(int idx, T t) { if (!ToInt.ContainsKey(t)) return 0; int i = ToInt[t]; return Lefts[idx][i]; } public int RightCount(int idx, T t) { if (!ToInt.ContainsKey(t)) return 0; int i = ToInt[t]; return Rights[idx][i]; } } |
使ってみる
問題の趣旨
最大長20万文字の文字列がひとつ与えられる。
ここから3文字抜き出して回文をつくりたい。
回文は文字を抜き出す位置が異なれば別物とみなす。
3つの要素のうち真ん中の要素S[j]を固定した場合、S[i]とS[k]が同じになるような組み合わせの数を数えればこれが解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Program { static void Main() { char[] S = Console.ReadLine().ToArray(); CountLeftRight<char> countLeftRight = new CountLeftRight<char>(S); long ans = 0; char[] uppers = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToArray(); for (int i = 1; i < S.Length - 1; i++) { for (int c = 0; c < uppers.Length; c++) { long v = 1L * countLeftRight.LeftCount(i, uppers[c]) * countLeftRight.RightCount(i, uppers[c]); ans += v; } } Console.WriteLine(ans); } } |
