PKU2313

http://d.hatena.ne.jp/nuc/20060714#c1153070704

118Byte はこんな感じです。全然サクっとではなくて、死にものぐるいで色々やってます。なんかだいぶアルゴリズムが違う感じですね。というか nuc さんの回答見てて何やってるかわからない。一見して for(a;b;c)d; の d の部分を使ってないので 1Byte 削れそうに思います。

b,c,v;
main(a,m){
    for(gets(m);~scanf("%d",&a);b=a)
        v+=b?abs(m=b-a)-abs(b-(c=c&&m*b>m*c?m*a>m*c?a:c:b)):0;
    printf("%d",v);
}

でもとりあえず gets は削れるなーと思ったので修正して 117Byte 。まだ縮みそうな気はするんですけど、自分でも何やってるかあんまり思い出せなくて手が出ません。なんか他と比べてかなり自分的に好みの問題だったと思います。

b,c,v,m;
main(a){
    for(;~scanf("%d",&a);b=m++?a:0)
        v+=b?abs(m=b-a)-abs(b-(c=c&&m*b>m*c?m*a>m*c?a:c:b)):0;
    printf("%d",v);
}

これ、入力によってはたぶんコケると思います。最初は b, c を main の第二第三引数にして、 b>1e5 などとして、未入力であることを検知していたのですが、なんかこれで通ちゃったのでだいぶ削れてしまいました。ちなみに 120=>118 の 2Byte は改行の \n だったりします…

tekezoさんに鬼気迫る…と言っていただいたので、なんとなく説明とか書いてみます。

この問題は、 N, A(1), A(2), ..., A(N) が入力として与えられて、 B(N) を考えて、最小の V = |A(1)-B(1)|+|A(2)-B(2)|+...+|B(1)-B(2)|+|B(2)-B(3)|+... を求める問題。

普通なら A をとりあえずバッファに入れて…とか考えますが、既に nuc さんが 130Byte 代を出していたので、随時見ていく方法でなんとかいきそうだと思えます。

で、考えていくと、入力例として与えられている 3, 5, 8 だと、 A=B となる数列で最小の V が得られることがわかります。これは単純に横の要素と引き算して絶対値取るだけで大丈夫。

でも、 A = 3, 5, 4 のような入力のとき、 B = 3, 5, 4 だと V = 3 ですが、 B = 3, 4, 4 などとすると V = 2 にすることができます。というわけで、 B = A を基本として考えつつ、 3, 5, 4 や、 5, 2, 5 のように、曲線が凹凸になっている部分では、中央の値を近隣の値に補正するようにしています。

で、恒例なのですが、最初の 1 入力が N であって A(1) じゃないというのに気付かず血涙を出してから、 for 文の中身がだいたいこんな感じのコードになったのでした。

        v+=b<1e5?abs(a-b)
            -abs((c=c<1e5?
            b<a&&b<c?a<c?a:c
            :b>a&&b>c?a<c?c:a
                  :b:b)-b):0;

で、あとはまぁ、ひたすら削っただけ、なのですが、 ?a:c とか ?c:a とかを (b-a)*(b-c) の値なんかを使って一本化して、

        v+=b<1e5?abs(a-b)
            -abs(b-(c=c<1e5&&
                  (b-a)*(b-c)>0?(a-c)*(b-a)>0?a:c
                  :b)):0;

こんな感じ。あとは変数増やして m=a-b を先に代入しておくことにして、そしたら式変形が色々とできて今みたいな形になりました。あとは 1e5 が前述の通りなんかインチキぽく消えて、 \n を消して、 gets を消して、今に至ります。

削りたいのは、 c の代入文での () と、あと m のかけ算をしまくっている部分ももう少しなんか無いのかな？と思っています。アルゴリズム自体もなんかよくする方法はありげ。まぁそんなことやってる場合じゃないはずです。