競技プログラミング

A10 - Resort Hotel

atcoder.jp 左からと右からの累積MAX(?)を計算しておく。 var N = int.Parse(Console.ReadLine()!); var A = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList(); var D = int.Parse(Console.ReadLine()!); var Q = new List<(int Left, i…

B09 - Papers

atcoder.jp ABとCDが座標というのを理解していなくて、1まわり大きい面積を計算してしまっていた。実際に手計算して気付けたけど、結構嵌まってしまったな。 var N = int.Parse(Console.ReadLine()!); var A = new int[N]; var B = new int[N]; var C = new …

A09 - Winter in ALGO Kingdom

atcoder.jp 配列のインデックスが配列に格納されているような形なんで、ミスしてもなかなか気付かずハマった。配列の中身を出力するコードを一時的に足して、間違っていた箇所にようやく気付けた。 var HWN = Console.ReadLine()!.Split(' ').Select(x => in…

B08 - Counting Points

atcoder.jp 点の座標を二次元配列にプロットしてから、二次元累積和を計算。 x座標用のループ変数はx、y座標用のループ変数はyと名前付けしたら、混乱が緩和された気がする。 const int H = 1500 + 1; const int W = 1500 + 1; var N = int.Parse(Console.Re…

A08 - Two Dimensional Sum

atcoder.jp 回答する際の、配列のインデックス指定で混乱した。変数名にもうちょい工夫が必要だったな。 var input = Console.ReadLine()! .Split(' ') .Select(x => int.Parse(x)) .ToList(); var H = input[0]; var W = input[1]; var X = new int[H, W]; …

B07 - Convenience Store 2

atcoder.jp 前の時間帯と比べて何人増減したかを計算して、次にその累積和を計算。 var T = int.Parse(Console.ReadLine()!); var N = int.Parse(Console.ReadLine()!); // 例えば0時から10時までの営業で、 // 5時から10時まで働く従業員がいた場合、 // B[…

A07 - Event Attendance

atcoder.jp 前日比を計算してから、前日比の累積和を計算。 var D = int.Parse(Console.ReadLine()!); var N = int.Parse(Console.ReadLine()!); // 前日比を計算 var B = new int[D + 2]; // 0 日目と D + 1 日目も含める for (var i = 0; i < N; i++) { va…

B06 - Lottery

atcoder.jp アタリとハズレの累積和をそれぞれ計算しておく。0 番目の累積和として 0 を追加しておくテクニックを使ってみた。 var N = int.Parse(Console.ReadLine()!); var A = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList(); var Q…

A06 - How Many Guests?

atcoder.jp (R日目までの累積来場者数) - (L - 1 日目までの累積来場者数)を愚直に実装してみた。 var NQ = Console.ReadLine()! .Split(' ') .Select(x => int.Parse(x)) .ToList(); var N = NQ[0]; var Q = NQ[1]; var A = Console.ReadLine()! .Split(' '…

B04 - Binary Representation 2

atcoder.jp 2進数を10進数に変換。 var N = Console.ReadLine()!; var answer = 0; for (var i = 0; i < N.Length; i++) { var m = Math.Pow(2, N.Length - 1 - i); if (N[i] == '1') { answer += (int)m; } } Console.WriteLine(answer);

A05 - Three Cards

atcoder.jp 3重ループだと時間切れになるので、2重ループで。 var input = Console.ReadLine()!.Split(' '); var N = int.Parse(input[0]); var K = int.Parse(input[1]); var answer = 0; for (var r = 1; r <= N; r++) { for (var b = 1; b <= N; b++) { v…

A04 - Binary Representation 1

atcoder.jp 10桁目から計算開始し、桁を下げていく。 var N = int.Parse(Console.ReadLine()!); var answer = ""; for (int i = 9; i >= 0; i--) { var m = Math.Pow(2, i); answer += (int)(N / m); N = (int)(N % m); } Console.WriteLine(answer);

B03 - Supermarket 1

atcoder.jp ただの 3 重ループだと商品が重複するので WA になる。商品が重複しない工夫が必要。 var N = int.Parse(Console.ReadLine()!); var A = Console.ReadLine()!.Split(' ').Select(int.Parse).ToList(); var answer = false; // 組み合わせなので、…

A03 - Two Cards

atcoder.jp N 使ってないけど、AC だったのでヨシ! var input = Console.ReadLine()! .Split(' ') .Select(int.Parse) .ToList(); var N = input[0]; var K = input[1]; var P = Console.ReadLine()! .Split(' ') .Select(int.Parse) .ToList(); var Q = Co…

B02 - Divisor Check

atcoder.jp LINQ 使わずに for で書いてみた。 var input = Console.ReadLine()!.Split(' '); var A = int.Parse(input[0]); var B = int.Parse(input[1]); var exists = false; for (var n = A; n <= B; n++) { if (100 % n == 0) { exists = true; break; …

A02 - Linear Search

atcoder.jp LINQ 便利。楽のし過ぎかも。 var input = Console.ReadLine()!.Split(' '); var N = int.Parse(input[0]); var X = int.Parse(input[1]); var A = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)); if (A.Any(x => x == X)) { Consol…

B01 - A+B Problem

atcoder.jp 単純な足し算。 var input = Console.ReadLine(); var array = input!.Split(' '); var A = int.Parse(array[0]); var B = int.Parse(array[1]); Console.WriteLine(A + B);

A01 - The First Problem

atcoder.jp 言語に C# 11.0(.NET 7.07) が追加されていたので、C# で書く。 var N = int.Parse(Console.ReadLine()!); Console.WriteLine(N * N); トップレベルステートメントが使えるので、コードが短くなって良し。

ARC005C - 器物損壊!高橋君

atcoder.jp 今までの幅優先探索ではスタート地点からの距離をカウントしていたけど、今回はその区画に着くまでに最低何回塀を壊す必要があるかをカウントしてみた。 using System; using System.Collections.Generic; using System.Linq; namespace ARC005C …

AGC033A - Darker and Darker

atcoder.jp 開始地点となる # の位置を記録しておいて、まとめて幅優先探索を行う。一つずつ幅優先探索を完了していったらタイムオーバーになるので、まとめてやるのが重要だった。 using System; using System.Collections.Generic; using System.Linq; nam…

第10回日本情報オリンピック予選(オンライン)E - チーズ (Cheese)

atcoder.jp 1→2→…→N と順番に辿っていけばいい。答えは「(S から 1 までの距離) + (1 から 2 までの距離) + … + (N - 1 から N までの距離)」になるので、幅優先探索による全探索を、開始地点を変えながら繰り返す。 using System; using System.Collections…

ABC007B - 辞書式順序

atcoder.jp 'a' を出力すれば、入力 A のほとんどのケースで正解になってしまう。例外は入力 A が 'a' のとき。そのときは -1 を出力するしかない。プログラミングコンテストは時間との勝負でもあるので、簡単な方法で解けそうなら、その方法を選んで時間を…

ABC091B - Two Colors Card Game

atcoder.jp カードの文字列を読み込みながら、その文字列が言われたとき何円もらえるかを計算しておく。 using System; using System.Collections.Generic; using System.Linq; namespace ABC091B { class Program { static void Main(string[] args) { var …

ABC088D - Grid Repainting

atcoder.jp 幅優先探索でスタート地点からの距離を測ってみた。ゴール地点の距離が判明していたら到達可能と判断できる。 ゴール地点の距離 + 1 が必須の白いマスで、それ以外の白いマスは黒に塗りつぶせる。あらかじめ白いマスの数を数えておき、ゴール地点…

ABC007C - 幅優先探索

atcoder.jp キューを使って幅優先探索を実装した。探索でスタート地点からの距離を記録していき、探索し終わったらゴール地点までの距離を出力。 using System; using System.Collections.Generic; using System.Linq; namespace ABC007C { class Program { …

ARC037B - バウムテスト

atcoder.jp 頂点の数 N は 100 以下なので、深さ優先探索を行った場合の深さは最大でもたかだか 100。今回は趣向を変えて、再帰で深さ優先探索を実装してみた。スタック使うよりすんなり書けたので、今後も使えそうな問題があれば使っていきたい。 using Sys…

ARC031B - 埋め立て

atcoder.jp 埋め立て候補の海をスタート地点にした、スタックを使った深さ優先探索。探索終了してスタート地点に戻ったとき、全ての陸地を訪れていれば1つの島にできる。 using System; using System.Collections.Generic; namespace ARC031B { class Progra…

ATC001A - 深さ優先探索

atcoder.jp スタックを使って深さ優先探索を実装。深い=sから遠い。次に調べる区画をスタックにプッシュしていき、調べ終わったらポップして前の区画に戻る、の繰り返し。 using System; using System.Collections.Generic; namespace ATC001A { class Prog…

ABC002D - 派閥

atcoder.jp N 人の議員がそれぞれ派閥に参加するかどうかのパターンは 2N なので、ビット全探索を使ってみた。仮の派閥を作っておいて、全員がお互いに知り合いかどうかを調べる。 using System; using System.Collections.Generic; using System.Linq; usin…

ARC029A - 高橋君とお肉

atcoder.jp 焼く時間が長い順にソートしてから、2台の肉焼き機に振り分けた。 using System; using System.Linq; namespace ARC029A { class Program { static void Main(string[] args) { var N = int.Parse(Console.ReadLine()); var t = new int[N]; for …