ARC です。C完でした。

第一回日本最強プログラマー学生選手権-予選-

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

A - Takahashi Calendar

問題概要: 整数 M, D が与えられる。1年が1月からM月まであり、各月は1日からD日まである暦を考える。積の日が年に何日あるか数えよ。ただしm月d日が積の日であるとは、dの1桁目と2桁目をそれぞれ d1, d2 とするとき、以下の条件がすべて成り立つことをいう:

d1 ≥ 2
d2 ≥ 2
d1 * d2 = m

制約: M≤100, D≤99

A: 考察

M, D の値が小さいので、1年間に出現するすべての日付を列挙できます。それぞれが積の日の条件を満たすか判定して、数えればよいです。

    let mut count = 0;
    for m in 1..M + 1 {
        for d in 1..D + 1 {
            let x = d % 10;
            let y = d / 10;
            if x >= 2 && y >= 2 && x * y == m {
                count += 1;
            }
        }
    }
    println!("{}", count)

筆者の回答 (Rust, AC): https://atcoder.jp/contests/jsc2019-qual/submissions/7107323

B - Kleene Inversion

問題概要: 長さ N の整数列 A と、整数 K が与えられる。A を K 個つなげた数列の転倒数を数えよ。

転倒数とは、数列の2要素のペア x, y (ただし x < y) で A(x) > A(y) であるようなものの個数のこと。

制約: N≤2000, K≤10^9, A(i)≤2000

B: 考察

A を K 個つなげた数列 B は、K 個のブロック B(1) = A, B(2) = A, .., B(K) = A を連結したものということにします。

例えば A=(3, 1, 4), K=2 を考えます。転倒しているペアは以下の5通りです。

  | B(1)  | B(2)
B | 3 1 4 | 3 1 4
--+--------------
1 | 3 1
2 | 3         1
3 |     4   3
4 |     4     1
5 |         3 1

A 自身の転倒数は、転倒ペア (3, 1) があるので 1 です。このような転倒ペアが、数列 B のすべてのブロックに含まれています。つまり、単一ブロック内の転倒ペアの個数は (Aの転倒数) * K 個 です。

これら以外の転倒ペア、すなわち異なるブロックにまたがる転倒ペア (x, y) を考えます。例えば以下の (4, 1) などです:

    B | 3 1 4 | 3 1 4
    --+--------------
      |     4     1

このような A(2)=4 と A(1)=1 を使う転倒ペアは、K の値を増やすと多数出現します。

  | B(1)  | B(2)  | B(3)
B | 3 1 4 | 3 1 4 | 3 1 4
--+----------------------
1 |     4     1
2 |     4             1
3 |             4     1

具体的には、ブロックを2つ選ぶ選び方の数だけ繰り返し出現します。ブロックが2つあれば、左のブロックから A(2)=4 を、右のブロックから A(1)=1 を選ぶことで、この種の転倒ペアを1個見つけられるからです。

K 個あるブロックから2つを選び方は C(K, 2) = K(K-1)/2 通りです。

まとめると、A(i) > A(j) (i < j でも i > j でも可) であるようなペア (i, j) 数を X とするとき、 複数のブロックにまたがる転倒ペアの個数は X * K * (K-1)/2 個 です。

X は i, j を全列挙すれば数えられます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/jsc2019-qual/submissions/7111261

C - Cell Inversion

問題概要: 2N 個のマスがある。各マスは白か黒である。i 番目のマスの色 S(i) が与えられる。以下の操作をちょうど N 回行う。ただし、同じマスを2回選ぶことはないとする。最終的にすべてのマスを白にする操作手順を数えよ。

操作: 2つのマス x, y (x < y) を選ぶ。x, y およびそれらの間にあるマスの色をすべて反転する。

C: 考察

例えば S=BWWB, N=2 なら、以下の N=2 回の操作によりすべてのマスを白にできます。

    BWWB
    [-]     操作1 ([-] の範囲内の色を反転)
    WBBB
     [-]    操作2
    WWWW

ここで問題を言い換えます。W, B をそれぞれ 0, 1 に置き換えると、色の反転は x → 1 - x になり、「すべて白」は「すべて 0」になります。上と同じ例は、以下のように書けます。

    1001
    [-]     操作1 ([-] の範囲内をそれぞれ x → 1-x に変換する)
    0111
     [-]
    0000

反転だと少し考えにくいので、加算にします。範囲内のマスにそれぞれ 1 を加算して、最終的にすべての要素が偶数になればOK、という問題にします。

    1001
    [-]     操作1 ([-] の範囲内にそれぞれ +1 する)
    2111
     [-]
    2222    すべて偶数だからOK

こうしてみると操作の順番はもう無意味です。2つの操作の順番を交換しても結果は同じですし、範囲の選び方も始点と終点の位置さえ変えなければ同じです。

同じマスを2回選べないことを考えると、操作手順とは、各マスに [ (操作の始点) と ] (操作の終点) を割り当てることと同じです。

    1001
    [[]]    操作 (d 重の [] の内側にある各要素を +d する)
    2222    すべて偶数だからOK

このような [] からなる文字列は左から偶奇を計算すれば一通りに定まります。(カッコの対応が破綻するときは操作手順なし、です。)

後はこの文字列を使って、操作手順を計算すればいいです。

各操作は、どの [ と ] を対応させるかにより決まります。例えば右端の [ は、それより右にある ] のどれかと対応するので、2通りです。

    [ [ ] ]
      ^ ~~~ 未対応の ] は2個
      2

その左の [ は、右側にある2個の ] のうち、先ほどの [ と対応しなかった1個と対応させることになるので、1通りです。これらを掛け合わせればよいです。

    [ [ ] ]
    ^ ~~~~~ 未対応の ] は1個
    1

最後に、操作手順をシャッフルするために N! を掛ければ完成です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/jsc2019-qual/submissions/7117479

本番では、操作の順番が無意味であることに気づくのに時間がかかってしまいました。小さいケースの操作手順を全探索するコードを書いている途中に気がつきました。

解説生放送では私の考察より遥かに明快な考え方が解説されているので、見ましょう。