はじめに
AtCoder Beginner Contest 246の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc246
問題A
各辺はX軸またはY軸に平行な長方形なので、Xが同じ頂点のペアが2つとYが同じ頂点のペアが2つが存在することになります。
そのため、XとYそれぞれ値に対するペアの存在を管理し、余ったXとYの値が残りの頂点の座標となります。
実装では、集合を管理するHashSetを使って、ペアとなる値が存在するならそのペアを削除し、存在しないならば値を追加するという方法で管理しました。
public static void Solve()
{
var X = new HashSet<int>();
var Y = new HashSet<int>();
for (var i = 0; i < 3; i++)
{
var (x, y) = Scanner.Scan<int, int>();
if (X.Contains(x)) X.Remove(x);
else X.Add(x);
if (Y.Contains(y)) Y.Remove(y);
else Y.Add(y);
}
var xx = X.First();
var yy = Y.First();
Console.WriteLine($"{xx} {yy}");
}
Xor演算を使うことでも求めることができます。
public static void Solve()
{
var x = 0;
var y = 0;
for (var i = 0; i < 3; i++)
{
var (X, Y) = Scanner.Scan<int, int>();
x ^= X;
y ^= Y;
}
Console.WriteLine($"{x} {y}");
}
問題B
2点間の距離はD=Sqrt(A*A+B*B)なので、(A/D, B/D)が答えとなります。
public static void Solve()
{
var (A, B) = Scanner.Scan<int, int>();
var d = Math.Sqrt(A * A + B * B);
var (x, y) = (A / d, B / d);
Console.WriteLine($"{x} {y}");
}
また、C#では、System.Numerics名前空間にあるVector2という構造体を使って、正規化したベクトルを取ることでも答えを求めることができます。
public static void Solve()
{
var (A, B) = Scanner.Scan<int, int>();
var v = new Vector2(A, B);
var answer = Vector2.Normalize(v);
Console.WriteLine($"{answer.X} {answer.Y}");
}
問題C
まず、1枚のクーポンにつきX円安くできるため、可能な限りX円安くすることを考えます。
これは、A[i]>=XとなるA[i]はクーポンがある限りA[i]-Xにすることができ、使うことができるクーポンの数がkのとき、A[i]=A[i]-k*Xとすることができます。
k枚のクーポンを持っていて値段がPのとき、Min(k, P/X)枚のクーポンを使うことができるため、クーポンの数を更新しながらAを順にみていくことで、Aの値を可能な限りX円安くした値にすることができます。
その後、まだクーポンが余っている場合は、Aの全ての値はA[i]<Xとなっているため、Aの値が大きい順にクーポンを使って0円にすることができます。
そして、全ての操作を終えたときの和が答えとなります。
public static void Solve()
{
var (N, K, X) = Scanner.Scan<int, long, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
for (var i = 0; i < N; i++)
{
var k = Math.Min(K, A[i] / X);
A[i] = A[i] - k * X;
K -= k;
}
Array.Sort(A);
Array.Reverse(A);
for (var i = 0; i < Math.Min(N, K); i++)
{
A[i] = 0;
}
var answer = A.Sum();
Console.WriteLine(answer);
}
問題D
コンテスト中の考察です。
aとbは最大でも1e6になりそう。F(a,b)=aaa+aab+abb+bbbのとき、a+b=cかつF(a,b)>=Nとなるcを二部探索して0<=a<=cのときの最小?
解説では尺取り法でした。
public static void Solve()
{
var N = Scanner.Scan<long>();
long F(long a, long b) => (a * a * a) + (a * a * b) + (a * b * b) + (b * b * b);
const long inf = (long)1e6;
var answer = inf * inf * inf;
var b = inf;
for (var a = 0; a <= b; a++)
{
while (F(a, b) >= N && b >= a)
{
answer = Math.Min(answer, F(a, b));
b--;
}
}
Console.WriteLine(answer);
}
問題E
マスは最大4方向から移動してくる可能性があることに注意し、Dijkstra法で最短経路を求めます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var (Ah, Aw) = Scanner.Scan<int, int>();
Ah--; Aw--;
var (Bh, Bw) = Scanner.Scan<int, int>();
Bh--; Bw--;
var S = new string[N];
for (var i = 0; i < N; i++)
{
S[i] = Scanner.Scan<string>();
}
var H = N;
var W = N;
var G = new int[H, W];
const int inf = (int)1e9;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
G[i, j] = inf;
}
}
var used = new bool[H, W];
G[Ah, Aw] = 0;
var D4 = new[] { (1, 1), (-1, -1), (1, -1), (-1, 1) };
var queue = new Queue<(int, int)>();
queue.Enqueue((Ah, Aw));
while (queue.Count > 0)
{
var (ch, cw) = queue.Dequeue();
if (used[ch, cw]) continue; // マスをみるのは訪れた最初の1回だけ
used[ch, cw] = true;
var cc = G[ch, cw];
// 各方向に広げていく
foreach (var (dh, dw) in D4)
{
for (var d = 1; d < N; d++)
{
var (nh, nw) = (ch + dh * d, cw + dw * d);
// 次のマスが範囲外またはブロックならそれ以上この方向に進むことができないからbreak
if (nh < 0 || H <= nh || nw < 0 || W <= nw) break;
if (S[nh][nw] == '#') break;
var nc = cc + 1;
// 少ない移動回数で訪れているなら、この方向は既にqueueに入っているからbreak
// 同じ移動回数の場合は、交差する点の可能性があるため、queueにいれる
if (G[nh, nw] < nc) break;
G[nh, nw] = nc;
queue.Enqueue((nh, nw));
}
}
}
var answer = G[Bh, Bw] == inf ? -1 : G[Bh, Bw];
Console.WriteLine(answer);
}