AtCoder Beginner Contest 166 に C# で参加した記録
AtCoder Beginner Contest 166 – AtCoder
ABC166 にC#で参加しました。結果はABCDEの5問ACでした。
とはいえコンテスト終了間近の滑り込みACだったので、パフォーマンスは1100くらいでレートは微減でした。昨日のコンテストのレートと合わせてちょうど±0でした。
D問題が数学で、とはいえ全探索だったんですが問題を勘違いして最初諦めました。そのせいでパフォーマンスが振るわなかったのが残念です。まあ、大幅減にならなくてよかったと思っておきます。
以下、振り返ります。
A – A?C
AtCoder 社は、毎週土曜日にコンテストを開催しています。
コンテストには ABC と ARC の 2 つの種類があり、毎週どちらか一方が開催されます。
ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催されます。
先週開催されたコンテストを表す文字列 S が与えられるので、今週開催されるコンテストを表す文字列を出力してください。
if文で判定すればよいです。
if (S == "ABC")
{
Console.WriteLine("ARC");
}
else
{
Console.WriteLine("ABC");
}B – Trick or Treat
ある街に、N 人のすぬけ君(すぬけ君 1 、すぬけ君 2 、 …、 すぬけ君 N )が住んでいます。
この街には、 K 種類のお菓子(お菓子 1 、 お菓子 2 、….、お菓子 K )が売られています。お菓子 i を持っているのは、すぬけ君 Ai,1,Ai,2,⋯,Ai,di の計 di 人です。
高橋君は今からこの街を回り、お菓子を 1 つも持っていないすぬけ君にいたずらをします。このとき、何人のすぬけ君がいたずらを受けるでしょうか。
B問題にしてはややこしい印象を受けます。
実装はN人についてお菓子を持っているかどうかのフラグを配列で管理して、すべてのお菓子の種類を確認していけばよいです。
var N = sc.ReadInt();
var K = sc.ReadInt();
// n番目の人が持っているお菓子の数を管理する配列
var X = new int[N];
// K種類のお菓子について
for (int i = 0; i < K; i++)
{
// i番目のお菓子を持っている人がd人いる
var d = sc.ReadInt();
for (int j = 0; j < d; j++)
{
// i番目のお菓子を持っているj人目はaさん
var a = sc.ReadInt();
a--;
// aさんが持っているお菓子の数を増やす
X[a]++;
}
}
// お菓子を1つも持っていない人を数える
var ans = X.Count(x => x == 0);
Console.WriteLine(ans);C – Peaks
AtCoder丘陵には N 個の展望台があり、展望台 i の標高は Hi です。 また、異なる展望台どうしを結ぶ M 本の道があり、道 j は展望台 Aj と展望台 Bj を結んでいます。
展望台 i が良い展望台であるとは、展望台 i から一本の道を使って辿り着けるどの展望台よりも展望台 i の方が標高が高いことをいいます。 展望台 i から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 i は良い展望台であるといいます。
良い展望台がいくつあるか求めてください。
制約
- 2≤N≤105
- 1≤M≤105
- 1≤Hi≤109
- 1≤Ai,Bi≤N
- Ai≠Bi
- 同じ展望台の組を結ぶ道が複数あることもある。
- 入力中の値はすべて整数である。
1本の道で行ける展望台の高さについて考えるので、N個の展望台について1本の道で行ける最大の高さを管理しておくことにします。
すべての道を見れば、Ajについては H[Bj] 、Bjについては H[Aj] で最大の高さを更新していくことで1本の道で行ける最大の高さをO(M) で求めることができます。
最後に、すべての展望台について1本の道で行ける最大の高さが自分より小さいものを数え上げればOKです。
var N = sc.ReadInt();
var M = sc.ReadInt();
var H = sc.ReadIntArray(N);
// n番目の展望台から1本の道で行ける展望台の最大の高さを管理する
var max = new int[N];
for (int i = 0; i < M; i++)
{
var A = sc.ReadInt();
var B = sc.ReadInt();
A--; B--;
// A, B について、最大を更新しておく
max[A] = Math.Max(max[A], H[B]);
max[B] = Math.Max(max[B], H[A]);
}
var ans = 0;
for (int i = 0; i < N; i++)
{
// 1本の道で行ける最大の高さより高い場合を数え上げる
if (max[i] < H[i]) ans++;
}
Console.WriteLine(ans);コンテスト中はなぜか実装に手間取り、面倒くさいので優先度付きキューにぶち込むという実装でACしました。
D – I hate Factorization
A5−B5=X を満たす整数の組 (A,B) をひとつ示してください。 ただし、与えられる X に対して、条件を満たす整数の組 (A,B) が存在することが保証されています。
制約
- 1≤X≤109
- X は整数である。
- 条件を満たす整数の組 (A,B) が存在する。
出ました数学問題です。とはいえ複雑な式変形や計算は不要です。単純にすべてのA, Bについて全探索すればOKです。
A, B についてはオバーフローしない範囲で探索すればいいです。
var X = sc.ReadLong();
for (long a = -5000; a < 5000; a++)
{
for (long b = -5000; b < 5000; b++)
{
if (a * a * a * a * a - b * b * b * b * b == X)
{
Console.WriteLine(a + " " + b);
return;
}
}
}やっていることはただの全探索です。A, B が負の数になる可能性を考慮に入ればあとは単純です。
ずっと勘違いしていたのがこの問題の制約にある 条件を満たす整数の組 (A,B) が存在する。 という内容です。これを問題文によく書かれている、"～であることは証明できます。"的な内容と同じことだとおもっていて、どんなXについても答えを見つけなければならないと思ってました。
例えば X=109 のときは、条件を満たす (A, B) は存在せず、したがってそのような入力は与えられないのに、上のコードでは答えが出ないため、ずっと悩んでました。結局コンテスト終了間近で気が付いて、何とかACを拾いました。最初に提出してWAだったコードは探索範囲が70くらいしか見てなくてWAだったのですが、これを120まで見ていればACだったみたいです。
おかげでレートが冷えました。
数学的な細かい話は editorial.pdf を見るのが良いです。
E – This Message Will Self-Destruct in 5s
E – This Message Will Self-Destruct in 5s
AtCoder 王国の優秀なエージェントであるあなたは、盗まれた極秘情報が AlDebaran 王国の手に渡ることを阻止するため、取引現場であるパーティに潜入しました。
パーティには N 人の参加者がおり、それぞれ 1 から N までの番号がついています。参加者 i の身長は Ai です。
あなたは事前の尋問によって、極秘情報を取引するのは以下の条件を満たす 2 人組であることを知っています。
2 人の持つ番号の差の絶対値が、2 人の身長の和に等しい。N 人の参加者のうちから 2 人を選んでペアにする方法は N(N−1)/2 通りありますが、このうち上の条件を満たすペアは何通りあるでしょう？
なお、極秘情報の内容が何であるかはあなたの知るところではありません。
制約
- 入力はすべて整数
- 2≤N≤2×105
- 1≤Ai≤109 (1≤i≤N)
よくある数え上げの問題です。N人から2人選ぶ方法は問題文にある通り N(N−1)/2 通りなので、これを全探索はできません。したがって何かしらの工夫をしてうまく数え上げる必要があります。
ここ条件を満たすペア(i, j)について考えると、以下のような式で表せることがわかります。
j - i = A[i] + A[j]この数式を変形すると
j - A[j] = i + A[i]となります。
左辺は j について、右辺は i についての式なので、それぞれ独立して O(N) で求めることができます。つまりN人について j - A[j] と i + A[i] を求め、一致する組み合わせを数えればよいです。
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
// j - A[j] = i + A[i] についてそれぞれ計算しておく
// Bi = i + A[i]
var Bi = new long[N];
for (int i = 0; i < N; i++)
{
Bi[i] = A[i] + i;
}
// Bj = j - A[j]
var Bj = new long[N];
for (int j = 0; j < N; j++)
{
Bj[j] = j - A[j];
}
// 連想配列に入れて一致する個数を数え上げる
var dic = new Dictionary<long, int>();
for (int i = 0; i < N; i++)
{
if (!dic.ContainsKey(Bj[i])) dic.Add(Bj[i], 0);
dic[Bj[i]]++;
}
var ans = 0L;
for (int i = 0; i < N; i++)
{
if (dic.ContainsKey(Bi[i])) ans += dic[Bi[i]];
}
Console.WriteLine(ans);結構すんなりと式変形から数え上げの考察に行きつき、実装もうまくいきました。解説もあってるみたいなので良かったです。
昨日のC問題より解かれているみたいなので易しめのE問題だったみたいです。とはいえさすがに昨日のC問題のほうが簡単だと思いますが。
たぶん
F
見てません。
以上。
