AtCoder のプログラミングコンテスト ABC 121 に参加しました。4週連続の ABC-only 回です。
競プロ参戦記
この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細はリンク先を参照してください。
- 筆者の回答は Rust (1.15.1) で書いています。
- 前回: 競プロ参戦記 #35 Decayed Bridges | ABC 120
AtCoder Beginner Contest 121
問題一覧: https://atcoder.jp/contests/abc121/tasks
A - White Cells
問題概要: H 行 W 列のマス目がある。h 個の行を選んで、選ばれた行のマスを黒に塗った。同様に w 個の列を選んで、選ばれた列のマスをすべて黒に塗った。黒に塗られなかったマスは何個あるか数えよ。
考察:
例えば H=3, W=2, h=2, w=1 なら次のようになります。
はじめはすべて白:
..
..
..
2つの行を黒で塗ったら:
**
**
..
1つの列を黒で塗ったら:
**
**
*.
行を黒で塗るときに塗られるのが h×W 個、列を黒で塗るときに塗られるのが w×H 個、なのでその和を白マスの個数 H×W から引けばいいんですが、これでは黒に2回塗られたマスを2重に数えてしまっているので、その分だけ戻します。
黒で2回塗られるマスは、行と列の両方が選ばれているマスなので、h×w 個です。
結局、答えは H * W - (h * W + w * H) + h * w になります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc121/submissions/4518341
B - Can you solve this?
問題概要: N 個のソースコード、M 個の整数、N×M の行列 A が与えられる。次の条件を満たす y (1≤y≤N) の個数を求めよ。
A[y][1]・B[1] + A[y][2]・B[2] + .. + A[y][M]・B[M] + C > 0
考察:
実際にループを回して計算すればいいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc121/submissions/4517700
線形代数の言葉でいえば「積 AB の成分で -C を超えるものの個数を求めよ」ということになりますが、なんか意味のある量なんですかね。
C - Energy Drink Collector
問題概要: N 軒の店がある。i 番目の店では栄養ドリンクの在庫が B_i 本あり、1本あたり A_i 円である。M 本の栄養ドリンクを買うとき、支払う合計金額の最小値を求めよ。
考察:
どの店から買っても同じ栄養ドリンクなら、安い店から買っていくのがベストです。店を栄養ドリンクの値段が安い順に並び替えて、M 本に達するまで上位の店から可能なかぎりの栄養ドリンクを買い漁っていけばOK。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc121/submissions/4516633
抜粋:
let (N, M) = read!(usize, usize); // 入力
let mut T = read!(i64, usize; N); // (A, B) のベクタ
// 値段が安い順にソートします
T.sort();
let mut sum = 0_i64; // 支払った合計金額
let mut num = 0; // 購入した栄養ドリンクの本数
for (a, b) in T {
// 「ほしい栄養ドリンクの本数」と「買える栄養ドリンクの本数」の小さいほう
let k = min(M - num, b);
sum += (k as i64) * a; // この店に支払った金額
num += k; // この店で購入した本数
}
println!("{}", sum)
M 本買った後に break するのを忘れていますが、num = M のとき min(M - num, b) = 0 だから「0本買う」(冷やかし)を繰り返すだけで、誤答にはなりませんでした。
D - XOR World
問題概要: A 以上 B 以下のすべての整数の XOR をとったものを f(A, B) とおく。整数 A, B が具体的に与えられるので、f(A, B) を計算せよ。
考察:
排他的論理和 XOR が何かについてはリンク先にも載っていますが、簡単にいえば各ビットにつき互いに異なるなら 1、同じなら 0、にする操作です。
XOR の重要な性質として X ^ X = 0 があります。これを利用すれば、
f(A, B) = f(0, B) ^ f(0, A - 1)
と書けます。f(0, A - 1) の部分がすべて対消滅を起こすからです。具体例:
A=3, B=5
f(0, 2) = 0 ^ 1 ^ 2
f(0, 5) = 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5
f(3, 5) = 3 ^ 4 ^ 5
f(3, 5) = f(0, 2) ^ f(0, 5)
そういうわけで f(A, B) の代わりに f(0, A - 1) と f(0, B) を計算できればよいことが分かりました。(A = 0 のケースに注意。)
問題の理解を深めるため、具体例をみていきます。f(0, X) を X = 0 から 15 ぐらいまで実際に計算してみます。累積和のアルゴリズムを利用すれば O(N) ステップです。
x bin f(0, X)
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0000
4 0100 0100
5 0101 0001
6 0110 0111
7 0111 0000
8 1000 1000
9 1001 0001
10 1010 1011
11 1011 0000
12 1100 1100
13 1101 0001
14 1110 1111
15 1111 0000
f(0, X) の列を眺めると次のことが分かります:
- 最下位桁は 0, 1, 1, 0 の繰り返しになっていそう
- 下から2番目の桁は 0, 0, 1, 0 の繰り返しになっていそう
- 下から3番目の桁は 0, 0, 0, 0; 1, 0, 1, 0 の繰り返しになっていそう
- 下から4番目の桁は 0, 0, 0, 0; 0, 0, 0, 0; 1, 0, 1, 0; 1, 0, 1, 0 の繰り返しになっているかも
- 下から h 番目の桁は 0, 0, 0, 0, ..; 1, 0, 1, 0, .. の繰り返しになっていてくれ
最後の一般化は、bin の列をみると以下のように確認できます。h = 1 を除いて、下から h 番目のビットは 0, 0, 0, 0, ..; 1, 1, 1, 1, .. という並びになっています。これを XOR で累積和を取ると予想通り 0, 0, 0, 0, ..; 1, 0, 1, 0, .. です。
次にこれを具体的な判定条件として記述します。Z = f(0, X) の値はビットごとに以下のように判定できます:
- 最下位桁が 1 なのは、X % 4 が 1, 2 のとき
- 下から h (≥ 2) 番目のビットがゼロなのは、2^h で割った余りが 2^(h - 1) 以上の偶数のとき
あとはこれをコードに落とし込めばOKです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc121/submissions/4522813
ちなみに上記の具体例を生成するコード:
fn main() {
let mut s = 0;
for i in 0..16 {
s ^= i;
println!("{:2} {:04b} {:04b}", i, i, s);
}
}
(追記) 想定解法はもっと賢いようです。
今回の教訓
今回の問題から学べる教訓のコーナー！
- 「A 以上 B 以下」は「0 以上 X 以下」に変形できるかも
- XOR の結果がビットごとに決められるかも