競プロがんばりたい

ABC206

結果

A $\ 02:21$

B $\ 03:57$

C $\ 28:03$

ノーペナ $3$ 完で，パフォは $661$ ，rating変動は $-8$ で $746 \to 738$ でした．

考察

A問題

通常の整数型の変数で $N \times 1.08$ を計算して場合分けをします．

B問題

$i=1$ を初期値とし，変数sumに $1, 2, 3, ....$ と足し込んでいきます．

それが $N$ を超えたら $i$ を出力すればOKです．

C問題

全体から， $A[ i ] = A[ j ]$ となるような $i, j$ の組の数を引きます．

それぞれの数字が何回出てくるかを数えておいて， $1$ からその数値 $-1$ までの和を数えていく，というのを足していったものを全体から引けばよいです．

例えば入力例3では， $1$ は $4$ 回出てきます．ということは， $1$ だけで見ると $A[ i ] = A[ j ]$ となるのは $3 + 2 + 1$ 通りあります．

一般的には，ある数値が $n$ 回出てくるならば， $A[ i ] = A[ j ]$ となる $(i, j)$ の数は， $\frac{(n-1)n}{2}$ 通りです．

これを他の数値でも見ていけばOKです．

ちなみに， $(i, j)$ の選び方の総数は $\frac{n(n+1)}{2}$ ではなくて， $\frac{(nｰ1)n}{2}$ であることに注意しないとだめです．

感想

C問題で沼りました．

同じ数字が $n$ 回出てくるなら， $A[ i ] = A[ j ]$ になるのは $n$ 通りやろ！とかやってたので無限に時間が溶けました．

激冷えではないのでヨシ！(前回の上昇分が消えた)