ABC206参加しました。

競プロで小数点を使わないといけない場合は、大抵小数点誤差が問題になってくる場合が多いですが、今回はそのまま計算しても問題ないと思います。(int)(N * 1.08) の値でif分岐しましょう。

B - Savings

Submission #23588128 - AtCoder Beginner Contest 206（Sponsored by Panasonic）

２次方程式の解の公式でO(1)解法になります。貯金額は、k日間貯めるとして、(初項,公差ともに1の等差数列の和なので) $$
\begin{align} \sum_{n=1}^{k}{{(1+k)k}/2} &\ge N\\ \end{align} $$ とした場合に、 $$
\begin{align} \sum_{n=1}^{k}{{(1+k)k}/2} &\ge N\\ \end{align} $$ を満たす最小のkを求めれば答えになります。

式を移行すると以下の２次方程式になります

$$
\begin{align} k^{2} + k - 2N &\ge 0 \\ \end{align} $$

あとは、これを解の公式でkについて解きます。kは自然数、つまり整数かつ0より大きい値にならないといけないので、解の公式で出た正のk,負のkのうち、正の方を採用します。また、kは小数で出ますが、いくつか具体的にNを入れて計算すれば、kを切り上げて整数にすればいいことがわかります。

C - Swappable

Submission #23599647 - AtCoder Beginner Contest 206（Sponsored by Panasonic）

解説 - AtCoder Beginner Contest 206

二分探索で、$O(N log N)$で計算できます。

long ans = 0;
Array.Sort(A);
for(int i = 0; i < N; ++i)
{
    int idx = UpperBound<long>(A, A[i]);
    ans += N - idx;
}

まずAをソートします。ソートしても答えには影響は出ません(ここ、実はちょっと自信がない。ACした以上、でないはずだけれど...)

その後で、それぞれの要素に対して、upperBoundを計算します。例えば以下の数列A(ソート済み)を考えてみます。

1,1,2,3,4

この数列の答えのペアは以下のようになります。

(1,2), (1,3),(1,4)   => (A[0],A[2]), (A[0],A[3]), (A[0],A[4]) ,軸A[0]
(1,2), (1,3),(1,4)   => (A[1],A[2]), (A[1],A[3]), (A[1],A[4]), 軸A[1]
(2,3), (2,4)         => (A[2],A[3]), (A[2],A[4]), 軸A[2]
(3,4)                => (A[3],A[4]), 軸A[3]

見ると、それぞれの行で「軸となる要素の右側に並ぶ数」の要素数だけペアができます。軸要素の右側(で同じ数字にならないもの)はすべてペアとなるというのが肝です。

この数列に対して、まず、A[0]=1でupperBoundを計算するとidx=2(つまりA[2]=2)が返ってきます。upperBoundは、コード中にも書いたとおりA[i] > vとなる最小のiの位置を返してくれます。言語によってはライブラリに入っています。二分探索がベースなので、計算量も低いです。ここで同じ数(今回なら1)同士のペアには意味がないため、upperBoundをつかうことでそれらを飛ばして、ペアとなる数を導くことができます。

あとはN-idxをすることで「軸となる数(最上段ならA[0]=1)の右側に並ぶ数」の要素数を求めることができます。

D - KAIBUNsyo

Submission #23642441 - AtCoder Beginner Contest 206（Sponsored by Panasonic）

解説 - AtCoder Beginner Contest 206

よく見るとunion-findで簡単に解ける問題でした。公式解説動画が詳しいのですが、せっかくなので、書いてみます。

まず例として、入力例にもある

A[0] = 1, A[1] = 2, A[2] = 3, A[3] = 4, A[4] = 1, A[5] = 2, A[6] = 3

を考えます。

まず要素数分だけノードを記述します。

[1], [2], [3], [4]

これらのノードで、「回分にしたとき、同じ数になってほしい要素」をつなぎます。

([1], [3], [4]), ([2])

( )の中身がノードがつながっている連結ノードになると思ってください。ここでは、A[0]=A[6], A[1]=A[5], A[2]=A[4]がつながる必要があります。

これらの連結ノードの中身を同じ数字に置き換えるための最小回数は、連結ノード内部のノード数-1回です。よって、全ての「連結ノード」(上の例だと([1], [3], [4])と([2]))について、ノード数-1回加算すれば答えが出ます。

これらノードを扱うにはunion-find(DSUとも)が便利です。何か知らない人は

qiita.com

このへんがわかりやすいかも。ノードをまとめるにはunion操作, ノード数はsize操作です。

1点だけコードの解説をしておくと、

if(dsu.root(i)==i){ 
  //ansに加算
}

ここは、連結ノード内のノード数-1を足し込む計算を1度しかしなくていいようにifで弾いています。つまり

([1], [3], [4]), ([2])

の場合に連結ノード([1], [3], [4])のノード数-1を足し込む計算は、コード中のfor分通りなら3回行ってしまうため、これを一回のみに制限しています。[1],[3],[4]のうち、どれがroot要素になるかはunion-findの実装次第ですが、逆に言えばどれか一つはroot要素(dsu.root(i) ==iを満たす)はずです。

まとめ

予め用意してあったライブラリがだいぶ使えました。が、Dをグラフと見抜けなかったので難しいです。

umem0chiの日記

AtCoder ABC206

A - Maxi-Buying

B - Savings

C - Swappable

D - KAIBUNsyo

まとめ