第3回 岩井星人アンソロジープログラミングコンテストが開催されていたので参加しました。結果は全 8 問のうち 4 問正解。118 人中 81 位という残念な結果になりました。
岩井星人さんはどんな人？
おもに AtCoder Beginner Contest (ABC) の実況動画を YouTube に投稿している配信者です。
関西弁による切れのあるツッコミ、問題が難しくて解けないときのぼやき、レートを減らしたときの激怒といった強烈な魅力のある実況によって、競技プログラミング界隈において人気を博しています。
第一問 No.3678 しゃべりすぎた男
問題の概要
長さ 7 の数列 T が与えられる。k = 0, 1, 2, 3, 4, 5, 6 において 6000 – (T[0] + .. + T[k])を出力せよ。ただし 6000 – (T[0] + .. + T[k]) が負数のときは -1 を出力せよ。また T[k] が -1 のときは -1 を、それ以降も -1 を出力し続けるものとする。
岩井星人さんは、競技プログラミングのコンテストに参加したときの様子を実況動画として YouTube に投稿していますが、コンテスト前のオープニングトーク同様、この問題文も長いです。長い問題文の要点をまとめると概要文のとおりです。あとはコードを書くだけです。
ans の初期値を 6000 とし、T[i] を引きます。ただし T[i] == -1 のときは 6000 よりも大きな値（6010 など）を引き、ans が 0 以上ならそのまま、負数のときは -1 を出力します。
|
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() { int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int ans = 6000; foreach (var v in A) { if (v >= 0) ans -= v; else ans -= 6010; if (ans >= 0) Console.WriteLine(ans); else Console.WriteLine(-1); } } } |
第二問 No.3684 chokudai_niku.png
問題の概要
長さ N の数列 A, B が与えられる。
連続する長さ M の区間からいくつかを選択して A[i] – B[i] の総和を最大化したい。最大化された値を求めよ。
連続する長さ M の区間からいくつか選択するのであれば A[i] – B[i] が 0 より大きなものだけを選べばよいです。C[i] = max(A[i] – B[i], 0) として C の区間和の最大値を考えます。累積和を使えばすべての連続する長さ 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 |
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[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] C = new int[N]; for (int i = 0; i < N; i++) C[i] = Math.Max(A[i] - B[i], 0); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + C[i]; long ans = 0; for (int i = 0; i + M - 1 < N; i++) ans = Math.Max(ans, sums[i + M] - sums[i]); Console.WriteLine(ans); } } |
第三問 No.3679 なんかでっかい虫リターンズ
問題の概要
縦 H マス、横 W マスのグリッドがある。
マス (sr, sc) をスタートして R1 ≦ r ≦ R2 かつ C1 ≦ c ≦ C2 をみたすいずれかのマス (r, c) に移動し、そこからマス (gr, gc) に移動し、マス (sr, sc)に戻ってくる移動を考える。移動回数の最小値を求めよ。
条件をみたすすべての (r, c) について (sr, sc) → (r, c) → (gr, gc) → (r, c) の移動量を計算し、そのなかから最小値をとればよいです。各フェイズにおける移動距離は、移動元から移動先のあいだに障害物はないので単純のマンハッタン距離を計算すればよいです。
|
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 (int a, int b) GetInput2() { int[] input = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); return (input[0], input[1]); } static (int a, int b, int c, int d) GetInput4() { int[] input = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); return (input[0], input[1], input[2], input[3]); } static void Main() { (int H, int W) = GetInput2(); (int sr, int sc) = GetInput2(); (int r1, int c1, int r2, int c2) = GetInput4(); (int gr, int gc) = GetInput2(); int ans = int.MaxValue; for (int r = r1; r <= r2; r++) { for (int c = c1; c <= c2; c++) { int d = Math.Abs(r - sr) + Math.Abs(c - sc); d += Math.Abs(gr - r) + Math.Abs(gc - c); d += Math.Abs(sr - gr) + Math.Abs(sc - gc); ans = Math.Min(ans, d); } } Console.WriteLine(ans); } } |
第四問 No.3683 サーバー代がもったいない!
問題の概要
長さ N の数列 A が与えられる。このなかから隣り合わない K 個の要素を選んだとき、その総和の最大値を求めよ。
動的計画法で解きます。2次元配列 dp[K + 1][2] を定義します。1つめの添字は何個選択したか？ 2つ目の添字は「0 なら選択可能、1 なら前の要素を選択したので選択できない」という意味です。
以下のように遷移させます。
A[i] を選択するとき：
new_dp[k + 1][1] = dp[k][0] + A[i]
A[i] を選択しないとき：
new_dp[k][0] = max(dp[k][0], dp[k][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 |
class Program { static (int a, int b) GetInput2() { int[] input = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); return (input[0], input[1]); } static void Main() { (int N, int K) = GetInput2(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); void ArrayFill(long[,] arr) { for (int i = 0; i < arr.GetLength(0); i++) { for (int j = 0; j < arr.GetLength(1); j++) arr[i, j] = long.MinValue; // long.MinValue は値が未定義であることを示す } } long[,] dp = new long[K + 1, 2]; ArrayFill(dp); dp[0, 0] = 0; foreach (long v in A) { long[,] new_dp = new long[K + 1, 2]; ArrayFill(new_dp); for (int k = 0; k <= K; k++) { // K 個以上選ぶ遷移や未定義の状態からは遷移させない if(dp[k, 0] != long.MinValue && k + 1 <= K) new_dp[k + 1, 1] = dp[k, 0] + v; new_dp[k, 0] = Math.Max(dp[k, 0], dp[k, 1]); } dp = new_dp; } long ans = Math.Max(dp[K, 0], dp[K, 1]); if(ans > long.MinValue) Console.WriteLine(ans); else Console.WriteLine("Impossible"); } } |
第五問 No.3681 心の沸騰石
問題の概要
赤、黄、青、緑の石がそれぞれ red, yellow, blue, green 個 ある。
コストが P を払うことで 赤、黄、青の石を 1 個ずつセットにして取り除くことができ、コスト Q を払うことでひとつの石の色を変えることができる。コストの総和を C 以下に抑えて取り除く石をセットを最大化したい。その最大値を求めよ。
問題文にはルーマニア人がどうのこうの書いてありますが、問題の趣旨は概要のとおりです。
この問題は決め打ち二分探索法で解きます。
セットの数を X にできるかどうかを考えます。セットを X 個つくるために 赤、黄、青 がそれぞれいくつずつ不足しているか、過剰に存在するかを考えます。不足分の総和が（過剰な石の総和＋緑の個数）以下であれば、石数の観点からは可能です。もし予算的にも可能であるなら セットの数を X 以上にすることが可能です。
二分探索法で X の最大値を求めます。以下のコードはライブラリ ac-library-csharp のAtCoder.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 |
using AtCoder; class Program { static void Main() { int[] cpq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (long C, long P, long Q) = (cpq[0], cpq[1], cpq[2]); int[] rybg = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (long red, long yellow, long blue, long green) = (rybg[0], rybg[1], rybg[2], rybg[3]); // これ以上は解としてありえない上限を求めておく。 // 全部を足して 3 で割ったものを切り上げた値であれば絶対に無理 long ng = (red + yellow + blue + green) / 3 + 10; long ok = 0; long ans = AtCoder.StlFunction.BinarySearch(ok, ng, mid => F(mid)); Console.WriteLine(ans); bool F(long x) { long shortages = 0; // 不足数 if (x - red > 0) shortages += x - red; if (x - yellow > 0) shortages += x - yellow; if (x - blue > 0) shortages += x - blue; long surplus = 0; // 剰余数 if (red - x > 0) surplus += red - x; if (yellow - x > 0) surplus += yellow - x; if (blue - x > 0) surplus += blue - x; surplus += green; if (shortages > surplus) // 絶対に無理 return false; return shortages * Q + x * P <= C; // 予算内でできるか？ } } } |
第六問 No.3680 セグメント釣り
問題の概要
異なるタイルを通るたびにコスト 1 が必要である。
(sx + 0.5, sy + 0.5) から (tx + 0.5, ty + 0.5) に移動するために必要なコストの最小値を求めよ。
このようにタイルに番号をつけます。すると番号は sx / Math.Pow(2, y) （ただし y ≧ 60 なら 0）で与えられます。
sy と ty のうち高いほうに移動して（そのときのコストは Math.Abs(ty – sy)）、あとは番号の差で解が得られるのではないかと思ったのですが、実は違っていました。いったんもっと上に移動してから降りてきたほうがコストが安くなる場合があるのです。
この場合、黄色いマスから水色のマスまで移動するとき、水色のマスと同じ高さまで上がってから横に移動すると移動コストは 8 になりますが、さらにひとつ上に上がって降りてくる方法だと移動コストは 6 になります。
なのでsy と ty のうち高いほうに移動して番号の差を取る方法だけでなく、それより高い場所（最高で 60）もすべて調べる必要があります。
|
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()); for (int i = 0; i < N; i++) { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); (long sx, long sy, long tx, long ty) = (vs[0], vs[1], vs[2], vs[3]); long left = Math.Min(sx, tx); long right = Math.Max(sx, tx); long max_y = Math.Max(sy, ty); if (max_y <= 60) { long ans = long.MaxValue; for (int i_max_y = (int)max_y; i_max_y <= 60; i_max_y++) { long dx = right / (1L << i_max_y) - left / (1L << i_max_y); long dy = Math.Abs(ty - sy); ans = Math.Min(ans, dx + dy + 2 * (i_max_y - (int)max_y)); } Console.WriteLine(ans); } else { long dy = Math.Abs(ty - sy); Console.WriteLine(dy); } } } } |
第七問 No.3685 ワロングアンサーやんけ！
問題の概要
文字列 R と S および整数 K が与えられる。R は ‘A’, ‘W’, ‘?’ のみからなる文字列である。
‘?’ が以下の条件をみたすように ‘A’, ‘W’ に特定できるなら置き換えて出力せよ。特定できない場合はそのまま ‘?’ を出力せよ。
S が “Warong” なら条件 X を満たす。S が “NotWarong” なら満たさない。
（条件 X）：「最初の K 文字がすべて A」かつ「少なくとも 1 文字 W を含む」。
S が “Warong” なら最初の K 文字にある ‘?’ はすべて ‘A’ に置き換えてよいです。それ以外の部分は ‘W’ がひとつも存在せず、’?’ がひとつだけならそこは ‘W’ です。そうでないなら特定できません。
S が “NotWarong” の場合ですが、条件 X の否定は「最初の K 文字のなかに少なくともひとつの W が含まれる」または「すべて A である」です。なので ① 最初の K 文字のなかにひとつも W が含まれないのであれば、K + 1 文字目から最後まですべて ‘A’ でなければなりません。また ② K + 1 文字目から最後までにひとつでも ‘W’ が存在するのであれば、最初の K 文字のなかに少なくともひとつの W が含まれるようにしなければなりません。
|
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 |
class Program { static void Main() { int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { Solve(); } void Solve() { string R = Console.ReadLine(); string S = Console.ReadLine(); int K = int.Parse(Console.ReadLine()); char[] res = R.ToArray(); if (S == "Warong") { for (int i = 0; i < K; i++) { if (res[i] == '?') res[i] = 'A'; } int q_cnt = 0; int w_cnt = 0; for (int i = K; i < R.Length; i++) { if (res[i] == '?') q_cnt++; if (res[i] == 'W') w_cnt++; } if (q_cnt == 1 && w_cnt == 0) { for (int i = K; i < R.Length; i++) { if (res[i] == '?') res[i] = 'W'; } } } else { // ①の場合 string r1 = R.Substring(0, K); if (r1.All(_ => _ == 'A')) { for (int i = K; i < R.Length; i++) { if (res[i] == '?') res[i] = 'A'; } } // ②の場合 string r2 = R.Substring(K); if(r2.IndexOf('W') != -1) { int w_cnt = 0; int q_cnt = 0; for (int i = 0; i < K; i++) { if (res[i] == 'W') w_cnt++; if (res[i] == '?') q_cnt++; } if (q_cnt == 1 && w_cnt == 0) { for (int i = 0; i < K; i++) { if (res[i] == '?') res[i] = 'W'; } } } } Console.WriteLine(new string(res)); } } } |
第八問 No.3682 きあいのハチマキ
問題の概要
水色コーダーと緑色コーダーが以下のルールで戦う。
水色コーダーのはじめの体力 は HC、攻撃力は AC、すばやさ は SC であり、緑色コーダーのはじめの体力 は HG、攻撃力は AG、すばやさ は SG である。
すばやさが大きい方が先に攻撃する。同じであれば 1 / 2 の確率でどちらが先に攻撃するかが決まる。
攻撃が行われると、攻撃された者の体力が、攻撃をした者の攻撃力だけ減る。
攻撃を受けて体力が 0 以下になるとき、1 / 10 の確率で体力を 1 残して耐えます。
どちらかの体力が 0 以下になった時点で即座に戦いは終了し、体力が 0 以下にならなかった方が勝ちとする。戦いが終了した時に水色コーダーの勝ちである確率を mod 998244353 で求めよ。
1 / 10 の確率で体力を 1 にして耐えることを「気合の発動」と呼ぶことにします。
気合の発動を考慮しない場合、水色コーダー、緑色コーダーの体力が 0 以下になるまでに必要な攻撃回数をそれぞれ TC、TG と定義します。
TC は HC / AG を切り上げた値であり、TG は HG / AC を切り上げた値です。
すばやさが高い方を A、すばやさが低い方を B とし、（気合の発動無しで）A が x 回、B が y回、攻撃を受けると体力が 0 以下になるという条件で A が勝つ確率を f(x, y) と定義します。
水色コーダーが勝つ確率は、水色コーダーのすばやさのほうが高い場合は f(TC, TG)、低い場合は 1 – f(TG, TC)、同じ場合は両者の平均である (f(TC, TG) + 1 – f(TG, TC)) / 2 となります。
あとは F(x, y) の求め方が分かれば解がわかります。
① x ≧ 2 かつ y ≧ 2 のとき
x ≧ 2 かつ y ≧ 2 のときは双方が攻撃しあっても体力が 0 以下になることは絶対にないので気合の発動を考える必要はありません。F(x, y) は F(x – 1, y – 1) と同じです。
またこれは x と ｙ の双方を 1 ずつ引いた結果、少なくともどちらか一方が 1 になるまで同じです。なので、F(x, y) = F(x – Math.Min(x – 1, y – 1), y – Math.Min(x – 1, y – 1)) です。
② x = 1 かつ y ≧ 2 のとき
この場合、A は B の攻撃に対して気合の発動をしなければ負けてしまいます。少なくとも y = 1 になるまでは耐え続けなければなりません。1 / 10 の確率で y – 1 回耐え続けた場合、勝つことができる確率は F(1, 1) が返す値と同じになります。
なのでまとめると、② の場合の解は Math.Pow(1 / 10, y – 1) × F(1, 1) です。
③ x ≧ 2 かつ y = 1 のとき
(a) A の攻撃に対して B が気合の発動をしなければ勝ちです。x = 1 かつ y = 1 になる確率は Math.Pow(1 / 10, x – 1) ですが、そうならない場合は A の勝ちです。その確率は 1 – Math.Pow(1 / 10, x – 1) です。
(b) A の攻撃に対して B が気合の発動で耐え続け x = 1 かつ y = 1 になる確率は Math.Pow(1 / 10, x – 1) であり、この状態から勝つことができる確率は F(1, 1) です。なのでこの場合の確率は Math.Pow(1 / 10, x – 1) × F(1, 1) です。
したがって両者をあわせた (1 – Math.Pow(1 / 10, x – 1)) + Math.Pow(1 / 10, x – 1) × F(1, 1) が ③ の場合の解です。
④ x = 1 かつ y = 1 のとき
この場合は B が気合の発動をしなければ勝ちです。その確率は 9 / 10 です。また双方が気合の発動をして ④ と同じ状態が繰り返される確率は (1 / 10) × (1 / 10) です。
なので F(1, 1) = 1 / 100 * F(1, 1) + 9 / 10 です。これは F(1, 1) の一次方程式とみることができます。これを解くと F(1, 1) = 10 / 11 となります。
以上から F(x, y) の値を求めることが可能になります。
mod 998244353 で解を求めなければならないので ライブラリ ac-library-csharp の AtCoder.StaticModInt クラスで ModInt を求めています。
参考： ac-library-csharpを使ってみる
C#にModInt型はあるのか？ ac-library-csharpのStaticModInt構造体とDynamicModInt構造体
|
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 |
using AtCoder; class Program { static void Main() { SourceExpander.Expander.Expand(); int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { int ans = Solve(); Console.WriteLine(ans); } int Solve() { long[] input = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); (long H1, long A1, long S1, long H2, long A2, long S2) = (input[0], input[1], input[2], input[3], input[4], input[5]); long T1 = H1 % A2 == 0 ? H1 / A2 : H1 / A2 + 1; long T2 = H2 % A1 == 0 ? H2 / A1 : H2 / A1 + 1; if (S1 > S2) return F(T1, T2).Value; if (S1 < S2) return (1 - F(T2, T1)).Value; if (S1 == S2) return ((F(T1, T2) + 1 - F(T2, T1)) / 2).Value; return 0; } StaticModInt<AtCoder.Mod998244353> F(long x, long y) { StaticModInt<AtCoder.Mod998244353> ten = new StaticModInt<AtCoder.Mod998244353>(10); if (x == 1 && y == 1) return ten / 11; if (x >= 2 && y >= 2) return F(x - Math.Min(x - 1, y - 1), y - Math.Min(x - 1, y - 1)); if (x == 1 && y >= 2) return (1 / ten).Pow(y - 1) * F(1, 1); if (x >= 2 && y == 1) return (1 / ten).Pow(x - 1) * F(1, 1) + (1 - (1 / ten).Pow(x - 1)); return 0; } } } |
