Bad Hair Day(2)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3250

• 最速コード

計算量を減らすには、無駄な数え上げを無くさなければなりません。まず、次のようなイメージで考えてみます。

左から降順に並んでいる場合、ウシ3からはウシ4だけ(1頭)が見えます。ウシ2からはウシ3とウシ4(2頭)が見えることになります。そして、ウシ1からはウシ2,3,4(3頭)が見えます。ウシ1から見える頭数を数えるとき、先にウシ2から見える頭数(2頭)がわかっていれば、ウシ1からウシ2が見えるとわかったときにウシ3以降を数える必要がありません。なぜなら、ウシ2からは「2頭見えることがわかっているから」です。つまり、ウシ1から見える頭数は、「ウシ2から見える頭数＋1」とすることで求められるので、すべてのウシについて調べるにしても、「一番右端から調べた方が数える手間を省ける」わけです。

もう少し複雑なパターンで単なる降順でない場合も、降順のパターンが複数あると考えれば同様に計算できるはずです。

#include<stdio.h>

#define MAX 80000

int cow[MAX], t[MAX];

main()
{
  int i, j, n;
  int sum = 0;
  
  scanf("%d", &n);
  
  for(i=0;i<n;++i)
    scanf("%d", &cow[i]);

  for(;i--;)
  {
    t[i]=i+1;

    for(; t[i]<n && cow[t[i]]<cow[i] ;)
    {
      j=t[i];
      sum+=t[j]-j;
      t[i]=t[j];
    }
    
  }
  printf("%u\n", sum);
}