ユニークビジョンプログラミングコンテスト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で訪問済みの家を管理、重複カウントを防止