2018-09-15

AtCoder Regular Contest 100 F - Colorful Sequences

問題

https://beta.atcoder.jp/contests/arc100/tasks/arc100_d

解法

「全ての列についての $A$ に一致する連続する部分列の個数の総和」から「カラフルでない列についての $A$ に一致する連続する部分列の個数の総和」を引く方針で考えます。前者は簡単なので省略します。後者は $A$ がカラフルな場合は $0$ なので、以下カラフルでないものとします。
まず次のDPを考えます。

$dp[i][j]=$ ある特定の長さ $i$ のdistinctな列の後に、 $j$ 個の要素を繋げてできるカラフルな列の個数

次が成り立ちます。

$dp[i][j]=\displaystyle \frac {dp[i-1][j+1] - \displaystyle \sum_{i'=1}^{i-1} dp[i'][j]} {K-i+1}$

ただし、このDPを初期化するには、 $dp[1][j]$ が分かっていないといけません。そこで、

$dp'[j][k]=$ ある特定の $1$ 項の後に、 $j$ 個の要素を繋げてできるカラフルな列であって、distinctなsuffixの最大長さが $k$ であるものの数

というものを考えれば、

$dp'[j][k]=\displaystyle \sum_{k'=k}^{K-1} dp'[j-1][k']+(K-k+1)dp'[j-1][k-1]$

と遷移が定義できることがわかります。 $dp[1][j]=dp'[j+1][1]$ です。これらのDPはいずれも累積和で高速化できます。
さて、以上を使って「カラフルでない列についての $A$ に一致する連続する部分列の個数の総和」を求めていきましょう。
$A$ がdistinctな場合。数列中に長さ $M$ のdistinctな列が登場する場合の数は、終了位置を $j$ と固定すれば、 $K \sum_{k=M}^{K-1} dp'[j-1][k]dp[k][N-j]$ です。その中に、 $A$ はちょうど $\frac{(K-M)!}{K!}$ の割合で存在します。あとは $j$ を $M$ から $N$ まで動かして総和をとればよいです。
$A$ がdistinctでない場合。 $A$ のdistinctなprefixの最大長さを $l$ 、suffixの最大長さを $r$ とすると、数列中に $A$ が登場する場合の数は、開始位置を $i$ と固定すれば、 $dp[i-1][l]dp[N-M-i][r]$ になります。あとは $i$ を $1$ から $N-M$ まで動かして総和をとればよいです。
計算量は全体で $O(NK)$ になります。

実装

https://beta.atcoder.jp/contests/arc100/submissions/3195797

反省

5日かかりました。難しかった。
コンテスト中のACが少ない問題はなかなか解けなくても自己嫌悪に陥らないので良いです。（にしても5日はかかりすぎか）
$dp$ の遷移を立てるまでにかなりの苦労がありました。しかも蓋を開けてみたら非想定解でした。想定解の方が数倍賢い。

2018-09-04

AtCoder Regular Contest 102 F - Revenge of BBuBBBlesort!

自力AC最高点を更新しました！

問題

https://beta.atcoder.jp/contests/arc102/tasks/arc102_d

解法

まず、操作の性質を考えてみると、以下のようなものが浮かび上がります。

一度反転した3項の中央は、その後動かすことはできない
一度動かした項を元の位置に戻すことはできない

一つ目を示します。 $i$ 項目を中心に反転させたとします。ここから $i$ 項目を動かすには、 $i \pm 1$ 項目を中心に反転させる必要がありますが、そのままでは $i$ 項目と $i \pm 1$ 項目が反転できる大小関係を満たしません。そこで $i \pm 2$ 項目を中心に反転させることでこれを解消しても、今度は $i \pm 1$ 項目と $i \pm 2$ 項目が反転できる大小関係を満たさなくなります。
二つ目は、一つ目の派生です。一度壊した大小関係は元には戻せません。（人間関係と似ていますね）
一つ目の性質から、その後動かさなくていい項、つまり $p_i=i$ なる $i$ 項目しか反転の中心にできないことがわかります。二つ目の性質から、このような項はむしろ動かしてはなりません。このような項をピボットと呼ぶことにします。さて、ピボットは操作の過程で増えるでしょうか？たしかに条件を満たす項は増えていきますが、実際にそこを中心とした反転を行うことはできない（動かすことのできない項が必ず隣にある）ため、ピボットは増えないものとしてよいことがわかります。よって、入力は以下を満たす必要があります。

任意の $i$ について、 $i-1, i, i+1$ 項目のいずれかはピボットである

