最近のあなごる問題

Spiral Fixed

なかなか難しい問題だった。どうアプローチするのが最善なのかわからない。私は以下の方法で解いた。他の人の解は結局調べていない。

05 15 25 35 45 55
04 14 24 34 44 54
03 13 23 33 43 53
02 12 22 32 42 52
01 11 21 31 41 51
00 10 20 30 40 50

この 6 x 6 を Spiral に展開し、上位の桁、下位の桁を上下に並べ、適当なところで区切ると、

上位: 01234555555 432100000 1234444 32111 233 2
下位: 55555543210 000001234 4444321 11123 332 2

となり、わりときれいな対象的な構造が出てくる。徐々に振り幅が小さくなる減衰振動みないなイメージだ。これを C にすると、

x,l,i;main(n,y,u,j){
    scanf("%d",&n);
    for(y=u=n-1;n--;x=i++%2?++l:--u)
        for(j=n-~n;j--;i%2?x<=l?y+=y<u:x--:x>=u?y-=y>l:x++)
            printf("%d%d ",x,y);
}

で 139B 。upper bound と lower bound を徐々に縮めていく方法だが、変数が 7 つにもなる。最短な感じがしないな。
なお、この問題は途中で FIX が出て、解の出力量が大幅に増された。このため、Groovy の解は、タイムアウトするようになってしまい、幻の解答になってしまった。

Circle radius

この問題の解法は、ピタゴラスの定理を用いて、

a*a+(r-b)*(r-b)=r*r
r=(a*a/b+b)/2

となる。この部分が、整数に丸めると C / JavaScript ともに、

a*a/b-~b>>1

と書ける。もう少しわかりやすく書くと、

(a*a/b+b+1)/2       // ただし、除算は整数除算(切り捨て)

整数に丸めるという前提のもと、これって正しいのかなぁ？つまり、以下が常に成り立つのか？

[(a*a/b+b)/2+0.5] == [([a*a/b]+b+1)/2]
     / : 有理数除算
     []: 切り捨て整数化

左辺は有理数計算で最後に四捨五入。右辺は、整数計算。
左辺は、

[(a*a/b+b)/2+0.5]
      = [([a*a/b]+a*a%b/b+b)/2+0.5]
      = [([a*a/b]+b+1)/2+a*a%b/b/2]
                                                 0<=a*a%b<b なので、
                                                 0<=a*a%b/b/2<0.5
      = [([a*a/b]+b+1)/2+X]                      0<=X<0.5
      = [[([a*a/b]+b+1)/2]+([a*a/b]+b+1)%2/2+X]
                                                 ([a*a/b]+b+1)%2/2=0 or 0.5
      = [[([a*a/b]+b+1)/2]+Y]                    0<=Y<1
      = [[([a*a/b]+b+1)/2]]
      = [([a*a/b]+b+1)/2]

と変形でき右辺に一致した。正しいということだ。

camelCase

camelCase と toggleCASE の私の C の解：

main(p,c){read(0,&c,1)&&main(c^putchar(c^c/2&p&32)/2);} //camelCase
main(p,c){read(0,&c,1)&&main(putchar(c^c/2&p&32)^c/2);} //toggleCASE

この双対性が美しかったが、最短ではなかった。