競プロっておいしいの？(仮)

ABC 057-D Maximum Average Sets

ABC AtCoder 競技プログラミング 組み合わせ

はいはい。クソ雑魚クソ雑魚

先に結論

閉区間と開区間を間違えて気づかないの

ゴミ of the 埖*1

閑話休題

Nafmoです。駄目です。

もう私eiyaプロいなかったらどうなってんだよ(

ABC 057-D問題 と戦ってきました

はーい解説しまーす

ABC 057-D Maximum Average Sets

問題概要。

  1. 数列がもらえる。A~Bの間の個数分だけ取って平均を最大化します。
  2. 平均の最大値と、そいつを作る場合の数を二行に渡って出力しよう

終わり。

 

解説的な何か

平均の最大化はA個とって割ればいいよね

具体例を考えれば自明ですよー数学的な説明は勘弁して。

(A=2{4,3,2,1}4 3と取ったら終わりよね。それ以上取ったら小さくなります。

また、{4,4,4,4}のときはA~Bの間の何個とってももう同じよね...)

前半終わり。

場合の数が問題。

 

  1. あ、ソートしてください。(前提)
  2. コンビネーション列挙*2
    パスカルの三角形をゴリ押ししましょう。

     ここに色々書いてあるよ()

  3. 数列の[0]~[A-1]が等しいときは、[0]==[A-1]が成り立つ。
    このときはA個、A+1.....Bまで取る可能性があるので
    数列にある[0]の値の数Cn個{N|A,A+1,...B}
    をループで回して足しておしまい。
  4. それ以外のときは、必ず2種類以上A個の中にひそんでいるので、
    全体にある[A-1]の値の個数C[0]~[A-1]までにある[A-1]の個数。です
  5. この個数はどうやって求めるかというとすべての要素でループを回してカウントしてください。

Submission #1201109 - 私のソース。

  • 変数の役割。
  • yui：場合の数
  • count：全体に[A-1]の値が何個あるか
  • lo：[0]~[A-1]までに[A-1]が何個あるか
  • 他にもわからなかったらコメント等で聞いてくれれば...

以上。になるのかな。

*1:これゴミって読みますよ

*2:数学の組み合わせの求め方は、ごめんなさい説明しきれません。わからなければ調べてください。