0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

B - Santa Claus 1

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

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

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で訪問済みの家を管理、重複カウントを防止
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?