AtCoder Beginner Contest 170 に C# で参加した記録
AtCoder Beginner Contest 170 – AtCoder
ABC170 にC#で参加しました。
結果はABCDEの5問ACで青パフォ、レートは昨日のARC級に続きいい感じに増えました。
D問題で問題を誤読して少し時間を溶かし、E問題はライブラリでごり押しして解きました。Fはまだ難しかった気がします。。。
ということで振り返ります。
A – Five Variables
5 つの変数 x1,x2,x3,x4,x5 があります。
最初、変数 xi には整数 i が代入されていました。
すぬけくんは、これらの変数の中から 1 つを選んで、その変数に 0 を代入する操作を行いました。
すぬけくんがこの操作を行ったあとの 5 つの変数の値が与えられます。
すぬけくんが 0 を代入した変数がどれであったかを答えてください。
制約
- 入力として与えられる x1,x2,x3,x4,x5 の値は、すぬけくんが操作を行ったあとのものとしてありえるものである。
5つの変数の1つに0が代入されました。どの変数に代入されたかを見つける問題です。
0になっている値を見つければそれが答えです。最初見たときはもともと0があったら(複数0がある場合)どうするのか考えてしまいましたが、そういうことはあり得ないという制約だと思って提出しました。
コードは配列で値を受け取って0のインデックスを探しました。
var X = sc.ReadIntArray(5);
var ans = Array.IndexOf(X, 0) + 1;
Console.WriteLine(ans);B – Crane and Turtle
庭に何匹かの動物がいます。これらはそれぞれ、2 本の足を持つ鶴か 4 本の足を持つ亀のいずれかです。
高橋くんは、「庭の動物の総数は X 匹で、それらの足の総数は Y 本である」と発言しています。この発言が正しいような鶴と亀の数の組合せが存在するか判定してください。
制約
- 1≤X≤100
- 1≤Y≤100
- 入力中のすべての値は整数である。
いわゆる鶴亀算です。中学受験算数で典型みたいですが、未経験なのでわかりません。
なんにせよ制約が小さいのでありうる組み合わせを全部試しましょう。
鶴を0からX匹まですべてのパターンを試します。鶴の数が決まれば亀の数も決まります。とは足を数えてYに一致するか確認します。
var X = sc.ReadInt();
var Y = sc.ReadInt();
// 鶴の数を0~Xまで試す。
for (int i = 0; i <= X; i++)
{
// 亀の数は(X-i)
// この場合の足の数を数える
var ashi = i * 2 + (X - i) * 4;
if (ashi == Y)
{
// 一致する組み合わせが見つかる場合
Console.WriteLine("Yes");
return;
}
}
// 一致する組み合わせが見つからなかった
Console.WriteLine("No");基本的な全探索でした。
C – Forbidden List
整数 X と、長さ N の整数列 p1,…,pN が与えられます。
整数列 p1,…,pN に含まれない整数 (正とは限らない) のうち X に最も近いもの、つまり X との差の絶対値が最小のものを求めてください。そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。
制約
- 1≤X≤100
- 0≤N≤100
- 1≤pi≤100
- p1,…,pN はすべて異なる。
- 入力中のすべての値は整数である。
これもB問題と同じく全探索で解けます。制約を確認するとだいたいC問題までは全探索できることが多いです。
答えになりうる範囲は 0..101 の範囲です。0も101も制約より整数列には含まれません。Xの範囲も0から100なので、負の数や102以上の数は差の絶対値が最小になることはありません。
ということで答えの候補の数を全探索して、あとは判定するだけです。
var X = sc.ReadInt();
var N = sc.ReadInt();
var P = sc.ReadIntArray(N);
var ans = int.MaxValue;
var d = int.MaxValue;
for (int value = 0; value <= 101; value++)
{
// 整数列に含まれていない数である
if (!P.Contains(value))
{
// Xとの差の絶対値を求める
var nd = Math.Abs(value - X);
if (d > nd)
{
// より小さい絶対値であればそれを答えとする
ans = value;
d = nd;
}
}
}
Console.WriteLine(ans);複数存在する場合は最も小さいものを答えるという部分については、答えの候補を小さいほうから列挙しているので問題なく答えられます。
D – Not Divisible
長さ N の数列 A が与えられます。
次の性質を満たす整数 i (1≤i≤N) の数を答えてください。
- i≠j である任意の整数 i (1≤j≤N) について Ai は Aj で割り切れない
制約- 入力は全て整数
- 1≤N≤2×105
- 1≤Ai≤106
単純に全部の数について、割り切れる数がほかにあるかどうかを判定すると計算量 O(N^2) になってTLEです。
割り切れるということは Ai は Aj の倍数であるという言いかえができます。なので倍数がAiとなるような数が存在するか判定することにします。
M以下の数の倍数を記録することは、重複した数を無視することで O(MlogM) くらいでできます。
なので、重複しないすべての数について倍数を記録しておき、その後すべての数についてその数が別の数の倍数になるかを判定することで答えを求めます。
ただし同じ数が複数ある場合は判定がおかしくなるので、別途処理します。具体的には以下の通りです。
var N = sc.ReadInt();
var A = sc.ReadIntArray(N);
var max = (int)1e6;
// 数の個数を数えておく
var count = new int[max + 10];
for (int i = 0; i < N; i++)
{
count[A[i]]++;
}
// ほかの数の倍数であるかどうかを記録する
var baisuuFlag = new bool[max + 1];
// 重複しないように倍数を記録する
foreach (var a in A.Distinct())
{
// その数自体は記録しないようにする
var now = a;
while (now + a <= max)
{
now += a;
baisuuFlag[now] = true;
}
}
var ans = 0;
for (int i = 0; i < N; i++)
{
// 別の数の倍数ではない かつ 同じ数が複数存在しない
if (!baisuuFlag[A[i]] && count[A[i]] == 1) ans++;
}
Console.WriteLine(ans);自分自身の数を倍数のフラグにするとすべての数が倍数になるので、記録しないようにします。その代わりに同じ数が複数あるときの判定がおかしくなるので、その点については個数が複数であればほかの数の倍数であると判定してます。
E – Smart Infants
AtCoder に参加している幼児が N 人おり、1 から N の番号が付けられています。また、幼稚園が 2×105 校あり、1 から 2×105 の番号が付けられています。 幼児 i のレートは Ai であり、はじめ幼稚園 Bi に所属しています。
これから Q 回にわたって、転園が行われます。 j 回目の転園では、幼児 Cj の所属を幼稚園 Dj に変更します。
ここで、「平等さ」を、AtCoderに参加している幼児が一人以上いるような幼稚園それぞれについて園内で最もレートの高い幼児のレートを求め、その最小値として得られる値とします。
Q 回それぞれの転園後の平等さを求めてください。
制約
- 1≤N,Q≤2×105
- 1≤Ai≤109
- 1≤Cj≤N
- 1≤Bi,Dj≤2×105
- 入力はすべて整数である。
- j 回目の転園の前後で幼児 Cj の所属は異なる。
この問題を見たときに考えたことは言われた通りの操作を平衡二分探索木を使って実装すればいいのではということです。
平衡二分探索木は以下のことが O(logN) でできます。
- 値の挿入
- 値の削除
- 最大値,最小値,k番目に大きい値の取得
要するにソート状態が担保されるリストみたいな感じで使えます。優先度付きキューの進化系みたいに使えて便利です。定数倍が重たいの乱用はできないのですが。
なので、幼稚園の数だけ平衡二分探索木を用意して園児の最高レートを取り出せるようにし、各幼稚園の最高レートを入れておく平衡二分探索木を用意して最小レートを取り出せるようにすればあとはやるだけといった感じになります。
計算量は O(QlogN) です。定数倍がやや重い気がしますが十分許容範囲です。3.5sの制約で、1800msくらいでした。
var N = sc.ReadInt();
var Q = sc.ReadInt();
// すべての幼稚園について平衡二分探索木を用意
var youchienCount = 200000;
var youchien = new Treap<int>[youchienCount];
for (int i = 0; i < youchienCount; i++)
{
youchien[i] = new Treap<int>();
}
var A = new int[N];
var B = new int[N];
for (int i = 0; i < N; i++)
{
A[i] = sc.ReadInt();
B[i] = sc.ReadInt() - 1;
youchien[B[i]].Insert(A[i]);
}
var topMin = new Treap<int>();
for (int i = 0; i < youchienCount; i++)
{
// 幼稚園に園児がいれば最高レートを取得しておく
if (youchien[i].Length > 0)
topMin.Insert(youchien[i][youchien[i].Length - 1]);
}
while (Q-- > 0)
{
// 園児cを幼稚園dに移動する
var c = sc.ReadInt() - 1;
var d = sc.ReadInt() - 1;
// 園児cのレート
var rate = A[c];
// 園児cの所属する幼稚園
var nowYouchien = B[c];
if (youchien[nowYouchien][youchien[nowYouchien].Length - 1] == rate)
{
// 現在所属している幼稚園のトップが自分なら
topMin.Erase(rate);
// 次のトップを更新
if (youchien[nowYouchien].Length > 1)
topMin.Insert(youchien[nowYouchien][youchien[nowYouchien].Length - 2]);
}
// 今の幼稚園から取り除く
youchien[nowYouchien].Erase(rate);
if (youchien[d].Length > 0)
{
// 移動先の幼稚園の最大レートを確認
var nextTopRate = youchien[d][youchien[d].Length - 1];
if (nextTopRate < rate)
{
// もし最高レートが更新されるなら
topMin.Erase(nextTopRate);
topMin.Insert(rate);
}
}
else
{
// 移動先が0人の時は最高レート
topMin.Insert(rate);
}
// 移動先の幼稚園に入れる
youchien[d].Insert(rate);
// 幼児の所属を更新
B[c] = d;
// 答え
var ans = topMin[0];
Console.WriteLine(ans);
}実装は少しややこしいですが、解説PDFと同じことをやってるはずです。丁寧にシミュレーションしてサンプルが通れば提出してACできるはずです。
C#に multiset なんてものはないので自前で用意する必要があります。
平衡二分探索木 Treap
長くなりますが、C#での平衡二分探索木の実装です。実装はTreapと呼ばれるものを使ってます。
class Treap<T> : IEnumerable<T> where T : IComparable
{
public int Length
{
get { return this.Root == null ? 0 : this.NodeCount(this.Root); }
}
public T this[int i]
{
get
{
if (this.Root.Count < i - 1) throw new IndexOutOfRangeException();
return this.Root.Get(i);
}
}
public Node Root;
private IComparer<T> Cmp = Comparer<T>.Default;
public Treap(IComparer<T> cmp = null)
{
if (cmp != null) this.Cmp = cmp;
}
public Node Merge(Node l, Node r)
{
if (l == null || r == null) return l == null ? r : l;
if (l.Priority > r.Priority)
{
l.R = this.Merge(l.R, r);
return this.Update(l);
}
else
{
r.L = this.Merge(l, r.L);
return this.Update(r);
}
}
// 左にk個、右に残り(n-k)個に分割する
public (Node, Node) Split(int k) { return this.Split(this.Root, k); }
public (Node, Node) Split(Node t, int k)
{
if (t == null) return (null, null);
if (k <= this.NodeCount(t.L))
{
var s = this.Split(t.L, k);
t.L = s.Item2;
return (s.Item1, this.Update(t));
}
else
{
var s = this.Split(t.R, k - this.NodeCount(t.L) - 1);
t.R = s.Item1;
return (this.Update(t), s.Item2);
}
}
public int NodeCount(Node node)
{
return node == null ? 0 : node.Count;
}
public int LowerBouond(T value) { return this.LowerBouond(this.Root, value); }
public int LowerBouond(Node node, T value)
{
if (node == null) return 0;
if (this.Cmp.Compare(value, node.Value) <= 0)
return this.LowerBouond(node.L, value);
else
return this.NodeCount(node.L) + 1 + this.LowerBouond(node.R, value);
}
public int UpperBound(T value) { return this.UpperBound(this.Root, value); }
public int UpperBound(Node node, T value)
{
if (node == null) return 0;
if (this.Cmp.Compare(value, node.Value) >= 0)
return this.NodeCount(node.L) + 1 + this.UpperBound(node.R, value);
else
return this.UpperBound(node.L, value);
}
public int ValueCount(T value)
{
return this.UpperBound(value) - this.LowerBouond(value);
}
public void Insert(T value)
{
var sub = this.Split(this.Root, this.LowerBouond(value));
var newNode = new Node(value);
var merged = this.Merge(sub.Item1, newNode);
this.Root = this.Merge(merged, sub.Item2);
}
public void Erase(T value)
{
if (this.ValueCount(value) == 0) return;
var sub = this.Split(this.Root, this.LowerBouond(value));
this.Root = this.Merge(sub.Item1, this.Split(sub.Item2, 1).Item2);
}
public void InsertAt(Node node, int k)
{
var sub = this.Split(this.Root, k);
var merged = this.Merge(sub.Item1, node);
this.Root = this.Merge(merged, sub.Item2);
}
public void InsertAt(T value, int k)
{
var node = new Node(value);
var sub = this.Split(this.Root, k);
var merged = this.Merge(sub.Item1, node);
this.Root = this.Merge(merged, sub.Item2);
}
public Node EraseAt(int k)
{
var sub = this.Split(this.Root, k);
var sub2 = this.Split(sub.Item2, 1);
var res = sub2.Item1;
this.Root = this.Merge(sub.Item1, sub2.Item2);
return res;
}
public Node Update(Node node)
{
node.Count = this.NodeCount(node.L) + this.NodeCount(node.R) + 1;
return node;
}
public class Node
{
private static Random Rand = new Random();
public T Value;
public Node L = null;
public Node R = null;
public int Count;
public double Priority;
public Node(T value, double priority)
{
this.Value = value;
this.Priority = priority;
this.Count = 1;
}
public Node(T value) : this(value, Rand.NextDouble()) { }
public T Get(int i) { return this.GetNode(i).Value; }
public Node GetNode(int i)
{
var lcount = 0;
if (this.L != null) lcount = this.L.Count;
if (lcount == i) return this;
else if (lcount < i) return this.R.GetNode(i - lcount - 1);
else return this.L.GetNode(i);
}
}
public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < this.Length; i++) yield return this.Root.Get(i);
}
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}ライブラリ貼るだけに近い問題ですが持っててよかったです。
ちなみに平衡二分探索木の実装はほかにもいろいろあるみたいです。
以上。Fは難しい！
