AtCoder NoviStepsを埋めてみる(17) 連想配列（Dictionary）の続きです。今回も連想配列関連の問題ですが、難しめの問題に挑戦します。
Contents
D – 183183
正整数 N, M と長さ N の正整数列 A が与えられる。
以下の条件を満たす整数の組 (i, j) の個数を求めよ。
(条件)
A[i], A[j] をそれぞれ文字列として解釈しこの順に連結して得られる文字列を S とする。
この S を十進表記の整数として解釈した値が M の倍数である。
A[i] と A[j] から生成される S を十進表記の整数として解釈した値 を x、A[j] の桁数を j_len とすると、x = (A[i] * 10^(j_len) + A[j]) です。x % M = 0 にするのであれば A[i] * 10^n % M (1 ≦ n ≦ 10) をすべて計算しておき、このなかから A[j] に対応するものがあるか調べます。
|
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 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Dictionary<int, int>[] dics = new Dictionary<int, int>[11]; for (int i = 0; i <= 10; i++) dics[i] = new Dictionary<int, int>(); foreach (long v in A) { for (int i = 1; i <= 10; i++) { // (v * (long)Math.Pow(10, i)) % M では long 型でもオーバーフローするので注意！ long a = (long)Math.Pow(10, i) % M; int m = (int)((v * a) % M); if (!dics[i].ContainsKey(m)) dics[i].Add(m, 0); dics[i][m]++; } } long ans = 0; foreach (int v in A) { int len = v.ToString().Length; int m = M - v % M; m %= M; if (dics[len].ContainsKey(m)) ans += dics[len][m]; } Console.WriteLine(ans); } } |
D – A Piece of Cake
問題の概要
幅W 高さ H の長方形のケーキがあります。
ケーキには N 個のイチゴが載っており、i 番目のイチゴの座標は (P[i], Q[i]) である。
X 座標が X[i] で y 軸に並行な直線のそれぞれにそってケーキを切る。
Y 座標が Y[i] で x 軸に並行な直線のそれぞれにそってケーキを切る。
切り分けたピースに載っているイチゴの個数としてあり得る最小値と最大値をそれぞれ出力せよ。
ただし、複数のイチゴが同一の座標にあることはないし、ピースの縁となる位置にはイチゴが存在することもない。
各イチゴがどのピース上に乗るかを求めます。そのために以下の処理をおこないます。
X に 0 と W, Y に 0 と H を追加してソートする。
二分探索法で p < X[idx1], q < Y[idx2] をみたす最大の idx1, idx2 を求める。
あとは idx1,idx2 を key にして dic にデータを格納していきます。dic に格納されたデータのうち Value が最も大きいものが最大値です。最小値はすべてのピースにイチゴが乗っているのであれば Value の最小値をとればいいですが、イチゴが乗っていないピースがひとつでもある場合は 0 です。これは 1L * (X.Count – 1) * (Y.Count – 1) == dic.Count かどうかで判定できます。
二分探索ではライブラリ ac-library-csharp の StlFunction.BinarySearch を使っています。
|
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
using AtCoder; class Program { static void Main() { int[] wh = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int W = wh[0]; int H = wh[1]; int N = int.Parse(Console.ReadLine()); int[] P = new int[N]; int[] Q = new int[N]; for (int i = 0; i < N; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int p = xy[0]; int q = xy[1]; P[i] = p; Q[i] = q; } int A = int.Parse(Console.ReadLine()); List<int> X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList(); X.Add(0); X.Add(W); X = X.OrderBy(_ => _).ToList(); int B = int.Parse(Console.ReadLine()); List<int> Y = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList(); Y.Add(0); Y.Add(H); Y = Y.OrderBy(_ => _).ToList(); Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i < N; i++) { int p = P[i]; int q = Q[i]; int ok = 0; int ng = X.Count; int x_idx = StlFunction.BinarySearch(ok, ng, mid => X[mid] < p); ok = 0; ng = Y.Count; int y_idx = StlFunction.BinarySearch(ok, ng, mid => Y[mid] < q); string key = $"{x_idx},{y_idx}"; if(!dic.ContainsKey(key)) dic.Add(key, 0); dic[key]++; } int max = dic.Max(_ => _.Value); int min = 1L * (X.Count - 1) * (Y.Count - 1) - dic.Count == 0 ? dic.Min(_ => _.Value) : 0; Console.WriteLine($"{min} {max}"); } } |
C13 – Select 2
問題の概要
長さ N の非負整数列 A が与えられる。
相異なる要素を選んで積を 1000000007 で割った余りが P になる選び方はいくつあるか求めよ。
dic に A の値を格納しておき、A[i] を取り除いたあとに (A[i] * x) % 1000000007 == P となる x の数を数えればよいです。x を求めるとき P / A[i] だと正確な値を求めることができません。割り算ができないので 逆元を求めてこれを掛けることで対応します。また A[i] == 0 && P == 0 の場合は何を掛けてもよいのでその場合は別の処理（解に N – i – 1 を加算すればよい）が必要です。
|
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
class Program { // 逆元を求める static long Inverse(long a, long mod) { if (a < 0) a += mod; long b = mod, u = 1, v = 0; while (b > 0) { long t = a / b; a -= t * b; swap(ref a, ref b); u -= t * v; swap(ref u, ref v); } u %= mod; if (u < 0) u += mod; return u; void swap(ref long a, ref long b) { long c = a; a = b; b = c; } } static void Main() { int[] np = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = np[0]; int P = np[1]; long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long mod = 1000000007; for (int i = 0; i < N; i++) A[i] = A[i] % mod; Dictionary<long, int> dic = new Dictionary<long, int>(); foreach (long v in A) { if(!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } long ans = 0; for (int i = 0; i < N; i++) { long v = A[i]; dic[v]--; if (dic[v] == 0) dic.Remove(v); // v == 0 && P == 0 ならこれより右にある数なら何でもよい if (v == 0 && P == 0) { ans += N - i - 1; continue; } // mod では P ÷ v という計算はできないので逆元を掛ける long tar = (P * Inverse(v, mod)) % mod; if (dic.ContainsKey(tar)) ans += (dic[tar]); } Console.WriteLine(ans); } } |
H – JOIOJI
問題の概要
J，O，I のみで構成される 長さ N の文字列が与えられる。
J，O，I がそれぞれちょうど同じ数ずつ入ったもののうち最長の連続部分文字列の長さを求めよ。
J, O, I の出現回数の累積和を取り、これを配列 J, O, I (idx == 0 は番兵。つねに 0) で表します。
J[i] – J[j] == O[i] – O[j] == I[i] – I[j] となる i, j がわかればよいのですが、3 つだと難しいので J に対する相対値を考えます。O, I をそれぞれ O[i] = O[i] – J[i], I[i] = I[i] – J[i] と変更します。
すると(O[i], I[i]) == (O[j], I[j]) となる 半開区間 [i, j) が J, O, I の出現回数が同じ連続部分文字列の区間になるので、そのなかで一番差が大きな値になるものを出力します。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] S = Console.ReadLine().ToArray(); // 各文字の出現回数の累積和 int[] J = new int[N + 1]; int[] O = new int[N + 1]; int[] I = new int[N + 1]; for (int i = 0; i < N; i++) { J[i + 1] = J[i] + (S[i] == 'J' ? 1 : 0); O[i + 1] = O[i] + (S[i] == 'O' ? 1 : 0); I[i + 1] = I[i] + (S[i] == 'I' ? 1 : 0); } // 累積和の相対値 for (int i = 0; i < J.Length; i++) { O[i] -= J[i]; I[i] -= J[i]; } // 相対値が同じになる (i, j) のペアを求める Dictionary<string, List<int>> dic = new Dictionary<string, List<int>>(); for (int i = 0; i < J.Length; i++) { string key = $"{O[i]},{I[i]}"; if(!dic.ContainsKey(key)) dic.Add(key, new List<int>()); dic[key].Add(i); } int ans = 0; foreach (var pair in dic) { int len = pair.Value.Max() - pair.Value.Min(); ans = Math.Max(ans, len); } Console.WriteLine(ans); } } |
E – Unbalanced ABC Substrings
問題の概要
A, B, C の 3 種類の文字のみからなる長さ N の文字列 S が与えられる。
S の空でない連続部分文字列のなかで A, B, C の出現回数が相異なるものの個数を求めよ。
A, B, C の出現回数が相異なるものの個数は、連続部分文字列の選び方（N * (N + 1) / 2）から以下に該当する部分を引けばよいです。注意しなければならないのは ①,②,③ のなかには ④の場合も含まれていることです。
① A, B の出現回数が同じになる選び方
② B, C の出現回数が同じになる選び方
③ C, A の出現回数が同じになる選び方
④ A, B, C の出現回数が同じになる選び方
包除原理より（N * (N + 1) / 2）- ① – ② – ③ + (④ * 2) が求める値です。
A, B, C の出現回数が同じになる選び方の個数は H – JOIOJI と同じ方法で求めることができます。2つの文字が同じになる個数を求めるには i 番目までに出現した x の個数 – y の個数 が同じになる i の個数 (cnt) を数えることで求められます。cnt * (cnt – 1) / 2 の総和を計算すればよいです。
|
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] S = Console.ReadLine().ToArray(); int[] A = new int[N + 1]; int[] B = new int[N + 1]; int[] C = new int[N + 1]; for (int i = 0; i < N; i++) { A[i + 1] = A[i] + (S[i] == 'A' ? 1 : 0); B[i + 1] = B[i] + (S[i] == 'B' ? 1 : 0); C[i + 1] = C[i] + (S[i] == 'C' ? 1 : 0); } long ans = 1L * N * (N + 1) / 2; ans -= F(A, B); ans -= F(B, C); ans -= F(C, A); long g = G(); ans += G() * 2; Console.WriteLine(ans); long F(int[] s, int[] t) { Dictionary<int, int> dic = new Dictionary<int, int>(); for (int i = 0; i <= N; i++) { int v = s[i] - t[i]; if (!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } long res = 0; foreach (var pair in dic) { long cnt = pair.Value; res += cnt * (cnt - 1) / 2; } return res; } long G() { Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i <= N; i++) { string key = $"{B[i] - A[i]},{C[i] - A[i]}"; if (!dic.ContainsKey(key)) dic.Add(key, 0); dic[key]++; } long res = 0; foreach (var pair in dic) { long cnt = pair.Value; res += cnt * (cnt - 1) / 2; } return res; } } } |
E – Rem of Sum is Num
問題の概要
長さ N の正整数列 A と正の整数 K が与えられる。
A の空でない連続部分列であって、要素の和を K で割った余りが要素の数と等しくなるものの数を求めよ。
まず剰余の累積和をとります。S[j] – S[i] を K で割った余りが j – i に一致するということは
S[j] – S[i] ≡ j – i (mod K) であり、
⇔ S[i] – i ≡ S[j] – j (mod K) なので
(S[x] – x) % K の値が同じになる（i, j）が何組できるかを数えます。ただし (S[x] – x) % K < K なので j – i < K が条件です。
以下のコードでは区間の数え上げは尺取法でおこなっています。
|
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 45 46 47 48 49 50 51 |
class Program { static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int K = nk[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] sums = new int[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = (sums[i] + A[i]) % K; for (int i = 0; i <= N; i++) { sums[i] -= i; sums[i] %= K; if (sums[i] < 0) sums[i] += K; } Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>(); for (int i = 0; i < sums.Length; i++) { int v = sums[i]; if (!dic.ContainsKey(v)) dic.Add(v, new List<int>()); dic[v].Add(i); } long ans = 0; foreach (var pair in dic) { List<int> list = pair.Value; int right = 0; for (int left = 0; left < list.Count; left++) { if (right == left) right++; while (right < list.Count && list[right] - list[left] < K) right++; ans += right - left - 1; // left も right も含まない開区間なので -1 する } } Console.WriteLine(ans); } } |
