競プロ参戦記 #67 All-you-can-eat | ABC 145

ABC に参加して、E完でした。

AtCoder Beginner Contest 145

• この連載記事では、着手した問題の考察を自分なりに書いていきます。
  • 前回: 競プロ参戦記 #66 Travel by Car | ABC 143
• 問題の詳細は問題一覧を参照してください。
  • 問題一覧: https://atcoder.jp/contests/abc145/tasks

A - Circle

問題概要: 半径 r の円の面積は、半径 1 の円の面積の何倍かを求めよ。

A: 考察

面積比の公式言えますか？

半径が r 倍なら面積は r^2 倍です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc145/submissions/8469770

B - Echo

問題概要: 長さ N の英小文字からなる文字列 S が与えられる。文字列 T で S = T + T であるようなものが存在するか判定せよ。

B: 考察

S の長さ N は T の長さの2倍なので、偶数でなければいけません。奇数なら、そのような T は存在しないといえます。

N が偶数のとき、T の長さは N/2 なので、T = S[0..N/2] = S[N/2..N] であることが分かります。実際にイコールが成り立つかを調べればよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc145/submissions/8469483

C - Average Length

問題概要: N 個の街があり、i 番目の街は座標 (x(i), y(i)) にある。いずれかの街から出発して、すべての街に1回ずつ訪れる。移動距離の平均値を求めよ。

制約: N≤8

C: 考察

移動経路は最大 8! = 40320 通りしかないので、全列挙できます。

移動経路は街を訪れる順番に対応します。つまり、1 から N までの整数の順列を全通り求めれば移動経路をもれなくだぶりなく調べたことになります。

各経路について移動距離の合計を求めて、それらの総和を経路数 (N!) で割ればよいです。

順列の全探索は next_permutation 関数を使うと簡単です。Rust の標準ライブラリにはないので、事前に用意しておくのがおすすめ。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc145/submissions/8468912

next_permutation ではなく深さ優先探索 (DFS) により実装することも可能です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc145/submissions/8566129

C にしては実装が難しいなと思ったら、公式解説によると数学的な解法もあったんですね。

D - Knight

問題概要: 二次元平面の点 (0, 0) に駒がある。この駒は1回の移動で、+1,+2 または +2,+1 だけ移動する。点 (X, Y) に駒を移動させる手順を数えよ。

制約: X, Y≤10^6

D: 考察

どちらに移動しても x 座標と y 座標の和が 3 増えることに注目すると、

• X+Y の値は3の倍数でなければ移動手順が存在しない
• (X+Y)/3 回移動する

ことが分かります。

K = (X+Y)/3 と置き、右方向へ a 回数、左方向へ b 回移動するとすると、以下の連立方程式が立てられます。

• a + b = K
• 2a + b = X
• a, b ≥ 0

これを解いて a = 2K - X, b = X - K です。移動回数は順列の場合の数から K!/(a! * b!) になります。

剰余の階乗は DP で求め、逆数はフェルマーの小定理と繰り返し二乗法で求められます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc145/submissions/8475304

公式解説の手順の方がスマートでした。

E - All-you-can-eat

問題概要: N 個の料理があり、i 番目の料理を食べるには A(i) 分かり、美味しさは B(i) である。最初の T 分間は好きな料理を食べることができるが、複数の料理を同時に食べることはできない。T 分経過した時点で、料理を食べ始めることはできなくなるが、すでに食べている料理を食べ続けることはできる。食べた料理の美味しさの最大値を求めよ。

制約: N, T, A(i), B(i)≤3000

E: 考察

美味しさを最大化する食べ方が1つ決まったとき、最後に食べる料理を食べ始める時間 (※元の問題文では「注文」する時間) は T-1 分以前です。T-1 分経過するまで待ってから食べ始めたと考えることで、結局、「最後に食べる料理は T-1 分経過した時点で食べ始める」と決めつけてよいです。

逆にいうと、最後に食べる料理以外は T-1 分間で食べ終わらないといけません。食べる料理は、

• A(i) の値の合計が T-1 分以下であるという条件の下で、
• B(i) の値の合計が最大になるもの、

であり、これはまさにナップサック問題と同じ状況です。

このナップサック問題を解いた後、まだ食べてない料理のうち最も B(i) の高いものを線形探索して食べればよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc145/submissions/8480672