AtCoder Beginner Contest 131

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

A - Security

問題概要: 4桁の数字列が与えられる。同じ数字が連続する箇所が存在するかを判定せよ。

A: 考察

いずれかの i (0≤i≤3) について S(i) == S(i+1) が成り立つかを判定すればいいです。もし S(i) == S(i+1) になる i があるなら、同じ数字が連続していて、そうでなければ連続していません。

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

B - Bite Eating

問題概要: N 個のリンゴがある。i 番目のリンゴの味は L+i-1 である．リンゴからアップルパイを作るとき、アップルパイの味は元のリンゴの味の総和になることが知られている。N 個のリンゴのうち、i 番目のリンゴを除く N-1 個からアップルパイ A(i) を作る。すべてのリンゴを使って作るアップルパイとの味の差の絶対値が最小であるような、アップルパイ A(i) の味を求めよ。

B: 考察

問題文の読解で疲れたので、考察はさておき言われた通りのコードを書いて、さっさと AC を見たい気分です。

すべてのリンゴを使って作るアップルパイの味 A' を始めに計算します。各リンゴ i につき、このリンゴを除くアップルパイの味 A(i) = A' - (L+i-1) を計算できます。

アップルパイの味の差の絶対値の最小値を変数で持っておくとして、いまの値 |A' - A(i)| が最小値を更新したら A(i) をベストな味として記録します。

最後に最小値を更新したときのベストな味を出力すれば OK です。

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

C - Anti-Division

問題概要: 整数 A, B, C, D が与えられる。A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を求めよ。

制約: A≤B≤10^18

C: 考察

B の値が巨大なので、A 以上 B 以下の整数を列挙することはできません。

例えば A=1, B=9, C=2, D=3 では以下のようになります。

        1 2 3 4 5 6 7 8 9
    C=2 x   x   x   x   x
    D=3 x x   x x   x x

C, D 両方に x がついている (C, D の両方で割り切れない) のは 1, 5, 7 の3つです。

「C でも D でも割り切れない」という条件は複雑なので、いったん D のことは忘れて、「C で割り切れない整数を数える」ことを考えます。

C で割り切れない整数は、C の倍数ではない整数の数です。C の倍数の個数を総数 (B-A+1 個) から引けばいいです。

同様に、「C でも D でも割り切れない」整数を数える代わりに、「C か D で割り切れる」整数を数えることを考えます。

C の倍数の個数と D の倍数の個数を総数から引けばよさそうです。ただし、C と D の公倍数を二重に引いてしまうので、埋め合わせとして C, D　の公倍数の個数を改めて足す、という操作をします。(包除原理)

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

D - Megalomania

問題概要: 作業が N 個ある。i 番目の作業は、A(i) 時間かかり、時刻 B(i) が締め切りである。2つの作業を同時に行うことはできない。時刻 0 から好きな順番で作業を行うとき、すべての作業の締め切りを守れるか、判定せよ。

D: 考察

締切の早いものから順番にやればいいです。もしこの順でやって間に合うなら、間に合います。この順でやって間に合わないからといって、絶対に間に合わないとはいえませんが、以下の理由で間に合わないと判断してよいです。

締切の早い順にやって間に合わないと仮定します。最初に間に合わない作業 i が存在します。このとき作業 i より前に完了しないといけない作業の作業時間の合計が B(i) を超えているので、どのように作業を並び替えても、作業 i は間に合いません。

結局、締切の時刻で作業をソートし、各作業につき順番に、A(i) 時間作業して、締切が守られたか (現在時刻が B(i) 以前か) を判定する、というループで解けます。

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

E - Friendships

問題概要: 整数 N, K が与えられる。以下の条件を満たす N 頂点の単純かつ連結な無向グラフが存在するか判定し、存在するなら一例を示せ。

条件: 頂点対 (u, v) のうち、最短距離が 2 に等しいものがちょうど K 個

E: 考察

例えば N=5, K=3 なら以下のグラフが条件を満たします。(1-3, 2-4, 3-5 という3つの頂点対の最短距離が 2 に等しい)

    1 -- 2 -- 3 -- 4 -- 5

入力例2によると N=5, K=8 では条件を満たすグラフはないそうです。

条件を満たすグラフが存在するような K の最小値と最大値を考えてみます。

すべての頂点間に辺を引くと最短距離がすべて 1 であるようなグラフを作れるので、K=0 は常に構築可能です。

頂点対の個数は N(N-1)/2 ですが、K = N(N-1)/2 はありえません。すべての頂点間の最短距離が 2 という状況では、辺が存在しないからです。(辺があったら、その両端の頂点間の最短距離が 1。)

N 頂点の連結グラフには少なくとも N-1 本の辺が存在することから、K の最大値の上限として N(N-1)/2 - (N-1) が考えられます。実はこれは達成可能です。

以下の構築手順があります。

グラフ問題の定石として、パスグラフとスターグラフを考えるとよいらしいです。パスグラフはもう見たので、スターグラフを用意します。

このグラフではすべての頂点間の最短距離が 2 以下になります。いま引かれている辺をスターグラフの辺と呼ぶことにします。

次に、このグラフのすべての頂点間に辺を引きます。そこからスターグラフの辺ではない辺を K 本選んで取り除きます。

取り除かれた辺の両端の頂点対の最短距離は 2 です。(スターグラフの辺が存在するため。)　他の頂点対の最短距離は、間に辺があるので 1 です。したがって、このグラフは条件を満たします。

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