ABC に参加して、D完でした。

AtCoder Beginner Contest 139

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #61 Cell Inversion | 第一回日本最強プログラマー学生選手権-予選-
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc139/tasks

A - Tenki

問題概要: 'S', 'C', 'R' のいずれかからなる長さ 3 の文字列 S, T が与えられる。S(i) = T(i) となる i (1≤i≤3) を数えよ。

A: 考察

zip を使うとシンプルにかけます。文字列 S, T の同じ位置にある文字のペアからなるイテレータを作り、条件を満たす要素を数えればよいです。

    S.chars()
    .zip(T.chars())
    .filter(|&(s, t)| s == t)
    .count()

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

もちろん S.chars().collect::<Vec<_>>() で Vec<char> に変換したり、S.as_bytes() でバイト列として操作しても解けます。

B - Power Socket

問題概要: 電源プラグの差込口が1個ある。A個口の電源タップをいくつか使って、全体でB口以上の未使用の差込口を用意したい。必要な電源タップの個数の最小値を求めよ。

B: 考察

電源タップを k 個使うとします。差込口の総数は kA+1 で、そのうち k 個の差込口を使用しているので、未使用の差込口の数は k(A-1)+1 です。

条件 k(A-1)+1 ≥ B から k ≥ (B-1)/(A-1) が得られて、この除算の端数を切り上げた値が整数 k の最小値となります。

整数 x, y の端数切り上げの除算 ceil(x/y) は (x + y - 1)/y で求まります。(x を y で割った余りが1以上なら結果が1増えるようになっているため。)

    ((B-1) + (A-1) - 1)/(A-1)

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

C - Lower

問題概要: 左右一列に N 個のマスがある。左から i 番目のマスの高さは H(i) である。いずれかのマスを1つ選び、右隣のマスの高さがいまいるマスの高さ以下である限り、右隣のマスへ移動し続ける。移動回数の最大値を求めよ。

C: 考察

入力例1の各マスを選んだ時の移動回数を計算してみると法則性が分かります。

  H   10 >= 4 < 8 >= 7 >= 3
  d    1    0   2    1    0

マス i を選んだ時の移動回数を d(i) とします。i=N (右端) のとき、右に移動できないので d(N) = 0 です。

i < N のとき、右隣のマスに移動できるなら、そこからさらに d(i+1) マス移動するので、d(i) = d(i+1) + 1 になります。移動できないなら d(i) = 0 です。

このように右から順番に計算していくと d を O(N) 時間で求められます。最大値が答えです。

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

D - ModSum

問題概要: 整数 1, ..., N からなる順列 P(1), ..., P(N) を1つ選ぶ。 $\sum_{i=1}^{N} i % P_{i}$ の最大値を求めよ。

D: 考察

N=2 から 9 での最大値と順列は以下の通りです。

    最大値 : 順列
    1 : [[2, 1]]
    3 : [
        [1, 3, 2],
        [2, 3, 1]]
    6 : [[2, 3, 4, 1]]
    10 : [
        [1, 3, 4, 5, 2],
        [2, 1, 4, 5, 3],
        [2, 3, 4, 5, 1]]
    15 : [[2, 3, 4, 5, 6, 1]]
    21 : [
        [1, 3, 2, 5, 6, 7, 4],
        [1, 3, 4, 5, 6, 7, 2],
        [2, 3, 1, 5, 6, 7, 4],
        [2, 3, 4, 5, 6, 7, 1]]
    28 : [
        [2, 1, 4, 5, 6, 7, 8, 3],
        [2, 3, 4, 5, 6, 7, 8, 1]]
    36 : [
        [1, 3, 4, 5, 6, 7, 8, 9, 2],
        [2, 3, 4, 1, 6, 7, 8, 9, 5],
        [2, 3, 4, 5, 6, 7, 8, 9, 1]]

どうやら 2, 3, 4, ..., N, 1 の N(N-1)/2 が最大値のようです。

よく考えると P(i) で割った余りは P(i) 未満なので、総和の最大値の上限は 0 + 1 + ... + N-1 = N(N-1)/2 です。前述の順列は上限を達成します。

    N * (N - 1) / 2

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

E - League

問題概要: N 人の選手の総当たり戦の大会を行う。大会は複数日に渡って行われる。各選手は1日に最大1試合のみ行う。選手 i は、選手 A(i, 1), A(i, 2), ..., A(i, N-1) とこの順で試合を行う。この条件を満たすような試合の日程が存在するか判定し、存在するなら日数の最小値を求めよ。

制約: N≤1000

E: 考察

入力例2を考えます。選手 1 の次の対戦相手は選手 2 なので、初日に選手 1 の試合があるとしたら1対2です。

また、選手 2 の次の対戦相手が選手 1 なので、1対2の試合は実際に初日に行えます。

同様に選手 3, 4 も互いに相手を最初の対戦相手に指定しているため、3対4の試合も初日に行えます。

2日目は、1対3の試合を行えますが、選手 2, 4 は試合を行えません。選手 2 の次の対戦相手は選手 3 ですが、選手 3 の次の対戦相手は選手 1 なので、2対3の試合を行うのは1対3の試合より後でなければいけないからです。

同様に、選手1を次の対戦相手に指定している選手4も、2日目には試合を行えません。

このように、2人の選手が互いに相手を次の対戦相手に指定しているとき、この2人の試合を組むのが最善 です。それ以外の試合は組むことができません。試合を全く組めない状態になったら、条件に矛盾があり、試合の日程が存在しないと判定してよいです。

これを素朴に実装すると O(N^3) 時間かかります。大会の日数の上限が O(N^2) であり、各日で試合を構成するのに O(N) 時間かかるからです。

1日分の試合を組むときに、試合を行える可能性がある選手の候補を絞ることで高速化できます。2日目以降、選手 i, j が試合を行えるとすると、どちらかが前日に試合を行っていたはずです。というのも、前日にどちらも試合を行っていないのに i, j が試合できる (= i, j が互いに相手を次の対戦相手に指定している) 状態というのはありえません。それなら前日に試合が組まれたはずだからです。

そういうわけで、「前日に試合を行った選手」の集合を持っておき、これらの選手の試合を組めるかどうかだけ調べればよいです。これにより計算量は O(試合数) = O(N^2) に落ちます。

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

本番ではトポロジカルソートで矛盾判定と試合順の計算をしてから「何らかの方法で」最小日数を計算する方針に固執してしまっていました。「互いに指名していない選手は試合できない」ということに気づいていなかったのでダメですね。