ここで、項を偶数番目と奇数番目に分けたとき、ピボットを区切りとした連続する非ピボット同士で数をやり取りするしかないため、そのような項のみ取り出します。まず、それらが集合として正しくない場合は弾きます。次にそれらを昇順に並べることを考えます。以下のような必要条件が浮かびます。

$i \lt j, p_i \gt p_j$ を満たし、非ピボットである $i, j$ 項目について、区間 $(i, j)$ と区間 $(p_j, p_i)$ は共通部分を持つ

つまり、ある2つの項を入れ替えなくてはならないとき、その間にそれらを入れ替えられるピボットが必要という事です。
実はこれは十分条件でもあります。つまり、条件を満たした状態から反転を行っても依然として条件は満たされたままになっています。例えば $\cdots , 8, 5, 10, 7, 6, \cdots$ （ $5, 7$ がピボット）のような列において、 $7$ を中心に反転を行うと $8$ と $6$ が交換できなくなるように思えますが、よく考えると $6$ より右側に $6$ より小さい項が1つはあるはずであり、元から条件を満たしていません。反転後に条件を満たさなくなるように思えるのはすべてこのパターンであることがわかります。
では、条件を満たしているかどうかを判定する方法を考えましょう。区間 $(i, j)$ と区間 $(p_j, p_i)$ が共通部分を持たないとすると、 $i \lt p_i$ か $j \gt p_j$ であるといえます。（非ピボットなので等しいことはない）
よって、非ピボットな $i$ 項目について、 $i \lt p_i$ ならばそれより右にそれより小さい非ピボットがなく、 $i \gt p_i$ ならばそれより左にそれより大きい非ピボットがないとき、条件は満たされています。これは、左からの累積 $\max$ 列と右からの累積 $\min$ 列を持っておけば、全体として $O(N)$ で判定することができます。

実装

https://beta.atcoder.jp/contests/arc102/submissions/3132626

反省

初めてARC-Fなるものを自力で通し、根気よく考察を進めていけば案外解けなくもないことがわかりました。
思考過程はほぼ解法に書いた通りですが、「項を偶奇で分けてピボットで区切った非ピボットたちが集合として正しくない場合は弾く」あたりが少しだけ違います。（といっても、予めそういうのが弾かれるような条件を考えてあったというだけです（ACコードはそっちの実装になっています））

2018-09-02

AtCoder Regular Contest 102 D - All Your Paths are Different Lengths

これは流石に解きたかった

問題

https://beta.atcoder.jp/contests/arc102/tasks/arc102_b

解法

頂点 $i$ から頂点 $i+1$ に長さ $0$ の辺と長さ $2^{i-1}$ の辺を張る

とすると、経路長 $0$ から $2^{N-1}-1$ のパスが1本ずつできます。
まずはこれでパスの最大長さを $L$ を超えない最大まで持って行きましょう。そこから、

頂点 $i$ から頂点 $N$ に長さ $現在あるパスの最大長さ+1$ の辺を張る

とすると、パスの最大長さが $2^{i-1}$ だけ更新されることがわかります。したがって、 $L-2^{N-1}$ の二進数における各桁を取り出しながら、適切に辺を張り最大長さを更新していけばよいです。

実装

https://beta.atcoder.jp/contests/arc102/submissions/3123362

反省

解法の上2行まではすぐでしたが、そこから先の考察がお粗末すぎました。
あくまで二進数を詰める方向で行けばよかったのですが、途中でこれでは無理だと勘違いして基数を変えてみたりしていました。
最初からある程度道が開けていただけに変に焦ってしまったところはあると思います。
しかしながらやっぱり

構成が苦手なのでもプレッシャーに弱いのでもなく単に頭が悪い
— ウォンバット (@wombat_packer) 2018年9月1日

2018-08-31

AtCoder Regular Contest 070 E - NarrowRectangles

考察してて生えてきた図に既視感があると思ったら、以前諦めて解説だけ見た問題だった

問題

https://beta.atcoder.jp/contests/arc070/tasks/arc070_c

解法

$dp[i][x]=i個目の左端をxとしたときのi個目までの総移動量の最小値$

というDPについて考えます。以下が成り立ちます。

$dp[i][x]=\displaystyle \min_{x-(r_{i-1}-l_{i-1}) \leq x' \leq x+(r_i-l_i)} dp[i-1][x'] + |x-l_i|$

ここまでで部分点が取れます。
実は $dp[i]$ は、傾きが段階的に変化するU字状の関数になっており、傾きが変わる点の集合をとして管理することができます。具体的には、

