AtCoder Beginner Contest 163 (Unrated) のA-E問題の考察を書いていきます。結果はぎりぎりE完でした。
A - Circle Pond
問題概要: 半径 R の円の円周の長さを求めよ。
A: 考察
円周の長さは直径に比例することが知られていて、比例定数は π です。つまり (円周の長さ) = π×(直径) = 2πR になります。
Rust では、円周率 π の値は std::f64::consts::PI で参照できます。
なお浮動小数点数である PI に整数 2 を掛けると型検査が通りません。2 * PI ではなく 2.0 * PI とすれば OK です。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc163/submissions/12099613
B - Homework
問題概要: 夏休みが N 日間あり、夏休みの宿題が M 個ある。i 個目の宿題をやるには A(i) 日かかる。複数の宿題を同じ日にやることはできない。宿題をやる日には遊ぶことができない。夏休み中にすべての宿題を終わらせられるか判定し、終わらせられるなら最大で何日遊べるかを求めよ。
B: 考察
A(i) の総和を S とします。複数の宿題を同じ日にやることはできないので、宿題を終わらせるには、ちょうど S 日かかります。夏休み中に宿題を終わらせるための条件は S≤N です。
夏休み中に宿題が終わるとき、宿題をする S 日は遊べませんが、残りは遊べます。そのため、遊べる日の最大は N-S 日です。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc163/submissions/12096931
C - management
問題概要: N 人の社員からなる会社があり、各社員は 1, ..., N の社員番号が割り当てられている。社員番号が 1 でない各社員には、自分より社員番号が小さい直属の上司が1人いる。社員 X が社員 Y の直属の上司であるとき、Y は X の直属の部下であるという。社員番号 i の社員の直属の上司の社員番号は A(i) である。各社員の直属の部下の人数を求めよ。
制約: N≤10^5
C: 考察
入力例1の状況を図示すると以下のようになります。(カッコ内は社員番号、左が上司)
(1) ----- (2) ---- (4)
\ \
\ --- (5)
--- (3)
社員 1, 2 の直属の部下は2人 (ぞれぞれ 2, 3 と 4, 5) です。
問題文の「社員 X が社員 Y の直属の上司であるとき、～」の X, Y にそれぞれ A(i), i を当てはめると、
- 社員 A(i) が社員 i の直属の上司であるとき、i は A(i) の直属の部下であるという
となります。「i は A(i) の直属の部下である」ことを言い換えると、
- i は、A(i) の直属の部下からなる集合のメンバーである
といえます。各社員 i に対して「社員 A(i) の直属の部下からなる集合」に i を追加していくことで、各社員の直属の部下を把握できます。
今回は直属の部下が具体的に誰かは問われないので、「直属の部下からなる集合」の代わりに「直属の部下の人数」を調べても OK です。
// 疑似コード
for i {
直属の部下の集合(A(i)).insert(i);
// または
直属の部下の人数(A(i)) += 1;
}
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc163/submissions/12089699
D - Sum of Large Numbers
問題概要: 正の整数 N, K が与えられる。10^100, 10^100 + 1, 10^100 + 2, ..., 10^100 + N の N+1 個の整数から K 個以上を選んでできる総和として、ありうるものの個数を求めよ。(mod 10^9+7)
制約: N≤10^5
D: 考察
制約から 0 + 1 + ... + N の総和は 10^10 未満なので、10^100 の和と 0～N の和が「混ざる」ことはありません。整数 10^100 + x を1個選ぶたびに「10^100 の個数が1増える」「0～N の和が x 増える」と別々に計算できます。特に、 10^100 にかかる係数は選んだ整数の個数に一致 します。
言い換えると、0～N から選んだ整数の和が等しくても、選んだ整数の個数が異なれば、異なるものとして扱うことになります。例えば 6 = 2 + 4 = 1 + 2 + 3 は、この問題では区別されます。
入力例1 (N=3, K=2) をみます。
2個の整数を選ぶケース (5通り):
- 0 + 1 = 1
- 0 + 2 = 2
- 0 + 3 = 1 + 2 = 3
- 1 + 3 = 4
- 2 + 3 = 5
3個の整数を選ぶケース (4通り):
- 0 + 1 + 2 = 3
- 0 + 1 + 3 = 4
- 0 + 2 + 3 = 5
- 1 + 2 + 3 = 6
4個の整数を選ぶケース (1通り):
- 0 + 1 + 2 + 3 = 4
したがって 5 + 4 + 1 = 10 通りです。
この例をよくみると、 0～N の小さい順に x 個を選ぶときの和の最小値から、大きい順に x 個を選ぶときの和の最大値まで、どの値も「0～N からちょうど x 個選んだ和」で表せる ことに気付ける……かもしれません。実際、小さい順に x 個を選ぶときの和を S とするとき、選ばれている数 m のいずれかを m+1 (≤N) で置き換えることで、和を 1 ずつ増やしていくことができるからです。
0 1 2 3
x x x 最小
x x x (1増やす)
x x x (1増やす)
x x x 最大
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc163/submissions/12137966
入力例1をあまり観察していなかったのが反省点です。手元で実験して法則性を発見しましたが、上記の「最小～最大までちょうど x 個の和で必ず表せる」に納得できなくて悩み、時間を費やしてしまいました。
E - Active Infants
問題概要: N 人の幼児が左右一列に並んでいる。幼児を好きな順番に並び替える。各幼児につき、この幼児がはじめに左から x 番目にいて、並び替え後に左から y 番目にいるとすると、A(x)・|x - y| のスコアを得る。適切に並び替えたときの、スコアの総和の最大値を求めよ。
制約: N≤2000, A(i)≥1
E: 考察
入力例2をみます。
1 2 3 4 5 6 初期位置
A B C D E F 名前
5 5 6 1 1 1 活発度
直感的には「活発度が高い幼児をなるべく遠くに移動させる」とスコアが増えそうです。活発度が高い順に幼児を見ていき、左端か右端の遠い方に移動させる、という手順を繰り返すと次の順列になります。
1 2 3 4 5 6 現在位置
D E F B A C 名前
1 1 1 5 5 6 活発度
この並び替えにおける活発度×距離の総和は 57 です。
D E F B A C 名前
1 1 1 5 5 6 活発度
4 5 6 2 1 3 初期位置
1 2 3 4 5 6 現在位置
3 3 3 2 4 3 移動距離
3 3 3 10 20 18 活発度×移動距離
一方、活発度 6 の幼児 C を右端ではなく左端に配置すると、総和を 58 にできて、最大になります。
6 2 3 4 5 6 現在位置
C D E F B A 名前
6 1 1 1 5 5 活発度
3 4 5 6 2 1 初期位置
2 2 2 2 3 5 移動距離
12 2 2 2 15 25 活発度×移動距離
「活発度が最大の幼児を端に置く」のは正しいでしょうか？ 実はこれは正しいです。というのも、活発度が最大の幼児 x が端にないとすると、元の位置から遠い方の隣 y と交換できます。この操作をするとスコアが A(x) 増える一方、移動した隣の幼児の距離が変化してもたかだか A(y) しか減らず、収支はプラスです。(正確には減らない。幼児 x は活発度が最大なので A(x)≥A(y))
したがって、最適な配置が与えられたとき、この交換操作を繰り返すことで総和を減らすことなく活発度が高い幼児を端に移動できるので、はじめから活発度が高い幼児を端に置くケースだけ考えてよいです。
同様に、残りの幼児も 活発度が高い順に左端か右端に配置していくことで総和を最大化可能 です。
問題は各幼児を左端に配置するか、右端に配置するかですが、動的計画法を使って両方試せばよいです。
活発度が高い順に i 人の幼児を左端か右端に配置したとします。そのうち、x 人は左端に、y 人は右端に配置したとします。次の i+1 番目の幼児は、左端 (x+1 番目) か右端 (N-y 番目) に配置するのがベストなので、それぞれの場合の活発度×距離を計算し、次の状態に遷移します。
一見、状態が i, x, y の3変数 (O(N^3)) で、遷移が2通り (O(1)) なので、全体として O(N^3) になりそうですが、i = x + y だから変数を1つ減らせば O(N^2) で間に合います。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc163/submissions/12141775
「活発度が高い順に見る (探索順序の最適化)」「左端か右端に置くと最善 (貪欲法)」「 原始的な動的計画法 」という3つのポイントがあって面白い問題だと思いました。