Atcoder 385 ふりかえり (C# .Net 7.0)

ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385）でした。
C# .Net 7.0での提出コードとともにふりかえります。

https://atcoder.jp/contests/abc385

# B -  Santa Claus 1
```C#
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] firstLine = Console.ReadLine().Split();
        int H = int.Parse(firstLine[0]);
        int W = int.Parse(firstLine[1]);
        int X = int.Parse(firstLine[2]);
        int Y = int.Parse(firstLine[3]);
        
        char[,] grid = new char[H, W];
        for (int i = 0; i < H; i++)
        {
            string line = Console.ReadLine();
            for (int j = 0; j < W; j++)
            {
                grid[i, j] = line[j];
            }
        }

        string T = Console.ReadLine();
        HashSet<(int, int)> visitedHouses = new HashSet<(int, int)>();
        
        int currentX = X - 1;
        int currentY = Y - 1;
        
        Dictionary<char, (int, int)> directions = new Dictionary<char, (int, int)>()
        {
            {'U', (-1, 0)},
            {'D', (1, 0)},
            {'L', (0, -1)},
            {'R', (0, 1)}
        };
        
        if (grid[currentX, currentY] == '@')
        {
            visitedHouses.Add((currentX, currentY));
        }
        
        foreach (char move in T)
        {
            int nextX = currentX + directions[move].Item1;
            int nextY = currentY + directions[move].Item2;
            
            if (grid[nextX, nextY] != '#')
            {
                currentX = nextX;
                currentY = nextY;
                
                if (grid[currentX, currentY] == '@')
                {
                    visitedHouses.Add((currentX, currentY));
                }
            }
        }
        
        Console.WriteLine($"{currentX + 1} {currentY + 1} {visitedHouses.Count}");
    }
}
```
### 方針 
- 入力の取得:
 マスの縦横のサイズ H と W、サンタクロースの初期位置 (X, Y) を読み込む。
- マスの状態を示すグリッド S を読み込む。
-- サンタクロースの移動指示を示す文字列 T を読み込む。
- 移動の処理:
 サンタクロースの現在位置と次の移動先を管理する。
 `T` に基づいてサンタクロースが通行可能かつ移動可能な場合に移動を行う。
 移動先が家の場合はカウントする。
- 移動結果の出力:
 サンタクロースが最終的に到達した位置と、通過または到達した家の数を出力する。

# C -  Illuminate Buildings
```C#
using System;
using System.Linq;

class Program
{
    static int FindMaxBuildings(int N, int[] heights)
    {
        int maxCount = 1;
        
        for (int start = 0; start < N; start++)
        {
            for (int interval = 1; start + interval < N; interval++)
            {
                int count = 1;
                int currentHeight = heights[start];
                int currentPos = start;
                
                while (currentPos + interval < N)
                {
                    if (heights[currentPos + interval] == currentHeight)
                    {
                        count++;
                        currentPos += interval;
                    }
                    else
                    {
                        break;
                    }
                }
                
                maxCount = Math.Max(maxCount, count);
            }
        }
        
        return maxCount;
    }
    
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] heights = Console.ReadLine().Split().Select(int.Parse).ToArray();
        
        Console.WriteLine(FindMaxBuildings(N, heights));
    }
}
```
### 方針
- 入力の取得:
ビルの総数 N と、それぞれのビルの高さを配列 H として読み込みます。
- 動的計画法 (DP) の適用:
高さが同じビルのペアを見つける際に、間隔 d を計算します。
各ビル間の間隔 d をもとに、同じ高さで等間隔に並んでいるビルを記録します。
- 条件のチェック:
高さが等しく、かつ等間隔に並んでいるビルの最大数を見つけるために、各ビルペアの間隔を利用します。
すべてのビルペアに対して、条件を満たす最大数を探します。
- 結果の出力:
最大でいくつのビルが条件を満たしているかを出力します。


# D - Santa Claus 2

```C#
using System;
using System.Collections.Generic;

class Program
{
    class HouseData
    {
        public List<long> Coordinates;
        public List<int> Indices;

        public HouseData()
        {
            Coordinates = new List<long>();
            Indices = new List<int>();
        }

        public void Sort()
        {
            List<(long coord, int idx)> combined = new List<(long, int)>();
            for(int i = 0; i < Coordinates.Count; i++) combined.Add((Coordinates[i], Indices[i]));
            combined.Sort((a, b) => a.coord.CompareTo(b.coord));
            Coordinates.Clear();
            Indices.Clear();
            foreach(var item in combined)
            {
                Coordinates.Add(item.coord);
                Indices.Add(item.idx);
            }
        }
    }

    static int LowerBound(List<long> list, long value)
    {
        int left = 0;
        int right = list.Count;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(list[mid] < value) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    static int UpperBound(List<long> list, long value)
    {
        int left = 0;
        int right = list.Count;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(list[mid] <= value) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);
        long sx = long.Parse(input[2]);
        long sy = long.Parse(input[3]);

        Dictionary<long, HouseData> X_to_Houses = new Dictionary<long, HouseData>();
        Dictionary<long, HouseData> Y_to_Houses = new Dictionary<long, HouseData>();

        for(int i = 0; i < N; i++)
        {
            input = Console.ReadLine().Split();
            long x = long.Parse(input[0]);
            long y = long.Parse(input[1]);

            if(!X_to_Houses.ContainsKey(x)) X_to_Houses[x] = new HouseData();
            X_to_Houses[x].Coordinates.Add(y);
            X_to_Houses[x].Indices.Add(i);

            if(!Y_to_Houses.ContainsKey(y)) Y_to_Houses[y] = new HouseData();
            Y_to_Houses[y].Coordinates.Add(x);
            Y_to_Houses[y].Indices.Add(i);
        }

        foreach(var key in X_to_Houses.Keys)
        {
            X_to_Houses[key].Sort();
        }
        foreach(var key in Y_to_Houses.Keys)
        {
            Y_to_Houses[key].Sort();
        }

        bool[] visited = new bool[N];
        long currentX = sx;
        long currentY = sy;

        for(int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            char direction = input[0][0];
            long distance = long.Parse(input[1]);

            if(direction == 'U' || direction == 'D')
            {
                long nextY = direction == 'U' ? currentY + distance : currentY - distance;
                if(X_to_Houses.ContainsKey(currentX))
                {
                    var houseData = X_to_Houses[currentX];
                    long lower = Math.Min(currentY, nextY);
                    long upper = Math.Max(currentY, nextY);
                    int lb = LowerBound(houseData.Coordinates, lower);
                    int ub = UpperBound(houseData.Coordinates, upper);
                    for(int j = lb; j < ub; j++) visited[houseData.Indices[j]] = true;
                }
                currentY = nextY;
            }
            else if(direction == 'L' || direction == 'R')
            {
                long nextX = direction == 'R' ? currentX + distance : currentX - distance;
                if(Y_to_Houses.ContainsKey(currentY))
                {
                    var houseData = Y_to_Houses[currentY];
                    long lower = Math.Min(currentX, nextX);
                    long upper = Math.Max(currentX, nextX);
                    int lb = LowerBound(houseData.Coordinates, lower);
                    int ub = UpperBound(houseData.Coordinates, upper);
                    for(int j = lb; j < ub; j++) visited[houseData.Indices[j]] = true;
                }
                currentX = nextX;
            }
        }

        int count = 0;
        foreach(bool v in visited) if(v) count++;
        Console.WriteLine($"{currentX} {currentY} {count}");
    }
}

```
### 方針
- 交差判定
IsOnSegment関数で線分上の点を判定、家が移動経路上にあるかを確認
- 訪問管理
HashSetで訪問済みの家を管理、重複カウントを防止