AtCoder NoviStepsを埋めてみる(2) 貪欲法 2Q問題の続きです。ちょっと難しめの問題を考えます。
Contents
- 1 E – Divide Graph
- 2 D – Match, Mod, Minimize 2
- 3 E – Simultaneous Kagamimochi
- 4 E – Takahashi is Slime 2
- 5 C – Socks 2
- 6 E – Takahashi Quest
- 7 D – Printing Machine
- 8 F – Vouchers
- 9 D – Bitmask
- 10 E – Red and Green Apples
- 11 D – Summer Vacation
- 12 D – Patisserie ABC
- 13 B – Sum AND Subarrays
- 14 C – Different Strokes
- 15 A – DEGwer’s Doctoral Dissertation
- 16 B – 展覧会 (Exhibition)
- 17 I – Maximize Array
- 18 C – 辞書式順序ふたたび
- 19 E – Amusement Park
- 20 C – Align
E – Divide Graph
問題の概要
N 頂点 M 辺からなる単純連結無向グラフ G が与えられる。
辺 i は頂点 U[i] と頂点 V[i] を結んでいて辺の重みは 2 の i乗 である。
G の連結成分の個数がちょうど 2 になるように、G の辺のうちいくつかを選んで削除する。
そのとき削除される辺の重みの総和の最小値は？ 998244353 で割ったときの余りを答えよ。
辺のないグラフを構築して辺の重みが大きい順に辺をつないでいきます。ただし辺を繋ぐことで全体が連結になってしまう場合はその辺は繋ぎません。この処理は UnionFind木を使えばできます。
辺の重みは 2 の i乗 なので、辺 i の重みは i – 1 番目以前のすべての辺の重みの総和よりも大きいです。なので上記の方法で正しい解を得ることができます。
Dsuクラスは ac-library-csharp のものを使っています。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); int[] U = new int[M]; int[] V = new int[M]; for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; U[i] = u; V[i] = v; } Dsu dsu = new Dsu(N); HashSet<int> set = new HashSet<int>(); for (int i = M - 1; i >= 0; i--) { int u = U[i]; int v = V[i]; if (!dsu.Same(u, v)) // 2つの頂点が同一連結成分にないなら... { // 連結前の連結成分の大きさの和が N になるのであれば、 // 連結することで連結成分数が 1 になってしまう // この場合は削除する辺なので指数をSetに格納する // そうでないならそのまま辺を繋ぐ if (dsu.Size(u) + dsu.Size(v) == N) set.Add(i + 1); else dsu.Merge(u, v); } } long temp = 1; long ans = 0; long mod = 998244353; // 2 の i乗 を順次求めて必要であれば加算していく // 2 の i乗 の総和を mod で割った余りは // (2 の i乗 を mod で割った余りの総和) を mod で割った余りと考えてよい for (int i = 1; i <= M; i++) { temp *= 2; temp %= mod; if (set.Contains(i)) ans += temp; } Console.WriteLine(ans % mod); } } |
D – Match, Mod, Minimize 2
長さ N の非負整数列 A, B と 正整数 M が与えられる。
A をならべかえて (A[i] + B[i]) Mod M の総和を最小化したい。
最小値はなにか？
Mod M を考慮しなくてよいのであればどのように並べ替えても総和は変わりません。また A[i], B[i] は M 未満なので A[i] + B[i] が M を超えることはあってもその 2 倍を超えることはありません。
A[i] + B[i] が M を超えることで M だけ総和が減少します。この問題は
長さ N の非負整数列 A, B と 正整数 M が与えられる。
A をならべかえて (A[i] + B[i]) ≧ M となるペアをできるだけたくさん作りたい。
この個数は？
という問題を解ければ解くことができます。
|
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 |
class Program { static void Main() { int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long[] B = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long ans = Solve(N, M, A, B); Console.WriteLine(ans); } long Solve(int N, int M, long[] A, long[] B) { A = A.OrderBy(_ => _).ToArray(); Queue<long> qB = new Queue<long>(B.OrderByDescending(_ => _)); long cnt = 0; foreach (long v in A) { if (qB.Count > 0 && qB.Peek() + v >= M) { qB.Dequeue(); cnt++; } } return A.Sum() + B.Sum() - M * cnt; } } } |
E – Simultaneous Kagamimochi
長さ N の整数列 A が与えられる。すべての要素が 1 以上であり、すでに昇順でソートされている。
A[i] * 2 ≦ A[j] となるペアをできるだけたくさん作りたい。
ぜんぶでいくつできるだろうか？
A[0] とペアにできるもので最小であるものを探し、次にペアとなっていない最小のものから…と同じことを繰り返すのは残念ですが、嘘解法です。
以下のコードでは出題ページにある 3 つの入出力例 では正しい解を返しますが、提出してみると WA になります。
嘘解法
|
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 |
class Program { class Mochi { public Mochi(int v) { V = v; } public int V = 0; public bool Done = false; } static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); List<Mochi> M = new List<Mochi>(); foreach (int v in A) M.Add(new Mochi(v)); int ans = 0; int bottom_idx = 0; foreach (var top in M) { if (top.Done) continue; for (int i = bottom_idx; i < N; i++) { bottom_idx = i + 1; if (!M[i].Done && top.V * 2 <= M[i].V) { top.Done = true; M[i].Done = true; ans++; break; } } } Console.WriteLine(ans); } } |
正しい解法は以下のとおりです。
K 個のペアが作れるときは 上位 K 個 と下位 K 個を組み合わせればできる。
K の最大値が問題の解なので、これを二分探索法で探す。
二分探索法の処理は 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 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); int ok = 0; int ng = N / 2 + 1; int ans = StlFunction.BinarySearch(ok, ng, mid => Check(mid)); Console.WriteLine(ans); // 上位 K 個 と下位 K 個を組み合わせてペアをつくることができるか調べる bool Check(int k) { if (k * 2 > N) return false; // N に対して作ろうとしているペアが多すぎる。できるわけがない。 for (int i = 0; i < k; i++) { if (A[i] * 2 > A[N - k + i]) return false; } return true; } } } |
E – Takahashi is Slime 2
問題の概要
縦 H 行横 W 列のマス目があり、マス(i,j) には強さ S[i, j] のスライムがいる。
マス(P,Q) にいるスライムは自身の強さの 1 / X 倍未満のものを選んで吸収し、その強さだけ強くなる。
また吸収されたスライムがいた部分は吸収したスライムによって埋められる。
このような処理を繰り返した場合、最初にマス(P, Q)にいたスライムの強さの最大値はどうなるだろうか？
一度接したスライムは吸収しない限り接し続けることと、自身の強さが減少することはないことから、吸収できるスライムはすべて吸収してしまってかまいません。このような処理は接しているスライムのうち、最も強さの小さいスライムを吸収し続けることで実現できます。PriorityQueue を使いましょう。
注意点として 一度 PriorityQueue に格納したマスは再度格納してはならないことと、自身の強さの 1 / X 倍未満かどうかを判定するときにそのまま割り算してしまうと誤差で WA になる場合があることです。
long a = 9007199254740993;
long b = 16384;
long c = 549755813888;
このとき 1.0 * a / b を計算すると c と一致しますが、実は両者は同じではありません。両辺に b を掛けてから a と c * b を比較すると 1 違うことがわかります。
なので割り算ではなく掛け算で比較します。このとき乗算に伴うオーバーフローが予想されますが、すべてのスライムの強さの総和は Math.Pow(10, 18) を超えないので、吸収できるか判定対象となるスライムの強さ × X が Math.Pow(10, 18) を超える場合は吸収できないことがわかります。
|
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 83 84 85 86 87 88 89 90 91 92 93 |
using System.Diagnostics; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } long[] ReadLongArray() => Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); (int H, int W, int X) = ReadInt3(); (int P, int Q) = ReadInt2(); P--; Q--; long[,] grid = new long[H, W]; for (int r = 0; r < H; r++) { long[] vs = ReadLongArray(); for (int c = 0; c < W; c++) grid[r, c] = vs[c]; } // 周囲のマスを取得する List<(int, int)> GetNexts(int r, int c) { List<(int, int)> res = new List<(int, int)>(); if (r > 0) res.Add((r - 1, c)); if (r < H - 1) res.Add((r + 1, c)); if (c > 0) res.Add((r, c - 1)); if (c < W - 1) res.Add((r, c + 1)); return res; } // マスの位置から一意の文字列を取得する（同じマスを何度も PriorityQueue に格納させないため） string GetKey(int r, int c) => $"{r},{c}"; PriorityQueue<(int, int), long> pq = new PriorityQueue<(int, int), long>(); long ans = grid[P, Q]; HashSet<string> set = new HashSet<string>(); set.Add(GetKey(P, Q)); var nexts = GetNexts(P, Q); foreach (var next in nexts) { pq.Enqueue((next.Item1, next.Item2), grid[next.Item1, next.Item2]); set.Add(GetKey(next.Item1, next.Item2)); } while (pq.Count > 0) { var cur = pq.Dequeue(); // 除算に伴う誤差で落ちるケースがある // if (grid[cur.Item1, cur.Item2] >= (double)ans / X) // break; // 両辺に X を掛けて比較する // grid の値をすべて足しても Math.Pow(10, 18)を超えることはないので // 超えてしまう場合は条件を満たさない。 if (1.0 * grid[cur.Item1, cur.Item2] * X > Math.Pow(10, 18)) break; if (grid[cur.Item1, cur.Item2] * X >= ans) break; ans += grid[cur.Item1, cur.Item2]; nexts = GetNexts(cur.Item1, cur.Item2); foreach (var next in nexts) { if (!set.Contains(GetKey(next.Item1, next.Item2))) { pq.Enqueue((next.Item1, next.Item2), grid[next.Item1, next.Item2]); set.Add(GetKey(next.Item1, next.Item2)); } } } Console.WriteLine(ans); } } |
C – Socks 2
問題の概要
i 番目の組は色 i の靴下 2 枚からなる N 組の靴下がある。
配列 A で与えられる色の靴下を 1 枚ずつなくしてしまった。
残りの靴下でペアを作りたいが 2 枚の色の差の総和ができるだけ小さくなるようにしたい。
差の総和の最小値は？ 残りの靴下が奇数枚の場合、1枚は使われることはない。
残りの靴下の色が格納されている昇順でソートされた配列 B をつくります（同じ色が 2 枚ある場合は同じ値を 2 回格納する）。
B の長さが偶数の場合は隣り合う要素の差の総和を計算すればそれが解となります。奇数の場合はどれか 1 枚を除外して同じように差の総和を計算すればいいのですが、この処理はどうやって高速化すればいいでしょうか？
まず先頭から隣り合う要素の差を計算して、その累積和を計算します。次に後方からも同じように後方からの累積和を計算します。あとは両者の組み合わせから 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int K) = ReadInt2(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); HashSet<int> set = new HashSet<int>(A); List<int> B = new List<int>(); for (int i = 1; i <= N; i++) { B.Add(i); if (!set.Contains(i)) B.Add(i); } if (B.Count % 2 == 0) { long ans = 0; for (int i = 0; i < B.Count; i += 2) ans += B[i + 1] - B[i]; Console.WriteLine(ans); } else { // 先頭からの差の累積和 List<long> sums1 = new List<long>(); sums1.Add(0); for (int i = 0; i + 1 < B.Count; i += 2) sums1.Add(sums1.Last() + B[i + 1] - B[i]); // 最後尾からの差の累積和 List<long> sums2 = new List<long>(); sums2.Add(0); for (int i = B.Count - 1; i - 1 >= 0; i -= 2) sums2.Add(sums2.Last() + B[i] - B[i - 1]); sums2.Reverse(); long ans = long.MaxValue; for (int i = 0; i < sums1.Count; i++) ans = Math.Min(ans, sums1[i] + sums2[i]); Console.WriteLine(ans); } } } |
E – Takahashi Quest
問題の概要
N 個の出来事がおきる。
t[i] = 1 のとき、タイプ x[i] のポーションを 1 つ発見する。
このときはこれを拾うか何もしないかの選択をする。
t[i] = 2 のとき、タイプ x[i] の敵と遭遇する。
もしタイプ x[i] のポーションを持っている場合、それを 1 つ消費することで敵を倒すことができる。
持っていない場合は敵に敗北する。
すべての敵を倒すことはできるだろうか？ できない場合は -1 を出力せよ。
できる場合は途中で持っているポーションの個数の最大値 K を最小化しようとしたとき、その値は何になるだろうか？ また t[i] = 1 のすべてのときにポーションを拾うかどうかについて出力せよ。
ポーションを見つけたとき、それを使用するかどうかはそのときにはわかりません。そこで敵に遭遇したときに過去に遡って必要なポーションを見つけたときはこれを手に入れるようにします。また手持ちのポーションは少ないほうがよいので過去に遡るときは現在に一番近い時間にします。
各種類のポーションをみつけた時刻をスタックに格納すれば、現在にもっとも近い時間がわかります。各時間においてポーションの増減を記録する配列（ポーションを拾う：1, ポーションを使う：-1, なにもしない：0）を用意しておくとそこから所持するポーションの最大値を計算することができます。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Stack<int>[] stacks = new Stack<int>[N]; for (int i = 0; i < N; i++) stacks[i] = new Stack<int>(); int[] T = new int[N]; int[] X = new int[N]; for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); T[i] = int.Parse(vs[0]); X[i] = int.Parse(vs[1]) - 1; } int[] diffs = new int[N]; for (int i = 0; i < N; i++) { int t = T[i]; int x = X[i]; if (t == 1) stacks[x].Push(i); if (t == 2) { if (stacks[x].Count > 0) { int pop = stacks[x].Pop(); diffs[pop] = 1; // ポーションを拾うべき時刻 diffs[i] = -1; // いま使ったので -1 } else { Console.WriteLine(-1); return; } } } int K = 0; int cnt = 0; for (int i = 0; i < N; i++) { cnt += diffs[i]; K = Math.Max(K, cnt); } // タイプ 1 のクエリのときだけなので負数が格納されている要素は不要 diffs = diffs.Where(_ => _ >= 0).ToArray(); Console.WriteLine(K); Console.WriteLine(string.Join(" ", diffs)); } } |
D – Printing Machine
問題の概要
N 個の商品がベルトコンベア上を流れている。ベルトコンベアには印字機が取り付けられており、商品 i は今から T[i] μs後に印字機の範囲に入り、その D[i] μs後に印字機の範囲から出る。
この印字機は、1 μs おきにその範囲内にある商品 1 つに一瞬で印字ができる（印字機の範囲に入る瞬間や範囲から出る瞬間を含む）。この印字機は最大で何個の商品に印字することができるだろうか？
印字機の範囲内に複数の商品がある場合、範囲外へ出る時刻が迫っているものから印字すべきです。そこでそのようなシミュレーションをおこないます。T の範囲が最大で 10^18, 印字機の範囲内にある時間も 10^18 ですが、印字機の範囲内に商品がない場合は時刻を先に進めてしまえばシミュレーション可能です。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); // 入る時刻が同じものをまとめる Dictionary<long, List<long>> dic = new Dictionary<long, List<long>>(); for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); long s = long.Parse(vs[0]); long t = s + long.Parse(vs[1]); if(!dic.ContainsKey(s)) dic.Add(s, new List<long>()); dic[s].Add(t); } // 入る時間順に Queue に格納する Queue<KeyValuePair<long, List<long>>> q = new Queue<KeyValuePair<long, List<long>>>(dic.OrderBy(_ => _.Key)); // 印字機の範囲内に入ったものを出る時刻が早い順に格納する PriorityQueue<long, long> pq = new PriorityQueue<long, long>(); int ans = 0; long t_max = (long)Math.Pow(10, 18) * 2; for (long cur = 0; cur <= t_max; cur++) { // この時刻に範囲内に入る商品がある if (q.Count > 0 && q.Peek().Key == cur) { var vs = q.Dequeue().Value; foreach (var t in vs) pq.Enqueue(t, t); } // 範囲内に商品がないなら範囲内に入る商品が出現する時刻まで現在時刻をすすめる if (pq.Count == 0 && q.Count > 0) { var d = q.Dequeue(); cur = d.Key; var vs = d.Value; foreach (var t in vs) pq.Enqueue(t, t); } // 範囲内にある商品は存在しないし、これから範囲内に入る商品も存在しない（終了） if (pq.Count == 0 && q.Count == 0) break; // すでに印字機の範囲外に出たものは PriorityQueue から取り除く while (pq.Count > 0 && pq.Peek() < cur) pq.Dequeue(); // 印字可能な商品に印字する（印字は1回だけなので PriorityQueue から取り除く） if (pq.Count > 0) { pq.Dequeue(); ans++; } } Console.WriteLine(ans); } } |
F – Vouchers
問題の概要
N 個の商品が売られていて 商品の定価は P[i] 円です。
M 枚のクーポンがあり、i 枚目のクーポンは定価が L[i] 円以上の商品に対して使うことができ、定価より D[i] 円安く買うことができる。
複数の商品に同じクーポンを使ったり、同じ商品に複数のクーポンを使うことはできない。
すべての商品を買うのに必要な最小の金額は？
値段の安い順に商品を見ていき、使えるクーポンがあるならばその中で最も D[i] が大きいクーポンを使用して商品を買えばよいです。PriorityQueue を使えば解けます。
|
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, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] L = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] D = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<(int, int)> vs = new List<(int, int)> (); for (int i = 0; i < N; i++) vs.Add((P[i], 0)); for (int i = 0; i < M; i++) vs.Add((L[i], D[i])); vs = vs.OrderBy(_ => _.Item1).ThenByDescending(_ => _.Item2).ToList(); long minus = 0; PriorityQueue<int, int> pq = new PriorityQueue<int, int>(); foreach (var pair in vs) { if (pair.Item2 > 0) pq.Enqueue(pair.Item2, - pair.Item2); else if(pq.Count > 0) minus += pq.Dequeue(); } long ans = 0; for (int i = 0; i < N; i++) ans += P[i]; Console.WriteLine(ans - minus); } } |
D – Bitmask
問題の概要
0, 1, ? からなる文字列 S および整数 N が与えられる。
S に含まれる ? をそれぞれ 0 または 1 に置き換えて 2 進整数とみなしたときに得られる値であって、N 以下 で最大のものを答えよ。
S と比較できるように N も文字列に変換します（T とする）。そして先頭（2の59乗の位）からみていき、先に 見つけることができるのが S[i] == ‘0’ && T[i] == ‘1’ か S[i] == ‘1’ && T[i] == ‘0’ かで処理を切り分けます。
S[i] == ‘0’ && T[i] == ‘1’ が先に見つかった場合はそれ以降の ‘?’ をすべて ‘1’ にしても S が N を超えることは絶対にありません。最大のものを求めたいので以降はすべて ‘1’ とします。
S[i] == ‘1’ && T[i] == ‘0’ が先に見つかった場合はそれ以降の ‘?’ をすべて ‘0’ にしても S が N を超えてしまいます。これではいけないのでそれより前に S[j] == ‘?’ && T[j] == ‘1’ になっているところを探して S[j] == ‘0’ にします。このような場所が見つからない場合は解は存在しません。見つかった場合は以降の ‘?’ はすべて ‘1’ にしてしまって問題ありません。
上記以前の ‘?’ は T と同じにしてよいです。あとは文字列を整数に変換して解を出力します。
|
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 83 84 85 86 87 88 89 90 |
class Program { static void Main() { // 入力された文字列の先頭に '0' を付加して長さを 60 にする char[] GetS(string s) { int cnt = 60 - s.Length; string zero = ""; for (int i = 0; i < cnt; i++) zero += '0'; return (zero + s).ToArray(); } // 入力された整数を 2 進数に変換して文字の配列を返す char[] ConvertToBinary(long v) { char[] res = new char[60]; for (int i = 0; i < 60; i++) res[i] = ((v >> i) & 1) == 1 ? '1' : '0'; return res.Reverse().ToArray(); } // '0' と '1' の文字の配列を整数に変換する long ConvertToDecimal(char[] s) { char[] clone = (char[])s.Clone(); clone = clone.Reverse().ToArray(); long res = 0; for (int i = 0; i < 60; i++) { if (clone[i] == '1') res += 1L << i; } return res; } char[] S = GetS(Console.ReadLine()); char[] T = ConvertToBinary(long.Parse(Console.ReadLine())); // 先に見つかるのは S[i] == '0' && T[i] == '1' か S[i] == '1' && T[i] == '0' か？ for (int i = 0; i < 60; i++) { if (S[i] == '1' && T[i] == '0') { int start = -1; for (int k = i - 1; k >= 0; k--) { if (S[k] == '?' && T[k] == '1') { S[k] = '0'; start = k; break; } } if (start == -1) { Console.WriteLine(-1); return; } for (int k = start + 1; k < 60; k++) { if (S[k] == '?') S[k] = '1'; } break; } if (S[i] == '0' && T[i] == '1') { for (int k = i + 1; k < 60; k++) { if (S[k] == '?') S[k] = '1'; } break; } } // それ以外の ? は T と同じでよい for (int i = 0; i < 60; i++) { if (S[i] == '?') S[i] = T[i]; } Console.WriteLine(ConvertToDecimal(S)); } } |
E – Red and Green Apples
問題の概要
A個 の赤いりんごがあり i 番目のおいしさは P[i]
B個 の緑色のりんごがあり i 番目のおいしさは Q[i]
C個 の色がついていないりんごがあり i 番目のおいしさは R[i]
A個 の赤いりんごのなかから X 個、B個の緑色のりんごのなかから Y 個を選びたい。
ただし無色のリンゴは着色することで、赤色または緑色のりんごと見なすことができる。
X + Y 個のりんごの美味しさの総和を最大化したとき、その値は何か？
3 色のりんごをおいしい順にソートして X 個の赤いりんごと Y 個の緑色のりんごを選びます。それぞれのなかからおいしさが一番小さいものを無色のりんごを交換します（ただし交換によっておいしさの総和が大きくならなくなったら終了）。
|
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 |
class Program { static void Main() { (int, int, int, int, int) ReadInt5() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2]), int.Parse(vs[3]), int.Parse(vs[4])); } int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int X, int Y, int A, int B, int C) = ReadInt5(); int[] P = ReadIntArray().OrderByDescending(_ => _).ToArray(); int[] Q = ReadIntArray().OrderByDescending(_ => _).ToArray(); int[] R = ReadIntArray().OrderByDescending(_ => _).ToArray(); PriorityQueue<int, int> pqRed = new PriorityQueue<int, int>(); PriorityQueue<int, int> pqGreen = new PriorityQueue<int, int>(); for (int i = 0; i < X; i++) pqRed.Enqueue(P[i], P[i]); for (int i = 0; i < Y; i++) pqGreen.Enqueue(Q[i], Q[i]); foreach (var v in R) { int rMin = pqRed.Peek(); int gMin = pqGreen.Peek(); if (v <= rMin && v <= gMin) break; if (gMin < rMin) { pqGreen.Dequeue(); pqGreen.Enqueue(v, v); } else { pqRed.Dequeue(); pqRed.Enqueue(v, v); } } long ans = 0; while (pqRed.Count > 0) ans += pqRed.Dequeue(); while (pqGreen.Count > 0) ans += pqGreen.Dequeue(); Console.WriteLine(ans); } } |
D – Summer Vacation
問題の概要
N 件の日雇いアルバイトがあり、i 件目の日雇いアルバイトを請けて働くと、その A[i] 日後に報酬 B[i] が得られる。毎日 1 日 1 件まで選んで働くことができるが、同じものを複数回選ぶことはできない。
今日から M 日後まで(M 日後を含む)に得られる報酬の合計の最大値は？
M 日を過ぎてしまったものは数えることができないので、報酬をもらえる日が M 日に近いものから選んでいきます。M 日への近さが同じ場合は報酬が大きい順に選びます。
時間の経過を逆順にして、PriorityQueue に M 日後が翌日(A[i] == 1)の仕事、A[i] == 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>(); for (int i = 0; i < N; i++) { (int a, int b) = ReadInt2(); if (!dic.ContainsKey(a)) dic.Add(a, new List<int>()); dic[a].Add(b); } long ans = 0; PriorityQueue<int, int> pq = new PriorityQueue<int, int>(); for (int d = 1; d <= M; d++) { if (dic.ContainsKey(d)) { foreach (int v in dic[d]) pq.Enqueue(v, -v); } if(pq.Count > 0) ans += pq.Dequeue(); } Console.WriteLine(ans); } } |
D – Patisserie ABC
N 種類の 綺麗さ X[i], おいしさ Y[i], 人気度 Z[i] （値は 0 以下である場合もある）のケーキが売られている。
ここから M 個のケーキ を選びたいが、(綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるようにしたい。
この場合の最大値は？
すべて正の値なら簡単なのだが負数の場合もあり、総和の絶対値を考えなければなりません。絶対値 |x| とは x と – x の大きい側のことなので、X, Y, Z のそれぞれについてそのままの総和と符号を反転させたものの総和とを計算（全部で 8 パターン）し、一番大きいものをとればよいです。
|
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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (long, long, long) ReadLong3() { string[] vs = Console.ReadLine().Split(); return (long.Parse(vs[0]), long.Parse(vs[1]), long.Parse(vs[2])); } (int N, int M) = ReadInt2(); long[] X = new long[N]; long[] Y = new long[N]; long[] Z = new long[N]; for (int i = 0; i < N; i++) { (long x, long y, long z) = ReadLong3(); X[i] = x; Y[i] = y; Z[i] = z; } long ans = 0; for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { for (int c = 0; c < 2; c++) { List<long> sums = new List<long>(); for (int i = 0; i < N; i++) { long x = a == 0 ? X[i] : -X[i]; long y = b == 0 ? Y[i] : -Y[i]; long z = c == 0 ? Z[i] : -Z[i]; sums.Add(x + y + z); } ans = Math.Max(ans, sums.OrderByDescending(_ => _).Take(M).Sum()); } } } Console.WriteLine(ans); } } |
B – Sum AND Subarrays
長さ N の整数列 A が与えられる。
A のなかには空ではない連続する部分列が N × (N – 1) / 2 個存在するが、そのなかから K 個を選びたい。
K 個の連続部分列の和のビット毎の論理積 (AND) の最大値は何だろうか？
累積和を使えば、N × (N – 1) / 2 個 あるすべての空ではない連続部分列の和を計算することができます。
次に K 個の連続部分列の和のビット毎の論理積の最大値を計算する方法ですが、まず各ビットを上位から見ていきます。
もしその位のビットが立っている値が K 個以上見つかったら解のその位のビットも立っています。そこでそうではないものは解の候補からはずします。もしその位のビットが立っている値が 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 52 53 54 55 56 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } // 累積和からすべての連続部分和の値を取得する List<long> GetSums(int[] arr) { List<long> res = new List<long>(); int len = arr.Length; long[] sums = new long[len + 1]; for (int i = 0; i < len; i++) sums[i + 1] = sums[i] + arr[i]; for (int a = 0; a < len; a++) { for (int b = a; b < len; b++) { long sum = sums[b + 1] - sums[a]; res.Add(sum); } } return res; } (int N, int M) = ReadInt2(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); var sums = GetSums(A); for (int i = 60; i >= 0; i--) { int cnt = 0; List<long> sums2 = new List<long>(); foreach (long sum in sums) { if (((sum >> i) & 1L) == 1) sums2.Add(sum); } if (sums2.Count >= M) // この場合は解の候補を絞り込める sums = sums2; } long ans = sums[0]; for (int i = 1; i < sums.Count; i++) ans &= sums[i]; Console.WriteLine(ans); } } |
C – Different Strokes
問題の概要
長さ N の配列 A, B が与えられる。
高橋くんが料理 i を食べると A[i] の幸福度を得る。青木さんが料理 i を食べると B[i] の幸福度を得る。
彼らが交互に「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選び続けた場合、高橋くんが得る幸福度の総和から青木さんが得る幸福度の総和を引いた値はどうなるのだろうか？
料理 i を食べることで自身は幸福度を得るとともに、相手はその料理を食べることができなくなるので相手の幸福度を奪うことができると考えます。すると料理 i を食べる効果は A[i] + B[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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } int N = int.Parse(Console.ReadLine()); List<(int, int)> pairs = new List<(int, int)> (); for (int i = 0; i < N; i++) { (int a, int b) = ReadInt2(); pairs.Add((a, b)); } pairs = pairs.OrderByDescending(_ => _.Item1 + _.Item2).ToList(); long T = 0; long A = 0; for (int i = 0; i < N; i++) { if (i % 2 == 0) T += pairs[i].Item1; else A += pairs[i].Item2; } Console.WriteLine(T - A); } } |
A – DEGwer’s Doctoral Dissertation
A – DEGwer’s Doctoral Dissertation
問題の概要
N ページからなる論文があり、論文内には K 個の誤植が存在する。
どの連続する T ページにも複数の誤植が存在しないようにしたい。
修正すべき誤植の個数を最小化するとき、その個数は？
与えられる配列 A は i 個目の誤植は何ページ目にあるかを示しているのですが、これを i ページ目に何個 誤植があるかを示す配列 B に変換すると、B の長さ T の連続部分列の和をすべて 1 以下にする問題と読み替えることができます。
この場合は最初の T 個の和が 1 以下になるように値を変更します。B[i + K] を追加して B[i] を引くという操作を繰り返し、必要であれば追加する B[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 52 53 54 55 56 57 58 |
class Program { static void Main() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (int N, int K, int T) = ReadInt3(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = new int[N]; foreach (int v in A) B[v - 1]++; int ans = 0; // B[0] から B[T - 1] までの総和が 1 以下になるように値を更新する（後ろの要素が優先） int head_sum = B.Take(T).Sum(); if (head_sum > 1) { int diff = head_sum - 1; for (int i = T - 1; i >= 0; i--) { if (diff > 0) { int d = Math.Min(diff, B[i]); B[i] -= d; diff -= d; ans += d; if (diff == 0) break; } } } int sum = B.Take(T).Sum(); Queue<int> q = new Queue<int>(); for (int i = 0; i < T; i++) q.Enqueue(B[i]); for (int i = T; i < N; i++) { sum -= q.Dequeue(); int target = sum == 0 ? 1 : 0; q.Enqueue(Math.Min(B[i], target)); sum += Math.Min(B[i], target); if (B[i] > target) ans += B[i] - target; } Console.WriteLine(ans); } } |
B – 展覧会 (Exhibition)
問題の概要
大きさが S[i]，価値は V[i] の絵が N 枚、大きさが C[i] の額縁が M 個ある。
額縁には大きさが C[i] 以下の絵だけを入れることができる。
使用する額縁の大きさが広義単調増加であり、額縁のなかの絵の価値も広義単調増加になっているようにならべたい。
最大で何枚並べることができるだろうか？
額縁の大きさよりも小さな絵であればその額縁に入れることができます。なので問題の解が K であれば使用する額縁は大きさが上位 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); List<(int, int)> P = new List<(int, int)>(); for (int i = 0; i < N; i++) { (int s, int v) = ReadInt2(); P.Add((s, v)); } P = P.OrderByDescending(_ => _.Item2).ThenByDescending(_ => _.Item1).ToList(); Queue<(int, int)> q = new Queue<(int, int)>(P); List<int> C = new List<int>(); for (int i = 0; i < M; i++) { int c = int.Parse(Console.ReadLine()); C.Add(c); } C = C.OrderByDescending(_ => _).ToList(); int ans = 0; foreach (var c in C) { while (q.Count > 0 && c < q.Peek().Item1) q.Dequeue(); if(q.Count > 0) { q.Dequeue(); ans++; } } Console.WriteLine(ans); } } |
I – Maximize Array
問題の概要
長さ N の正整数列 A と正整数 K が与えられる。
A から長さ K の連続部分列を削除する操作を繰り返して（0 回でもよい）辞書順最大の数列を求めよ。
辞書順最大の数列を B とすると、B[0]の候補は A[0], A[K], A[K * 2], A[K * 3], … となります。このなかで値が最大値となるもので添字が最小のものを選ぶとよいです。その添字を i0 とすると B[1] の候補は A[i0 + 1], A[(i0 + 1) + K], A[(i0 + 1) + K * 2], A[(i0 + 1) + K * 3], … となります。
A の後ろから K おきに A の累積 MAX とそのときの 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int K) = ReadInt2(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int, int)[] maxes = new (int, int)[N]; // 後方からの累積 MAX とその添字 for (int first_idx = 0; first_idx < K; first_idx++) { int last_idx = (N - 1 - first_idx) / K * K + first_idx; for (int i = last_idx; i >= first_idx; i -= K) { if (i + K < N && A[i] < maxes[i + K].Item1) maxes[i] = (maxes[i + K].Item1, maxes[i + K].Item2); else maxes[i] = (A[i], i); } } List<int> ans = new List<int>(); int cur_idx = 0; while (cur_idx < N) { ans.Add(maxes[cur_idx].Item1); cur_idx = maxes[cur_idx].Item2 + 1; } Console.WriteLine(string.Join(" ", ans)); } } |
C – 辞書式順序ふたたび
問題の概要
英小文字からなる N 文字の文字列 S が与えられる。
これを並び替えて作れるような文字列 T のうち、以下の条件を満たす辞書順で最小になるようなものを求めよ。
条件：並び替えることで元の位置から変わった文字の個数を K 以下にすること。
辞書順で最小を目指すときには 文字列の先頭にできるだけ小さいアルファベットがある方がよいです。なので最小の文字を探して先頭の文字といれかえます。1文字目が確定したら2文字目以降も2文字目よりあとにある最小の文字を探してこれと入れ替える処理を続けます。
ただし並び替えることで元の位置から変わった文字の個数を 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 52 53 54 55 56 57 58 59 60 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int K) = ReadInt2(); string S = Console.ReadLine(); char[] T = S.ToArray(); // a 文字目と b 文字目を入れ替えても位置が異なる文字が K 個以下であるか確認する bool Check(char[] vs, int a, int b) { char[] clone = (char[] )vs.Clone(); char c = clone[a]; clone[a] = clone[b]; clone[b] = c; string str = new string(clone); int cnt = 0; for (int i = 0; i < N; i++) { if (str[i] != S[i]) cnt++; } return cnt <= K; } for (int i = 0; i < N; i++) { char ch = T[i]; char min_char = T[i]; int min_idx = -1; for (int k = i + 1; k < N; k++) { // 入れ替えの候補がみつかったら本当に入れ替え可能かチェック if (min_char > T[k] && Check(T, i, k)) { min_char = T[k]; min_idx = k; } } // 入れ替えの可能の候補のなかから最小の文字と実際に入れ替える if (min_idx != -1) { char c = T[i]; T[i] = T[min_idx]; T[min_idx] = c; } } Console.WriteLine(new string(T)); } } |
E – Amusement Park
問題の概要
遊園地に N 個のアトラクションがあり、i 個目のアトラクションの「楽しさ」の初期値は A[i] である。
1 回アトラクションに乗るたびに
「満足度」に、i 個目のアトラクションの現在の「楽しさ」が加算される。
i 個目のアトラクションの「楽しさ」が、1 減少する。
アトラクションに合計 K 回まで乗ることができる場合、最終的な「満足度」の最大値は？
K の値が小さいのであれば、「A の要素のうちもっとも大きなものを 解を表す変数 ans に加え、その要素の値を 1 減らす」という処理を K 回 繰り返す（すべての要素が 0 になった場合はその時点で終了）でよいのですが、与えられる K は最大で 2 * 10^9 なのでこの方法は使えません。
A の要素をまとめて引くことはできないかを考えます。
二分探索法で Math.Max(A[i] – m, 0) の総和が K を超えない最小の m である minM を求めます。これによってすべての要素を minM 以上の要素をすべて minM に減らすとともにこれによって得られる満足度を計算することができます。
Math.Max(A[i] – minM, 0) の総和と K の差を計算することで、この状態から何回 楽しさ minM のアトラクションに乗ればいいかもわかります。
二分探索の StlFunction.BinarySearch メソッドは ac-library-csharp のものを使っています。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, long K) = ReadInt2(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int maxA = A.Max(); // Math.Max(A[i] - m, 0) の総和が K を超えない最小の m である minM を求める long ok = maxA + 1; long ng = -1; long minM = StlFunction.BinarySearch(ok, ng, mid => { long sum = 0; foreach (long v in A) sum += Math.Max(v - mid, 0); return sum <= K; }); // アトラクションの楽しさが minM 以下になるまでに得られる満足度を計算する // minM + 1 から A[i] までの総和の総和 long ans = 0; foreach (long v in A) { if (v < minM) continue; long sum1 = v * (v + 1) / 2; long sum2 = minM * (minM + 1) / 2; ans += sum1 - sum2; } // Math.Max(A[i] - minM, 0) の総和と K の差 を求める // 合計 K 回になるまで 楽しさ minM のアトラクションに乗ることができる long sum = 0; foreach (long v in A) sum += Math.Max(v - minM, 0); ans += (K - sum) * minM; Console.WriteLine(ans); } } |
C – Align
問題の概要
長さ N の整数列 A が与えられる。
これらを並べ替えて、隣り合う要素の差の絶対値の合計を最大化したい。
その最大値は何か？
ソートして両端から交互にとっていけばよいのではないかと思われますが、これは嘘解法です。
隣り合う差の絶対値を総和を最大化するのであれば左右の振れ幅を大きくすればいいのですが、交互にとっていくよりももっとよい解を得る方法があります。
数列 A を並び替えた数列を B とすると以下のどちらかになります。
B[0] > B[1] < B[2] > B[3] < B[4] > B[5] < B[6]
B[0] < B[1] > B[2] < B[3] > B[4] < B[5] > B[6]
隣り合う要素の差の絶対値の総和を計算するなら以下の引き算の総和を計算することになります。
上の場合
B[0] – B[1]
B[2] – B[1]
B[2] – B[3]
B[4] – B[3]
B[4] – B[5]
B[6] – B[5]（長さが偶数の場合、これはない）
下の場合
– B[0] + B[1]
– B[2] + B[1]
– B[2] + B[3]
– B[4] + B[3]
– B[4] + B[5]
– B[6] + B[5]（長さが偶数の場合、これはない）
これはそれぞれ足し算を何回したかを数えてみると
上の場合
B[0]： 1回
B[1]： -2回
B[2]： 2回
B[3]： -2回
B[4]： 2回
B[5]： -2回
B[6]： 1回
（長さが偶数のとき、B[5]： -1回, B[6] は存在しない）
下の場合
B[0]： -1回
B[1]： 2回
B[2]： -2回
B[3]： 2回
B[4]： -2回
B[5]： 2回
B[6]： -1回
（長さが偶数のとき、B[5]： 1回, B[6] は存在しない）
総和を最大化したいので 2回足す数 > 1回足す数 > 1回引く数 > 2回引く数 としたいです。
なので、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 55 56 57 58 59 60 61 62 63 64 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N = int.Parse(Console.ReadLine()); int[] A = new int[N]; for (int i = 0; i < N; i++) A[i] = int.Parse(Console.ReadLine()); A = A.OrderByDescending(_ => _).ToArray(); // 添字が偶数（初項と末項は除く）、初項、末項、添字が奇数（同）の順に格納されたリスト List<int> indexes1 = new List<int>(); for (int i = 1; i < N - 1; i++) { if (i % 2 == 0) indexes1.Add(i); } indexes1.Add(0); indexes1.Add(N - 1); for (int i = 1; i < N - 1; i++) { if (i % 2 == 1) indexes1.Add(i); } // 添字が奇数（初項と末項は除く）、末項、初項、添字が偶数（同）の順に格納されたリスト List<int> indexes2 = new List<int>(); for (int i = 1; i < N - 1; i++) { if (i % 2 == 1) indexes2.Add(i); } indexes2.Add(N - 1); indexes2.Add(0); for (int i = 1; i < N - 1; i++) { if (i % 2 == 0) indexes2.Add(i); } // 降順にソートされた A の値を上記のふたつの方法で割り当てる int[] B1 = new int[N]; int[] B2 = new int[N]; for (int i = 0; i < N; i++) { B1[indexes1[i]] = A[i]; B2[indexes2[i]] = A[i]; } // 実際に隣の項との差の絶対値の総和を計算して大きいほうを解として出力する long ans1 = 0; long ans2 = 0; for (int i = 0; i < N - 1; i++) { ans1 += Math.Abs(B1[i] - B1[i + 1]); ans2 += Math.Abs(B2[i] - B2[i + 1]); } Console.WriteLine(Math.Max(ans1, ans2)); } } |
