最短コード59B

POJ3671 Dining Cows(2)

前回(http://d.hatena.ne.jp/Ozy/20080730#p1)のコードを、まず大雑把に短縮しておきます。

a,b,c,m;

main()
{
  gets(&b);
  for(;~scanf("%d",&b);)
  {
    c+=b%2; /* 1の数を数える */
    b%2?--a:++a; /* 分割点を求める */
    m=a<m?a:m;
  }
  printf("%d\n",c+m);
}

入力値の数は必要ないので基本通りgets関数で読み飛ばします。1の数を数えるのと、分割点を求める操作を一つのループ内でまとめてやっておきます。この程度の短縮方法で仕上げていくと、90B程度になりますが小手先の技だけでは到底トップには及びません。計算方法自体をもう少し工夫してみます。最小値を更新する部分

    m=a<m?a:m;

は、aの値がループ内に1増加するか減少するだけなので、最小値の更新も1ずつなされることになります。つまり、条件演算子を用いなくても

    m-=a<m;

とするだけで良いことに気が付きます。それから、入力値は最初の1行を除けば1か2しかないことが分かっているので、scanf関数を使わずにgets関数で読み込んで、文字コードのまま処理すれば良さそうです。但し、最初の1行を読むときとそれ以降を読むときは同じ変数を使うことが出来ません。1行目は2文字以上の文字列の可能性があるので、ごみが混ざってしまうからです。この部分の解決方法はあとで考えるとして、とりあえずコードを仕上げます。

a,b,c,m;

main(n)
{
  for(gets(&n);gets(&b);m-=a<m)
    b%2?++c,--a:++a;
  printf("%d\n",c+m);
}

これで80B程度。ここから頑張れば、当初のTopといい勝負になるでしょう。しかし70Bを切るためには、アルゴリズムをさらに洗練していかなければなりません。ここで変数aとcに注目します。1の数を数えているだけですが、こいつを何とかして消せないものでしょうか。cがインクリメントされるとき、必ずaはデクリメントされるわけで、

  for(gets(&n);gets(&b);m-=a-c<m)
    b%2?++c:++a;

としても問題ないはずです。しかし、これではほんの2B短縮しただけであって、根本的な改善にはなりません。aとcをインクリメントする部分と、mの値を更新する部分を一体化しなくては最短コードにはたどり着けません。

ここで、「最小値だからmを減らしていかなければならない」という観念を捨てます。aは、2が出現した場合1に反転するためのコストを保持しています。1が出現した場合は、2を1に反転するコストaと比較して、aを超えていなければ、コストに余裕があると判断し、mの値を1つ増やします。平たく言えば「ここいらの2を1にひっくり返してるより、ここの1を2にひっくり返した方がマシかなー」と考えるということです。

最小値を求めるのにmを増加させるのは違和感があるかもしれませんが、「どこを境界にすればお得か」という基本姿勢は変わりません。

a,b,c,m;

main(n)
{
  for(gets(&n);gets(&b);)
    b%2?m+=a>m:++a;
  printf("%d\n",m);
}

これで一気に70B前半まで短縮することができました。あとはgets関数の問題を解決しておきましょう。gets関数を一つにする場合の具体的な問題点は2つ。

(1)変数bを汚してしまう
(2)aの値をインクリメントしてしまうと困る

(1)はどうしようもないので、ループごとにbに小さな値を代入しておくことにします。(2)の解決方法は、要するにbが'2'(=50)であるときだけaの値を更新すれば良いので、

    b%2?m+=a>m:++a;

を

    50-b?m+=a>m:++a;

に変えておきます。

これらを併せて以下のようなコードを書けば、夢の61Bコードが完成です。

a,m;
main(b)
{
  for(;gets(&b);)
    b=50-b?m+=a>m:++a;
  printf("%d",m);
}

実のところ、私はこのコードを、59Bコードが完成した後で見つけました。bの初期化についてと、bをmain関数の第1引数にすることから、直ぐに「あ、これはmain再帰だな」と思ってしまったからです。いわゆる職業病です。つまり、上記のコードは

a,m;
main(b)
{
  gets(&b)?main(50-b?m+=a>m:++a):printf("%d",m);
}

と書くことができます。これで59Bの完成です。50-bの部分は、テストケースの穴を見つけてどうにかしようと思いましたが、ちょっと無理そうです。