DDCC2019 参加記録（コード部門）＆解説（A, B, D）

今回はオンサイト参加でした！

コード部門以外のもろもろ参加記はまた別途書こうかなと思っています。この記事ではいつものように問題の解説を。

f:id:betrue12:20190120141813p:plain

本番はAB2完でしたが…A, B, D問題について書きます。

A - レース (Race)

解法

連続した氷マスの長さに応じて所要時間が変わるので、連続した氷マスそれぞれの塊について考えます。

雪マス1つを氷マスに変えたとき、もし別々の氷マスの塊が結合してしまうようであれば厄介ですが、制約からそのようなことは起こりません。そのため、氷マスを1つ増やして一番得になる氷マスの塊に付けることを考えればよく、それは最も長い氷マスの塊になります。

あとは実際に計算です。私のコードではまず氷マスの塊の長さを全て列挙し、一番大きい要素に1加え（氷マスが1つもない場合に注意）、最後に計算しています。

ACコード

B - 大吉数列 (Array of Fortune)

解法

$a_{i} \ge a_{j}+K$ かつ $i \lt j$ を満たすペア $(i, j)$ の個数というものは、「転倒数」によく似ています。実際、 $K = 1$ とするとこれは順列の転倒数そのものになります。この記事ではこのペアの個数を $K$ 転倒数と呼ぶことにします。

転倒数が最大になるのは数列が逆順ソートされているときでした。 $K$ 転倒数が最大になるのも、同様に数列が逆順ソートされているときです。まずはその個数を求めます。

f:id:betrue12:20190120164606p:plain

図に示すように、長さ $N$ の順列を逆順ソートしたときの $K$ 転倒数は、 $1, 2, ..., N-K$ を全て足したものになり、計算すると $\frac{(N-K)(N-K+1)}{2}$ です。与えられた $R$ がこの値より大きい時は、どうやっても条件を満たせないので No Luck で終了です。以降、そうでないときに数列を構成する方法を考えます。

まず $1, 2, ..., N$ という正順ソートされた数列を考えると、この数列の $K$ 転倒数はもちろん0です。この数列の末尾要素 $N$ を先頭に移動させると、 $1, ..., N-1$ までの要素との位置関係が逆になります。このうち $1, ..., N-K$ の値に対して $K$ 転倒数が増えるため、 $K$ 転倒数は $N-K$ 増えます。

次に $N-1$ を2番目に移動させると、同じように $K$ 転倒数は $N-K-1$ 増えます。このように「末尾の要素 $N-i$ を数列の $i$ 番目に移動させてきて、 $K$ 転倒数を $N-K-i$ 個増やす」という操作を、 $K$ 転倒数が $R$ を超えないところまで繰り返します。（「 $i$ 番目」は0-indexedです）

最後は $K$ 転倒数をぴったり $R$ に合わせるために微調整をする必要があります。といっても、同じように末尾の要素 $N-i$ を数列の $i$ 番目に移動させた後、増えすぎたぶんを戻すために1つずつ後ろに戻していくと考えると楽です。後ろに戻すときは $1, 2, ...$ といった小さい値から順に位置関係が戻っていくため、ぴったり $R$ になるまでは1つ戻すごとに $K$ 転倒数が1減っていきます。

f:id:betrue12:20190120165441p:plain

あとはこれを実装します。私の実装では全要素 $-1$ （空いていることを示す）で初期化したvectorを用意し、 $K$ 転倒数が $R$ になるまでは大きいほうから値を埋めていって、最後に空いているところに小さいほうから値を入れています。

ACコード

（C++）Submission #4039728 - DISCO presents ディスカバリーチャンネルコードコンテスト2019 本戦

D - DISCO!

公式解説とは違う方法で解いたので、その方法を書きます。

解法

もしクエリの全てが $L = 1$ 、つまり常に先頭からある右端までの部分列 DISCO の個数を答えるのであれば簡単です。「 $S$ の先頭から $i$ 文字目までに含まれる、 DISCO のうち $j$ 文字目までの部分列の個数」を $dp\lbrack i \rbrack \lbrack j \rbrack$ とするDPをしておけばよいです。この場合の答えは $dp\lbrack R \rbrack \lbrack 5 \rbrack$ です。

今回の問題の場合は $L$ も様々な値を取りますが、 $L=1$ のときの応用で解けないか考えてみます。

与えられたクエリ $L, R$ に対して、まず区間 $\lbrack 1. R \rbrack$ に含まれる部分列 DISCO の個数が先ほどのDPで分かっているとします。この個数をいくつかのパターンに分解します。

f:id:betrue12:20190120170554p:plain

求めたいのはこのパターンのうち一番上のものなので、それ以外の値を全て引けば答えが求められるはずです。

これらの値の求め方を考えます。例えばD | ISCO と分断されているパターンについて、この個数は区間 $\lbrack 1, L)$ に含まれる D の個数と区間 $\lbrack L, R \rbrack$ に含まれる ISCO の個数の積です。前者は $dp\lbrack L-1 \rbrack \lbrack 1 \rbrack$ です。次に後者ですが…これは元のクエリで問われている値の、頭の文字数が1文字少ないバージョンになっています。必要なDPテーブルの値さえ分かっていれば、これは今まで書いてきた方法と全く同じように求められるはずです。

DI | SCO と分断した場合も、区間 $\lbrack 1, L)$ に含まれる DI の個数と区間 $\lbrack L, R \rbrack$ に含まれる SCO の個数として同様に求められます。 DIS | CO、DISC | O についても同様です。最後の DISCO | となっているパターンは、 $dp\lbrack L-1 \rbrack \lbrack 5 \rbrack$ そのものです。

ここまでの議論を一般化します。「区間 $\lbrack L, R \rbrack$ の間に含まれる、 DISCO の末尾 $k$ 文字と一致するような部分列の個数」を $f(L, R, k)$ と置くと、クエリの答えは $f(L, R, 5)$ です。そしてこの値は先ほどの図で示したやり方を用いて、 $f(L, R, k-1), ..., f(L, R, 1)$ の値と、前計算したDPテーブルの値を用いて計算することができます。

このときDPテーブルの値は少し拡張する必要があって、例えば $f(L, R, 4)$ の計算では ISCO の個数を求めなければいけないので、先頭からの ISCO や I IS などの個数が必要となります。そのため、「 $S$ の先頭から $i$ 文字目までに含まれる、 DISCO のうち $j$ 文字目から $k$ 文字目までの部分列の個数」を $dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack$ とするDPテーブルを全て計算しておけば必要な値が揃います。