今週は実質 ABC/ARC の企業コンでした。

diverta 2019 Programming Contest

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #44 Three Religions | コドフォ #556 Div.2
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/diverta2019/tasks

A - Consecutive Integers

問題概要: N 個の整数 1, 2, .., N のうち連続する K 個を選ぶ選び方は何通りか。

考察:

具体例を試すと簡単に法則性が見つかって、N - K + 1 だと分かります。例えば N=7, K=4 だと4通りです。

    N=7, K=4

    1 2 3 4 5 6 7
    ^^^^^^^
      ^^^^^^^
        ^^^^^^^
          ^^^^^^^

形式的に考えるなら、選ばれる区間の左端 (最小値) に注目して数えるのがよいです。上の例でいうと 1, 2, 3, 4 の4つ。

一般に m が選ばれる区間の最小値であるためには、m 以上の値が K 個必要です。そのため N から大きい順に K-1 個の値は区間の最小値になりません。N 個のうち K-1 個を除くので、N - K + 1 が答えです。

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

B - RGB Boxes

問題概要: 以下の3種類の箱が売られている。これらの箱を購入して、ちょうど N 個のボールを買う方法を数えよ。

R 個のボールが入った赤色の箱
G 個のボールが入った緑色の箱
B 個のボールが入った青色の箱

考察:

精選10問でやったやつです。

赤・緑の箱を購入する個数を全探索すれば、ボールの個数の合計を N にするために買うべき青の箱の個数が確定するので、2重ループを回すことで解けます。

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

C - AB Substrings

問題概要: N 個の文字列がある。これらの文字列を好きな順番に並び替えて連結したとき、部分文字列に含まれる AB の個数の最大値を求めよ。

考察:

文字列の途中に含まれている AB は、連結の順番に関係なく数えられるので無視していいです。これらは最初に数えておくことにします。

後は文字列の連結部分に出現する AB の個数を最大化すればいいです。連結部分以外は興味がないので、各文字列の最初と最後の文字以外は除去していいです。結果、文字列は以下の4パターンになります。

BA
By
xA
xy

(x は B でない任意の文字、y は A でない任意の文字。)

理想的には以下のように A, B がすべて AB の形で並ぶようにするとベストです。

xA BA BA .. BA By    xA By  xA By  ..  xA By    xy .. xy

これは xA, By がどちらも1つ以上存在し、xA, By の個数が等しいという仮定をしています。実際にはコーナーケースを考慮する必要があります。

BA が存在しないときは xA, By を交互に並べて、ペアになった個数だけ AB が出現します。これは xA, By の小さい方の個数です。以下、BA が存在するとします。

xA が存在しないときは、BA の左側の B をすべては活用できないので、BA を1つ xA に変換しても AB の個数は減りません。同様に By がないときも BA を 1つ By に変換できます。これにより xA, xB が存在することにできて、後は上記のように並べればいいです。

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

D - DivRem Number

問題概要: 整数 N が与えられる。N 以下の正の整数 m で N を割ったとき商と余りが等しいとする。そのような m の総和を求めよ。

考察:

N を m で割ったとき商が q で余りが r になるというのを式で表すと以下の通りです。

    N = q・m + r       (0 ≤ r < m)

ここで q = r を代入すると

    N = q・m + q = (m + 1)・q

となり q が N の約数に限られることが分かります。N の約数は O(√N) しかないので全列挙可能です。

したがって、N の約数 q を列挙して m = (N / q) - 1 が条件を満たすか確認すればいいです。

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

約数の列挙

正整数 N の正の約数 d を列挙するときは以下の2つに注目します。

d が N の約数なら N/d も N の約数
d ≤ N/d のとき d ≤ √N

1つ目は 約数はペアで出現する という話です。これは d・(N/d) = N からいえます。例えば N=12 なら以下の通り。

d = 1 に対して N/d = 12 も約数
d = 2 に対して N/d = 6 も約数
d = 3 に対して N/d = 4 も約数

2つ目は 約数のペアのうち小さい方が最大で √N という話です。例えば N=9 なら最大の約数は √9 = 3。(証明は式変形するだけ。)

そういうわけで √N 以下である「約数のペアのうち小さい方」を列挙すれば大きい方の約数もすべて列挙できて、全体として O(√N) 時間です。

fn divisors(N: i64) -> Vec<i64> {
    let mut ds = vec![];
    let mut d = 1;
    while d * d <= N {
        if N % d == 0 {
            ds.push(d);
            ds.push(N / d);
        }
        d += 1;
    }
    ds
}