Codeforces Round #674 - yamake's blog

Codeforces Round674に参加しました（ratedだと思ってたらunratedだった......）、結果は1:19で全完しました（プレテストあるのかな？知らない）！！

Petyaくんの住んでいる部屋番号が与えられるので、何回に住んでいるかを答えなさい。

$n \leq 2$ なら1階、

それいがいは $n-2$ を $x$ で切り上げ除算して、1を足した数が答えです。

$m$ が偶数かつ、 $2 \times 2$ 行列の中に対照行列があればYESです。

1つの対照行列を規則正しく並べると、対称行列になります。

合計で $x$ 回、後ろに $1$ 加える操作を $k$ 回行った時

1. $a_1$ に $1$ をk回加える。

2. $a_1$ を $x-k$ 回コピーする。

のように操作を行うと数列の総和 $sum$ は最大となります。

このとき、

$sum=(1+k)(x-k) \geq n$

が成り立ちます。この式を変形すると

$x \geq \frac{n}{1+k}+k$

となります。

この式を見ると、 $k$ を定めると $x$ の最小値が定まることがわかります。

ま $x$ を $k$ で微分すると

$\frac{dx}{dk}=1-\frac{n}{(1+k)^2}$

となり、 $x$ は $k$ について下に凸だとわかります。

あとは下に凸な関数の最小値を求めたいので3分探索をします。

僕は三分探索の実装が面倒だったので微分係数を二分探索しました（微分係数は単調増加かつ、最小値では0を取るので二分探索で0を探索してもいけます）。

$総和が0となる連続部分列が存在する \leftrightarrow sum[i]=sum[j]となるi,j \ (i \neq j)が存在する$

より、累積和が被った時は総和が0となる連続部分列が存在するということになります。

したがって、この問題は「一番左からの累積和が全て異なるように適当な値を挿入する回数を最小化せよ」と言い換えられます。

数列内に適当に大きい値を挿入すると、その値を挿入したあとの累積和は挿入する前の累積和よりも必ず大きくできます。

したがって、

1. 左から順番に見ていき、累積和を逐一取っていって、setなどにいれて管理する。

2. 累積和が被ったとき、今見ている要素の前に適当に大きい値を挿入する。

によってこの問題を解くことができます。

最小値を求めるの難しいんですが、最小費用流を流して解決しました。

この問題の適当な提出からACコードをコピー、A, B, Cを小文字に直して提出！ｗ