傾き $0$ のところから点を左右に分け、左側を降順、右側を昇順のpriority_queueとして持つ。左右それぞれで点同士の相対位置が正しくなるようにする。傾き $0$ の線の両端の点だけ正しい座標を持っておく。
漸化式の第1項を処理することを考える。傾き $0$ の線が広がることがわかるので、両端の点の座標を更新する。
漸化式の第2項を処理することを考える。ある点で傾きが $2$ 変わることがわかるので、priority_queueに同じ点を2つ追加し、左右間で点を受け渡す。座標と答えを更新する。

とすればよいです。
計算量は $O(N \log N)$ となり、満点が得られます。

実装

https://beta.atcoder.jp/contests/arc070/submissions/3107540

反省

解説だけ見たものも意外と覚えているらしく、割とすんなりACできました。
データ構造を持ってDPのオーダーを落とすというのは初めてやったように思います。こういうのもあると心の片隅に置いておきます。

2018-08-30

AtCoder Regular Contest 066 E - Addition and Subtraction Hard

過去問。
なんかやけにあっさり解けて、順位表見たら通してる人が意外と少なく、ついに僕も覚醒したか？と思ったらXor Sum回だった

問題

https://beta.atcoder.jp/contests/arc066/tasks/arc066_c

解法

正符号の後ろから括弧を開始するのは明らかに無意味です。ある負符号から何項かを括弧で括ることを考えます。（この括弧を外括弧と呼ぶことにします）

$- (11 + 45 - 14 + 19 + 19 - 8 + 10)$

ここで、外括弧内の項はなるべく最終的に正にしてやりたいです。

$- (11 + 45 - (14 + 19 + 19) - (8 + 10)) = - 11 - 45 + 14 + 19 + 19 + 8 + 10$

このように負符号を区切りとして括るようにすると、与式において正符号が続く最初の何項かを除いて全部正にできることがわかります。
この最初の何項かというのは、外括弧の開始位置を固定して意味のある括り方をしようとすると必ず巻き込まれてしまいます。（必要な犠牲）
外括弧内の後ろの方は正にできるので、終了位置は与式の一番最後にするとよさそうです。外括弧は1つでよいこともわかります。
最終的に負となってしまうのは、開始位置からの何項かと、開始位置より前にあるもとから負だった項です。
ここまでわかれば、あとは与式を前から見ていって開始位置を動かしながら、なるべく大きくなるような答えを探せばよいです。

実装

https://beta.atcoder.jp/contests/arc066/submissions/3103383

反省

正の項しかない場合の処理を忘れて1WA食らったものの、ほとんど解法に書いた道筋通りに考察を進め、スムーズに解くことができました。
コンテスト本番でもかくありたいものです。

2018-08-30

AtCoder Regular Contest 101 D - Median of Medians

解けませんでした。そろそろ本番で700点問題を通せるようになりたい。

問題

https://beta.atcoder.jp/contests/arc101/tasks/arc101_b

解法

答えを二分探索します。「 $m$ の中央値が $x$ 以上かどうか」が判定できれば、それを満たす最大の $x$ が答えとなります。
「 $m$ の中央値が $x$ 以上かどうか」というのは、「 $a$ の中の区間のうち、 $x$ 以上の要素が半数以上を占める区間が半数以上かどうか」と言い換えられます。
そのような区間の数を知るには、 $a$ 中の各要素を $x$ 以上ならば $+1$ 、 $x$ 未満ならば $-1$ と置き換え、その累積和の転倒してない数を求めてやればよいです。
全体の計算量は $O(N \log N \log \max a_i)$ となります。

実装

https://beta.atcoder.jp/contests/arc101/submissions/3093529

反省

まず「 $m$ の中央値が $x$ かどうか」を求めようとしました。
$a$ を $\pm 1$ で置き換えたやつの累積和の転倒してない数を求めればよさそうだと思いましたが、これをやるのに $O(N \log N)$ かかるので、 $x$ を各 $a_i$ について試すとなると厳しいです。
$a$ を小さい要素から順に見て、差分を計算する……など考えましたが、うまくいきませんでした。
条件を緩くして二分探索に落とすという発想が一切出なかったところに頭の弱さを感じます。数え上げの問題などにも似たようなのがあるので慣れなきゃダメですね。
コンテスト直後ナーバスになって弱音を吐く僕↓

答えを二分探索する系の問題一生慣れる気がしない
— ウォンバット (@wombat_packer) 2018年8月25日

Australia

ウォンバットのブログ