AtCoder NoviStepsを埋めてみる(16) 集合（set）の続きです。今回は 連想配列（map）の問題です。C#にはキーと値のペアを格納するデータ構造である Dictionary があり、連想配列に似た操作ができます。
Contents
C – Poll
問題の概要
N 個の文字列が与えられる。
回数が最も多い文字列をすべて辞書順で小さい順に出力せよ。
Dictionary で出現回数を数え、もっとも回数が多かったものと同じ回数の文字列を取得してソートして出力するだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i < N; i++) { string s = Console.ReadLine(); if (!dic.ContainsKey(s)) dic.Add(s, 0); dic[s]++; } int max = dic.Max(_ => _.Value); string[] ans = dic.Where(_ => _.Value == max).Select(_ => _.Key).OrderBy(_ => _).ToArray(); foreach (string s in ans) Console.WriteLine(s); } } |
D – Diversity of Scores
問題の概要
長さ N の配列 X があり、最初はすべての要素が 0 である。
T 回にわたって X[A[i]] が B[i] だけ増加する。
各更新が終わったときに配列内に何種類の値が現れるか出力せよ。
Dictionary でどの値が何個あるかを持つようにすれば TLE することなく AC できます。
|
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 |
class Program { static void Main() { int[] nt = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nt[0]; int T = nt[1]; long[] X = new long[N]; Dictionary<long, int> dic = new Dictionary<long, int>(); dic.Add(0, N); for (int i = 0; i < T; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1]; dic[X[a]]--; if (dic[X[a]] == 0) dic.Remove(X[a]); X[a] += b; if(!dic.ContainsKey(X[a])) dic.Add(X[a], 0); dic[X[a]]++; Console.WriteLine(dic.Count); } } } |
C – Colorful Candies
|
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 |
class Program { static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int K = nk[1]; int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Dictionary<long, int> dic = new Dictionary<long, int>(); Queue<int> q = new Queue<int>(); int ans = 0; foreach (int c in C) { q.Enqueue(c); if(!dic.ContainsKey(c)) dic.Add(c, 0); dic[c]++; if (q.Count == K) { ans = Math.Max(ans, dic.Count); int v = q.Dequeue(); dic[v]--; if(dic[v] == 0) dic.Remove(v); } } Console.WriteLine(ans); } } |
A – Zero-Sum Ranges
問題の概要
長さ N の整数列 A が与えられる。
A の 空でない 連続する 部分列であって、その総和が 0 になるものの個数を求めよ。
累積和（A[0] から A[i] までの総和を sums[i + 1] とする）を考えます。sums[b] – sums[a] = 0 (b > a) であれば A[a + 1] から A[b] までの総和は 0 です。なので sums[i] = x となる i の個数 cnt[x] を数えます。cnt[x] * (cnt[x] – 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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; Dictionary<long, int> dic = new Dictionary<long, int>(); foreach (long v in sums) { if (!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } long ans = 0; foreach (var pair in dic) { long cnt = pair.Value; ans += cnt * (cnt - 1) / 2; } Console.WriteLine(ans); } } |
D – Count Interval
長さ N の数列 A と 整数 K が与えられる。
A の連続部分列のうち、要素の和が K になるものはいくつあるか求めよ。
A – Zero-Sum Ranges と似ていますが、今回は K = 0 とは限りません。
この場合も累積和を使えばよいです。sums[a] = x であれば b > a かつ a sums[b] = x + K を満たす b の個数を数えることになります。dic に x の個数を格納して a に相当するデータを取り除きながら数えればよいです。
|
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 |
class Program { static void Main() { long[] nk = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long N = nk[0]; long K = nk[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; Dictionary<long, int> dic = new Dictionary<long, int>(); foreach (long v in sums) { if (!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } long ans = 0; // sums[i] + K == sums[j] となる j の個数を数えるが // i < j という条件があるので i 以下のものは dic から取り除く foreach (long v in sums) { dic[v]--; if (dic[v] == 0) dic.Remove(v); if(dic.ContainsKey(v + K)) ans += dic[v + K]; } Console.WriteLine(ans); } } |
D – Kadomatsu Subsequence
問題の概要
長さ N の整数列 A が与えられる。
以下をすべて満たす整数の 3 つ組 (i, j, k) がいくつあるか求めよ。
(条件 1) A[i] : A[j] : A[k] = 7 : 5 : 3
(条件 2) min(i, j, k) = j または max(i, j, k) = j
min(i, j, k) = j のものを探す方法を考えます。j < i, k という条件で A[i] : A[j] : A[k] = 7 : 5 : 3 となるものを探します。そのためには dic に A[i] の値と出現回数を格納して、i に相当する値を削除してから (条件 1) を満たすものの個数を数えればよいです。max(i, j, k) = j のものを数えるときは A を反転して同じようなことをすればよいです。
|
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 |
class Program { static void Main() { long N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Dictionary<long, int> dic1 = new Dictionary<long, int>(); Dictionary<long, int> dic2 = new Dictionary<long, int>(); foreach (long v in A) { if (!dic1.ContainsKey(v)) { dic1.Add(v, 0); dic2.Add(v, 0); } dic1[v]++; dic2[v]++; } long ans = 0; foreach (long v in A) { dic1[v]--; if (dic1[v] == 0) dic1.Remove(v); if ((v * 3) % 5 == 0 && (v * 7) % 5 == 0) { long tar1 = v * 3 / 5; long tar2 = v * 7 / 5; if (dic1.ContainsKey(tar1) && dic1.ContainsKey(tar2)) ans += 1L * dic1[tar1] * dic1[tar2]; } } Array.Reverse(A); foreach (long v in A) { dic2[v]--; if (dic2[v] == 0) dic2.Remove(v); if ((v * 3) % 5 == 0 && (v * 7) % 5 == 0) { long tar1 = v * 3 / 5; long tar2 = v * 7 / 5; if (dic2.ContainsKey(tar1) && dic2.ContainsKey(tar2)) ans += 1L * dic2[tar1] * dic2[tar2]; } } Console.WriteLine(ans); } } |
E – This Message Will Self-Destruct in 5s
E – This Message Will Self-Destruct in 5s
問題の概要
N 人の人がいる。人 i の身長は A[i] である。
「2 人の持つ番号の差の絶対値が、2 人の身長の和に等しい」
このようなペアは何通りあるか求めよ。
i < j とすると求めるものは、j – i = A[i] + A[j] を満たすペアの数です。この条件式を変形すると、i + A[i] = j – A[j] となります。
j – A[j] となる j の個数を数えておき、i + A[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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = new int[N]; int[] C = new int[N]; for (int i = 0; i < N; i++) { B[i] = A[i] + i; C[i] = A[i] - i; } Dictionary<int, int> dic = new Dictionary<int, int>(); foreach (int v in C) { if(!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } long ans = 0; for (int i = 0; i < N; i++) { int key = C[i]; dic[key]--; if (dic.ContainsKey(-B[i])) ans += dic[-B[i]]; } Console.WriteLine(ans); } } |
D – Candy Distribution
問題の概要
長さ N の整数列 A が与えられる。
A の 空でない 連続する 部分列であって、その総和が M の倍数 になるものの個数を求めよ。
M で割った剰余の累積和を考えます。あとは A – Zero-Sum Ranges と同じです。
|
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 |
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(); int[] modSum = new int[N + 1]; for (int i = 0; i < N; i++) { modSum[i + 1] = modSum[i] + A[i]; modSum[i + 1] %= M; } Dictionary<int, int> dic = new Dictionary<int, int>(); foreach (int v in modSum) { if(!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } long ans = 0; foreach (var pair in dic) { long cnt = pair.Value; ans += cnt * (cnt - 1) / 2; } Console.WriteLine(ans); } } |
D – Takahashi’s Solitaire
長さ N の非負整数列 A が与えられる。
最初に A のなかからある値 X を選ぶ。
X または (X + 1) mod M である要素があるなら取り除き、その値で X を更新する。
これを繰り返して A のなかに残された値の総和を最小化したい。最小値を求めよ。
dic で同じ値をひとつにまとめて、Key がつながっている（差が 1）ものをひとつのグループにします。このとき dic のなかに 0 と M – 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 |
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(); long sum1 = 0; Dictionary<int, int> dic = new Dictionary<int, int>(); foreach (int v in A) { if(!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; sum1 += v; } var pairs = dic.OrderBy(_ => _.Key).ToArray(); List<List<int>> keyGroups = new List<List<int>>(); List<int> cur = new List<int>(); int prev = -2; foreach (var pair in pairs) { if (pair.Key == prev + 1) cur.Add(pair.Key); else { cur = new List<int>(); cur.Add(pair.Key); keyGroups.Add(cur); } prev = pair.Key; } if (keyGroups.Count >= 2 && dic.ContainsKey(0) && dic.ContainsKey(M - 1)) { keyGroups.Last().AddRange(keyGroups.First()); keyGroups.RemoveAt(0); } long ans = long.MaxValue; foreach (var group in keyGroups) { long sum2 = 0; foreach (var key in group) sum2 += 1L * key * dic[key]; ans = Math.Min(ans, sum1 - sum2); } Console.WriteLine(ans); } } |
A – 碁石ならべ 2 (Stone Arranging 2)
A – 碁石ならべ 2 (Stone Arranging 2)
問題の概要
碁石を左から右へ順番に並べる。
途中でそれよりも左にある碁石で同じ色のものがある場合、そのあいだにある碁石はすべてその色で塗り替える。
すべての操作を行った後の碁石の色をそれぞれ出力せよ。
同じ色であれば必ずひとつながりの連続した区間になります（飛び地には絶対にならない）。
最後にその色が現れた index を dic に記録しておきます。また Stack に（色、その色がはじまる最初の index、その色が終わる最後の index）を格納していきます。
もし左側に置かれている碁石と同じ色の碁石を置くときは同じ色のものが現れるまで Stack を pop します。そしてその色がはじまる最初と最後の index の情報を更新します。また pop された他の色に関する情報は色が塗り替えられるので dic からも削除します。
最後に Stack に残されている情報から各碁石の色を求めて出力します。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Dictionary<int, int> lastIndex = new Dictionary<int, int>(); Stack<(int color, int start, int end)> stack = new Stack<(int color, int start, int end)> (); for (int i = 0; i < N; i++) { int v = int.Parse(Console.ReadLine()); if (!lastIndex.ContainsKey(v)) { lastIndex.Add(v, i); stack.Push((v, i, i)); } else { while (stack.Peek().color != v) { lastIndex.Remove(stack.Peek().color); stack.Pop(); } var pop = stack.Pop(); stack.Push((v, pop.start, i)); lastIndex[v] = i; } } var tps = stack.ToArray(); int[] ans = new int[N]; foreach (var tp in tps) { for (int i = tp.start; i <= tp.end; i++) ans[i] = tp.color; } foreach (var v in ans) Console.WriteLine(v); } } |
origami – 折り紙 (Origami)
問題の概要
横 a cm，縦 b cm の長方形の台紙がある。この台紙には 1 cm おきに辺に平行になるように縦横に直線が引かれ、全体で a × b 個の一辺 1 cm の正方形の格子ができるように区切られている。
左から x 列目、下から y 行目の格子を (x, y) と表す。
台紙の上に n 枚の長方形の紙を順番に貼っていく。紙を貼る位置は 4 つの整数の組 (p, q, r, s) で指定され、格子 (p, q), (p, s), (r, q), (r, s) が紙の角になるように貼っていく。
紙が最も多く重なっている部分が何枚重ねなのか、またその部分の合計の面積を求めよ。
a × b が大きな値なので二次元配列を定義してシミュレーションすることができません。座圧して最も紙が厚くなっている部分を調べます。
|
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 74 75 76 77 78 79 80 81 82 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] wh = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int W = wh[0]; int H = wh[1]; HashSet<int> setX = new HashSet<int>(); HashSet<int> setY = new HashSet<int>(); setX.Add(0); setX.Add(W); setY.Add(0); setY.Add(H); int[] L = new int[N]; int[] B = new int[N]; int[] R = new int[N]; int[] T = new int[N]; for (int i = 0; i < N; i++) { int[] lrrt = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); L[i] = lrrt[0]; B[i] = lrrt[1]; R[i] = lrrt[2]; T[i] = lrrt[3]; setX.Add(L[i]); setX.Add(R[i]); setX.Add(R[i] + 1); setY.Add(B[i]); setY.Add(T[i]); setY.Add(T[i] + 1); } // XY 座標をそれぞれ圧縮する。Key: 圧縮前の座標, Value: 圧縮後の index Dictionary<int, int> xToIndex = new Dictionary<int, int>(); Dictionary<int, int> yToIndex = new Dictionary<int, int>(); int[] arrX = setX.OrderBy(_ => _).ToArray(); int[] arrY = setY.OrderBy(_ => _).ToArray(); for (int i = 0; i < arrX.Length; i++) xToIndex.Add(arrX[i], i); for (int i = 0; i < arrY.Length; i++) yToIndex.Add(arrY[i], i); // 圧縮された格子に紙を貼っていく。被覆された格子点を dic で数える Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i < N; i++) { for (int y = yToIndex[B[i]]; y <= yToIndex[T[i]]; y++) { for (int x = xToIndex[L[i]]; x <= xToIndex[R[i]]; x++) { string key = $"{x},{y}"; if(!dic.ContainsKey(key)) dic.Add(key, 0); dic[key]++; } } } int max = dic.Max(_ => _.Value); // 最大の厚さ var keys = dic.Where(_ => _.Value == max).Select(_ => _.Key).ToArray(); long cnt = 0; foreach (var key in keys) { // 圧縮された格子点から被覆された部分の面積を求める int[] xy = key.Split(',').Select(_ => int.Parse(_)).ToArray(); int x = xy[0]; int y = xy[1]; long w = arrX[x + 1] - arrX[x]; long h = arrY[y + 1] - arrY[y]; cnt += w * h; } Console.WriteLine(max); Console.WriteLine(cnt); } } |
