PKU1163 The Triangle

G++で最短をとれた記念。

解法

よくある問題なので簡単に書くと、ピラミッドの各点について、自分にたどりつくまでのコストの最大値を求めながらDP。短くするためには、一番最初に与えられるピラミッドの段数の処理を工夫する必要がある。たぶん、getsや場合分けで無視するより、三角形の内部の点だと思って計算して、最後に答えから段数を引いたほうが短い。

fmaxが大活躍するOzyさんのコードはこちら。http://d.hatena.ne.jp/Ozy/20070204#p1

コード

一昨年通した113BのGCCのコード。

a[99];i,r;
main(k,d){
  for(;~scanf("%d",&d);r=r>d?r:d)
    a[k=k--?k:i++]=d+=a[k]>a[k-1]?a[k]:a[k-1];printf("%d\n",r-i);
}

まだfmaxを知らなかったのにくわえて、無駄な改行を出力するとかいう寝ぼけた真似をしている。グローバル変数は(たぶん)16バイト境界に配置されてるので、a[-1]を触っても大丈夫なはず。

とりあえずfmaxを使って改行を消してみると、105B。

a[99];i,r;
main(k,d){
  for(;~scanf("%d",&d);r<d?r=d:0)
    a[k=k--?k:i++]=d+=fmax(a[k],a[k-1]);printf("%d",r-i);
}

さらに配列をa[];の形で宣言できれば103B。GCCは変数名をいじることでグローバル変数がメモリ上に配置される順番を変えられるので、なんとかして配列がグローバル変数の最後に来るように調整する。

…という調子でいけるかと思いきや、PKUの仕様変更でfmax,fminその他もろもろの超絶便利な関数たちが使えなくなってしまっている。こうなったらG++の出番。まず、上記のコードをそのまま変換した103B。この時点でGCC涙目。

#import<algo.h>
int a[99],i,r,k=1,d;
main(){
  for(;cin>>d;r>?=d)
    a[k=k--?k:i++]=d+=a[k]>?a[k-1];cout<<r-i;
}

PKUのG++ではグローバル変数のメモリ上の配置は宣言の逆順になるようなので、a[9]でもOK。さらに鬱陶しいk=1を始末しつつ、式の評価順に期待すると、98Bのコードが得られる。

#import<algo.h>
int a[9],i,r,k,d;
main(){
  for(;cin>>d;)
    r>?=a[k=~k?k:i++]=d+=a[k]>?a[--k];cout<<r-i;
}

G++だとa[-1]はiになるのかもしれない。どっちにしろ大丈夫なのは確か。