ABC-only 回です。
競プロ参戦記
この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細はリンク先を参照してください。
- 前回: 競プロ参戦記 #39 Minimum Triangulation | エデュフォ 62 Div.2
AtCoder Beginner Contest 123
A - Five Antennas
問題概要: 5本のアンテナが左から順に位置 A, B, C, D, E に配置されている。2本のアンテナは、間隔が K 以下なら直接通信できて、そうでなければできない。直接通信できないアンテナのペアがあるか判定せよ。
考察:
アンテナのペアは10通りなので、そのすべてについて調べてもいいですが、もっと簡単にできます。
例えば A と C の間の距離が K 以下なら、A と B の間も K 以下です。このことから、A と E の間の距離が K 以下なら A-B, A-C, .. すべてのペアについて距離が K 以下であることが分かります。
したがって、A-E 間の距離が K 以下か否かだけ判定すれば十分です。
println!("{}", if E - A <= K { "Yay!" } else { ":(" });
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4850431
B - Five Dishes
問題概要: 5種類の料理があり、それぞれ提供時間が A, B, C, D, E である。注文ができるのは、時刻が10の倍数のときに限る。これらの料理を好きな順番で1つずつ注文するとき、最後の料理が提供される時刻を求めよ。
考察:
料理をどの順番で頼むかは 5! = 120 通りしかないので、全列挙すればよいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4849640
C - Five Transportations
問題概要: 都市が6つあり、前から 1, 2, 3, 4, 5, 6 とする。隣接する2つの都市の間にはそれぞれ1つだけ交通機関があり、1分につき A, B, C, D, E 人を輸送する。はじめ、N 人が都市 1 にいる。全員が都市 6 に行くまで最短で何分かかるか求めよ。
考察:
都市 6 に最後に到着する1人 X 氏に注目します。この人は他の人に必ず席を譲るので、可能な限り遅い便に乗るとします。
はじめ都市 1 から 2 に行くには ceil(N / A) 分かかり、最後の便は ceil(N / A) 本目です。
次に、都市 2→3 の輸送を考えます。A ≤ B なら、1→2 に移動した人はみな次の1分で 2→3 と移動できます。
A > B なら、都市 1→2 に移動した人の一部だけが次の1分で 2→3 に移動できます。人々は次々に都市 2 に送られてくるため、「はじめから N 人全員が都市 2 にいる」と考えても同様です。
輸送は時刻 1 から始まるので、最後の便は時刻 1 + ceil(N / B) です。
都市 1→2 に最後に輸送された X 氏は、時刻 ceil(N / A) に都市 2 について、次に乗る便の出発時刻が 1 + ceil(N / B) なので、その差だけ待つことになります。
このように X 氏が乗る便がどの時刻に出発するかを計算して、待ち時間を加算していくことで解けます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4847281
// 最後の便
let mut s = 0;
// 現在時刻
let mut t = 0;
for x in X {
// 次の交通機関の最後の便が何本目か
let y = (N + x - 1) / x;
// 待ち時間を加算
if y > s {
t += y - s;
s = y;
}
// 1分ずつずれていく
t += 1;
}
t -= 1; // 最後の t += 1 をキャンセル
D - Cake 123
問題概要: 3種類のキャンドルがあり、キャンドル 1, 2, 3 のついたケーキがそれぞれ X, Y, Z 種類ある。キャンドル 1 のついた x 番目のケーキの美味しさを A[x] とする。同様にキャンドル 2 の y 番目が B[y]、キャンドル 3 の z 番目が C[z] の美味しさを持つ。キャンドル 1, 2, 3 のそれぞれからケーキの種類を1つ選ぶ組み合わせを、美味しさの和が高い順に並べたとき、上位 K 個の美味しさの和を列挙せよ。
考察:
ケーキの種類の組み合わせを決めたとき、キャンドル 1, 2, 3 がついたものの美味しさをそれぞれ a, b, c という変数で表すことにします。
組み合わせの総数 X * Y * Z が十分に小さければ、美味しさの和を実際に列挙してソートすることで解けます。実際には X * Y * Z は 10^9 のオーダーなので、すべて列挙するには時間もメモリも足りません。
組み合わせの数を減らすため、(b, c) だけ列挙することを考えます。つまり b + c の値からなる配列 W を作ってソートしておきます。a の値を決めたとき、a + b + c の値は降順に a + W[0], a + W[1], .. です。
はじめ、美味しさの最大値の候補は A[0] + W[0], A[1] + W[0], .. です。この中から最大値を探して出力します。仮に A[i] + W[0] が最大だったとしましょう。
A[i] + W[0] はもう列挙できませんが、A[i] のケーキを使う組み合わせの中で次に大きい美味しさの和は A[i] + W[1] です。また、A[i] のケーキを使わない組み合わせの美味しさの和の最大は A[x] + W[0] のままです。
したがって、2番目に大きい美味しさの和の候補は A[0] + W[0], A[1] + W[0], .., A[i] + W[1], .., A[i + 1] + W[0], .. です。以降も同様に W の添字を1つずつ増やしながら列挙していけば、常に「美味しさの和の最大値の候補」を X 個以下に保ったまま列挙を進めることができて、十分に高速です。
計算量は事前計算が O((Y + Z) log (Y + Z))、列挙部分が O(KX) 時間で、全体としては大きく見積もって O(KN log N) (N = X + Y + Z) です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4858437
反省:
考察では省略しましたが、かなり迷走しつつなんとか辿り着いたという感じでした。
今回の教訓
- A: 三角不等式
- B: 全列挙で解ける問題は全列挙で解いていい
- C: 複数のものを動かすとき、1つの動きに注目すると何か分かるかも