ABC 125 に参加しました。
競プロ参戦記
この連載記事では、着手した問題の考察を自分なりに書いていきます。
AtCoder Beginner Contest 125
- 問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc125/tasks
A - Biscuit Generator
問題概要: ビスケット生産装置を時刻 0 に起動すると、各整数 k について、時刻 kA にビスケットが B 枚生産される。時刻 T + 0.5 までに生成されたビスケットの総数を求めよ。
考察:
時刻 t を 0 から T まで動かして、各時刻 t について条件 t = kA つまり t % A == 0 が成り立つならビスケットの総数を加算する、というループで計算できます。O(T) 時間ですが、T ≤ 20 なので間に合います。
もう少し考察すると、時刻 T + 0.5 までに ビスケットの増産が何回起こるか を計算することで解けることが分かります。例えば A = 3, T = 9 なら3回です。T = 10, 11 でも 3回なので、端数は切り捨てです。つまり floor(T / A) 回となります。
B * T / A
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc125/submissions/5144209
B - Resale
問題概要: N 個の宝石がある。i 番目の宝石のコストは C[i] で、価値は V[i] である。好きな数の宝石を選ぶ。選ばれた宝石のコストの総和を Y、価値の総和を X とするとき、X - Y の最大値を求めよ。
考察:
(追記: この考察より遥かに簡単な解法で解けます。公式の解説 PDF 参照)
考察の余地は広そうですが、制約を見ると N ≤ 20 なので、全探索できます。宝石の選び方の場合の数は、各宝石につき「選ぶか選ばないかの」2通りなので、2^20 通り (約 10^6 通り) です。
さて、実装の話になりますが、要素数 64 以下の集合の列挙にはビット演算を使うと便利です。(ビットセット)
整数を2進数表記したとき、下から i 番目なら 1 なら「要素 i が集合に含まれている」、0 なら「含まれていない」と考えることで、整数を集合の代わりにできます。
具体的には、要素数 N (≤64) の集合が、0 以上 2^N 未満の整数と 1:1 に対応します。(2^N 以上の整数は集合と対応しない桁を持つのでダメ。) つまり 0 以上 2^N 未満までループを回すだけで集合の列挙が可能 です。
要素 i が集合に含まれているか、つまり整数の下から i 番目のビットが立っているかは、2^i (下から i 番目のビットだけからなる数) との論理積で検査できます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc125/submissions/5145035
C - GCD on Blackboard
問題概要: 長さ N の整数列 A が与えられる。いずれか1つの要素を、好きな整数 (ただし 1 以上 10^9 以下) に置き換えるとき、数列 A の最大公約数の最大値を求めよ。
考察:
最大公約数 (GCD) は「ユークリッドの互除法」というアルゴリズムにより対数時間で計算できます。
仮にいずれかの要素をうまく書き換えて数列 A の最大公約数 G を最大にできたとします。書き換えなかった整数の最大公約数を g とするとき、書き換えられた整数 X はどんな値でしょうか？
GCD を取ることによって公約数が大きくなることはないので、G = GCD(g, X) から G ≤ g がいえます。X = g とすれば最大化できます。(G = GCD(g, g) = g)
そういうわけで、どの要素を書き換えるかを決めたら、他の要素の最大公約数 g が解となります。この計算は、左右から 累積和 (累積GCD) を使うことによって O(1) 時間でできます。
具体的には、次のような2つの累積和(GCD)を事前に用意します:
- X[i] = GCD(A[0], A[1], .., A[i-1])
- Y[i] = GCD(A[N-1], A[N-2], .., A[i+1]) (Aを逆順にして累積和をとる)
こうしておくと、i 番目を書き換えると決めたとき、i 番目以外の GCD の値は g = GCD(X[i], Y[i]) で決まります。
「どの要素を書き換えるか」を全通り試しても間に合います。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc125/submissions/5143605
別解: 約数列挙
累積和を使う代わりに、約数を列挙する解法をツイッターで拝見しました。(参考) 興味深い解法なので追記します。
最適解 (1つの要素を書き換えた後の最大公約数の最大値) を G とします。書き換えられたのが A[0] か否かで場合分けしてみます。
もし A[0] を書き換えて最適解 G を得られたのなら、G は A[0] 以外の最大公約数です。特に、G は A[1] の約数といえます。
そうでなければ、G は A[0] 以外のどれかを書き換えることで求まったはずです。このとき G は A[0] の約数になります。
したがって、G は A[0] の約数か A[1] の約数に限られます。これらの約数は O(√X) 個しかないので全列挙可能です。(X = A[0] + A[1] ≤ 2 * 10^9)
ここで列挙した約数が A の公約数になるかどうかは、実際に A の各要素を割ってみることで確認できます。整数 d で A の要素のうち N-1 個以上が割り切れる (☆) なら、割り切れなかった要素を書き換えることで d を A の公約数にできます。
結局、A[0] の約数か A[1] の約数のうち、そのような条件 (☆) を満たすものの最大が G です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc125/submissions/5176474
振り返ってみると、解の候補を効率よく列挙する → 各候補が解であるか確認する、という流れになっていて、他の問題にも応用できそうです。
D - Flipping Signs
問題概要: 長さ N の整数列 A が与えられる。隣り合う2つの整数にそれぞれ -1 をかける、という操作を好きなだけ行ったあと、総和 (ΣA) の最大値を求めよ。
考察
操作では要素の絶対値が変化せず、符号だけ変わります。そのため、絶対値と符号を分離して表現すると分かりやすいです。例えば (-10, 5, -4) なら
-1 +1 -1
10 5 4
のように2つの数列を考えます。操作では下の数列は変化しません。操作が上の数列にどのように影響するかを見ていきましょう。
考察: 交換操作
上の数列で +1 と -1 が隣り合っているところにそれぞれ -1 をかけると、+1 と -1 が入れ替わります。つまり、
- 隣接する +1 と -1 を交換する
という操作が好きなだけ行えます。したがって、 +1 と -1 は好きな順番に並べ替えることが可能 です。
考察: 相殺操作
上の数列で2つの -1 が隣接しているところにそれぞれ -1 をかけると、両方 +1 になります。つまり、
- 隣接する -1 と -1 を +1 に置き換える
という操作が好きなだけ行えます。+1 と -1 は好きな順番に並ぶので、「隣接する」という条件は無意味です。そのため、-1 が2つあれば、両方 +1 にできる といえます。
いまの問題では -1 より +1 の方が常に「良い」ですから、可能なかぎり多くの -1 を +1 にしたいです。つまり、最終的に -1 は1個または0個にするのがベストです。-1 が残ったら、それは絶対値が最小である数につくように移動させるのがベストです。
まとめ
絶対値の総和を S、最小値を m とします。
もし負数の個数が偶数なら、答えは S。奇数なら、(S - m) - m つまり S - 2m が答えとなります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc125/submissions/5146875
今回の教訓
- B: 実装する前に入力例を確認したほうがいいかも
- C: 最適な操作をした後の状態を考えるといいかも
- D: 交換ができるなら並び替えができる