AtCoder Beginner Contest 159 に参加した記録
AtCoder Beginner Contest 159 – AtCoder
ABC159 に参加しました。結果はABCDの4問ACでした。
今回はD問題が20分しないで解けたので簡単な部類でした。E問題は時間をかけましたが実装しきれませんでした。
前回のAGCに続き、一応レート微増でした。とりあえずWA0でしっかり実装できたのはよかったです。
問題を振り返ります。
A – The Number of Even Pairs
N+M 個のボールがあります。各ボールには整数が 1 つ書かれています。
これらのボールに書かれている数について、
- N 個のボールに書かれている数は偶数
- M 個のボールに書かれている数は奇数
であることがわかっています。
これらの N+M 個のボールの中から 2 つ選んで、書かれた数の和が偶数になる方法の数を求めてください。選ぶ順序は考慮しません。
なお、この方法の数はボールに書かれている整数の実際の値によらないことが示せます。
制約
- 0≤N,M≤100
- 2≤N+M
- 入力はすべて整数である。
普段のA問題に比べると少しややこしい問題です。
足し算の結果が偶数になるには 奇数+奇数 もしくは 偶数+偶数 である必要があります。つまり今回の問題の答えはN個の偶数から2個選ぶ方法の数と、M個の奇数から2個選ぶ方法の数を足し合わせた数が答えになります。
N個から2個選ぶ方法の数は N*(N-1)/2 です。よって以下のコードで答えが求まります。
var ans = 0;
ans += N * (N - 1) / 2;
ans += M * (M - 1) / 2;
Console.WriteLine(ans);また上記のような計算式を知らなくても、問題文に「この方法の数はボールに書かれている整数の実際の値によらないことが示せます。」とある通り、適当な数を当てはめて全探索しても問題ありません。例えば偶数はすべて2、奇数はすべて1として考えて、全探索すると以下のようになります。
var a = new List<int>();
for (int i = 0; i < N; i++) a.Add(2);
for (int i = 0; i < M; i++) a.Add(1);
var ans = 0;
for (int i = 0; i < N + M; i++)
{
for (int j = i + 1; j < N + M; j++)
{
if ((a[i] + a[j]) % 2 == 0) ans++;
}
}
Console.WriteLine(ans);NとMの制約が小さいのでこのコードでもOKです。
B – String Palindrome
長さが奇数である文字列 S が以下の条件をすべて満たすとき、S は「強い回文」であるといいます。
- S は回文である。
- N を S の長さとするとき、S の 1 文字目から (N−1)/2 文字目まで(両端含む)からなる文字列は回文である。
- S の (N+3)/2 文字目から N 文字目まで(両端含む)からなる文字列は回文である。
S が強い回文かどうかを判定してください。
よく見る回文問題です。3パターンの回文判定をすべてクリアできればOKという問題です。
ややこしいですが、S の 1 文字目から (N−1)/2 文字目まで と S の (N+3)/2 文字目から N 文字目まで をそれぞれ切り出して別々の文字列として判定すればよいです。
var ok = true;
var S = sc.ReadStr();
var N = S.Length;
for (int i = 0; i < N / 2; i++)
{
if (S[i] != S[N - i - 1]) ok = false;
}
var S2 = S.Substring(0, (N - 1) / 2);
var N2 = S2.Length;
for (int i = 0; i < N2; i++)
{
if (S2[i] != S[N2 - i - 1]) ok = false;
}
var S3 = S.Substring((N + 3) / 2 - 1);
var N3 = S2.Length;
for (int i = 0; i < N3; i++)
{
if (S3[i] != S3[N3 - i - 1]) ok = false;
}
Console.WriteLine(ok ? "Yes" : "No");もちろん元の文字列に対して3パターンの判定をしても問題ないです。
C – Maximum Volume
正の整数 L が与えられます。 縦、横、高さの長さ (それぞれ、整数でなくてもかまいません) の合計が L の直方体としてありうる体積の最大値を求めてください。
制約
- 1≤L≤1000
- L は整数
立方体が一番体積が大きくなるみたいです。詳しい証明は editorial.pdf にあります。
直感的に、そんな感じがしたので実装してサンプルが通ったので投げました。数学問題は半分は勘です。
var ans = Math.Pow(L / 3.0, 3);
Console.WriteLine(ans);実装はシンプルに3分の1した値を3乗するとACできます。
D – Banned K
ボールが N 個あり、 i 番目のボールには整数 Ai が書かれています。
k=1,2,…,N に対して以下の問題を解いて、答えをそれぞれ出力してください。
- k 番目のボールを除いた N−1 個のボールから、書かれている整数が等しいような異なる 2 つのボールを選び出す方法の数を求めてください。選ぶ順序は考慮しません。
制約
- 3≤N≤2×105
- 1≤Ai≤N
- 入力はすべて整数である。
これはA問題でのN個から2個選ぶ計算式 N*(N-1)/2 があれば解けます。
方針としては、あらかじめどのボールも除かれていない状態の方法の数を求めておきます。そして、k番目のボールを取り除いたときの差分だけ引く、みたいな感じで実装します。
// iが書かれたボールの数
var count = new long[N + 1];
foreach (var a in A)
{
count[a]++;
}
// iが書かれたボールから2個を取り出す方法の数
var c = new long[N + 1];
for (int i = 0; i < N+1; i++)
{
c[i] = count[i] * (count[i] - 1) / 2;
}
// ボールを除かないときの方法の数
var sum = c.Sum();
// aを除くときの方法の数を求める
foreach (var a in A)
{
if (count[a] == 0) continue;
var newCount = count[a] - 1;
var ans = sum - c[a] + (newCount * (newCount - 1) / 2);
Console.WriteLine(ans);
}注意点として組み合わせの数は N2 くらいまでとりうるので、32bit整数ではオーバーフローする可能性があります。
そんな感じでACできました。
E – Dividing Chocolate
縦 H マス、横 W マスのグリッドに区切られたチョコレートがあります。
上から i 行目、左から j 列目にあるマス (i,j) のチョコレートは、Si,j が 0 のとき普通のチョコレートであり、1 のときホワイトチョコレートです。
このチョコレートに対して、マスの境界に沿った直線によってグリッド全体の端から端まで割る操作を何度か行い、いくつかのブロックに分割します。
分割後のどのブロックにもホワイトチョコレートのマスが K マス以下しか含まれないようにするためには、最小で操作を何回行う必要があるか求めてください。
制約
- 1≤H≤10
- 1≤W≤1000
- 1≤K≤H×W
この問題は解けませんでした。一応考えたのはHが小さいので横方向に分割するパターンを全探索し、それぞれについて縦の分割を貪欲に求めればよさそうというものでした。
解説を見ると方針自体はあっていたみたいです。ですが実装しきれませんでした。完全に実装力不足なので弱かったですね。残念です。
以上。
