AtCoder Beginner Contest 163 に C# で参加した記録
AtCoder Beginner Contest 163 – AtCoder
ABC163 にC#で参加しました。結果はABCEの4問ACでした。
コンテスト自体は Unrated でレート変動はありませんでした。D問題は30分くらい考えても解けなくて、Unratedが確定してたので諦めました。
DをパスしましたがE問題は解けました。E問題のほうがとても簡単な気がしました。
以下、振り返ります。
A – Circle Pond
半径 R の円の周長を出力してください。
円周は 直径 * π です。
var ans = 2 * R * Math.PI;
Console.WriteLine(ans);B – Homework
高橋君の夏休みは N 日間です。
夏休みの宿題が M 個出されており、i 番目の宿題をやるには Ai 日間かかります。
複数の宿題を同じ日にやることはできず、また、宿題をやる日には遊ぶことができません。
夏休み中に全ての宿題を終わらせるとき、最大何日間遊ぶことができますか？
ただし、夏休み中に全ての宿題を終わらせることができないときは、かわりに -1 を出力してください。
var ans = N - A.Sum();
if (ans < 0) ans = -1;
Console.WriteLine(ans);宿題にかかる日数を合計し、夏休みのN日から引いてやると遊べる日数が求まります。
ただし、夏休み中に宿題を終わらせられないときは N-宿題にかかる合計日数 が負の数になるので、その時は -1 を出力するようにします。
C – management
N 人の社員からなる会社があり、各社員には 1,…,N の社員番号が割り当てられています。
社員番号 1 の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど 1 人います。
X さんが Y さんの直属の上司であるとき、Y さんは X さんの直属の部下であるといいます。
社員番号 i の社員の直属の上司の社員番号が Ai であることが与えられます。各社員について直属の部下が何人いるか求めてください。
最初は問題を誤読して、直属の という部分を見逃していて、すべての部下を求めていましたが、この問題で求めるのはあくまで直属の部下のみです。
したがって、部下数のカウンターを配列で作り、すべての社員について上司を確認し、上司の部下数をカウントアップすればよいです。
// 部下数のカウンタ
var counter = new int[N];
foreach (var a in A)
{
counter[a - 1]++;
}
foreach (var ans in counter)
{
Console.WriteLine(ans);
}D – Sum of Large Numbers
10100, 10100+1 … 10100+N の N+1個の数があります。
この中から K 個以上の数を選ぶとき、その和としてあり得るものの個数を mod(109+7) で求めてください。
a個選ぶときにできる和と、b個選ぶときにできる和は、一致するものはありません。なぜならどんな選び方をしても10100くらいの差ができるからです。というのはわかりました。
なのでa個選んだ時にどれだけ和の個数が重複するのかが求まれば後はすべての選びうる個数について、ループして数えればいいやと思ってました。が、結局いい方法を思いつかず諦めました。E問題のほうが面白そうだったので。
解説を見ると単純にa個選んだ時の最大値と最小値の間の数はすべて得られるというだけの話でした。すごく納得しました。以下解説ACのコードです。
var N = sc.ReadInt();
var K = sc.ReadInt();
var A = Enumerable.Range(0, N + 1).ToArray();
var sum = new long[N + 2];
for (int i = 0; i < N + 1; i++)
{
sum[i + 1] = sum[i] + A[i];
}
var ans = 0L;
for (int i = K; i <= N + 1; i++)
{
var min = sum[i];
var max = sum[N + 1] - sum[N + 1 - i];
var x = max - min + 1;
ans += x;
ans %= (int)1e9 + 7;
}
Console.WriteLine(ans);これはなかなかひらめくのが難しいです。
E – Active Infants
N 人の幼児が左右一列に並んでおり、左から i 番目の幼児の活発度は Ai です。
あなたは一回だけ、幼児たちを好きな順番に並び替えさせることができます。
はじめ左から x 番目に並んでいた幼児が左から y 番目に移動するとき、うれしさが Ax * |x−y| だけ生じます。
幼児のうれしさの合計が最大でいくつになるか求めてください。
制約
- 2≤N≤2000
- 1≤Ai≤109
- 入力はすべて整数である。
幼児に活発度というパラメータがあり、元の位置からより離れた場所に並べ替えるとうれしさが 活発度*距離 だけ生じるので事由に並べ替えてうれしさを最大化します。
一目DPで解くイメージでした。Nの制約が小さいので O(N2) くらいの計算量が許容されるためです。
考えてみると、基本的には活発度の高い幼児をできるだけ離れた場所に並び替えたほうがいいと思いました。
しかし、活発度の高い幼児から順番に貪欲に並べようとすると、左右どちらに並べても同じ距離しか離れない場合、つまりどちらに並べてもその幼児についてはうれしさが変わらない場合があります。このとき、それ以降に並べる幼児の位置によって、並べ方の良し悪しが変わってきます。
こういう先読みしないと解けない問題はDPだとうまくいくと思います。私は難しい問題のDPはループで解けないのでメモ化再帰を使うことにします。
活発度の高い幼児から並べます。今左に何人、右に何人並んでいるかの状態を管理し、その状態からの最大のうれしさを返すような再帰関数を考えます。右に並べたときと、左に並べたときの結果を再帰的に求め、その結果からうれしさが大きくなるほうを選ぶような関数です。
DPテーブルで管理するのは以下のようなイメージです。
DP[i, j, k] = 左にj人、右にk人を並べた状態から、i番目以降の幼児を並べたときの嬉しさの最大値これでは O(N3) くらいのテーブルが必要になるので何かしら省略しなければなりません。そこで r は省略できることに気が付きます。今i番目で左にj人並んでいるなら右にはi-j人並んでいることがわかるのでテーブルは以下のようになります。
DP[i, j] = 左にj人並べた状態から、i番目以降の幼児を並べたときの嬉しさの最大値これを実装すればよいです。
ということで実装はメモ化再帰です。
static void Solve()
{
N = sc.ReadInt();
var A = sc.ReadLongArray(N);
// メモ用のテーブルを-1で初期化しておく
Memo = new long[N + 1, N + 1];
for (int i = 0; i < N + 1; i++)
{
for (int j = 0; j < N + 1; j++)
{
Memo[i, j] = -1;
}
}
// 幼児の元の位置のインデックスと活発度のペア
C = new (int, long)[N];
for (int i = 0; i < N; i++)
{
C[i] = (i, A[i]);
}
// 活発度の高い順にソートしておく
C = C.OrderByDescending(t => t.Item2).ToArray();
var ans = Rec(0, 0);
Console.WriteLine(ans);
}
static int N;
static (int, long)[] C;
static long[,] Memo;
// n番目の幼児を並べる(左にl人すでに並んでいる)ときのうれしさの最大値を返す関数
static long Rec(int n, int l)
{
if (n == N) return 0;
// すでに計算済の場合はそれを返す
if (Memo[n, l] >= 0) return Memo[n, l];
// 右端に並べるパターンを再帰的に計算
var r = N - (n - l);
var u = (r - C[n].Item1 - 1) * C[n].Item2;
var res1 = Rec(n + 1, l) + u;
// 左端に並べるパターンを再帰的に計算
var v = (C[n].Item1 - l) * C[n].Item2;
var res2 = Rec(n + 1, l + 1) + v;
// より大きなうれしさを得られる並べ方を採用してメモ
var res = Math.Max(res1, res2);
Memo[n, l] = res;
return res;
}ACでした。
割とよく見かけるDPだったので比較的易しめのE問題だったと思います。水色行かないくらいのDifficultyだと思いました。
解説を見ると DP[x][y] にして左にx右にyを並べるみたいな管理になってました。まあたぶん同じことだと思います。
以上。
