Hatena::ブログ(Diary)

nu4nu@hatena

2016-09-05 Tokyo Westerns/MMA CTF 2nd 2016 write-up

ちょくちょくできないなりにCTF参加してるけど、記録を残さないと自分でも忘れてしまうので。

Web系が一つもできないのはつらい。アセンブリ読むの好きといいつつPwnも全然ダメ。このあたりができればもっと楽しいのだろうなぁ。

[Misc] [Warmup] Welcome!! (10pt)

問題文に書いてあるのを入れるだけ。

[Pwn] [Warmup] judgement (50pt)

printfの第一引数に入力が渡っている。スタック上に残っているflagのポインタを読むように"%28$s"を渡してやればよい。

[PPC] [Warmup] Make a Palindrome! (20pt / 30pt)

10! = 3628800通り全部試しても3分の時間制限に間に合う。

[Crypto] [Warmup] Twin Primes (50pt)

p*qと(p+2)*(q+2)が与えられるので、p+qが求まって、解と係数の関係でpとqがわかってしまう。あとはencrypt.pyの逆の手順をたどればよい。

[Reverse] [Warmup] Reverse Box (50pt)

とりあえず動かしてみると、実行ごとに同じ入力でも出力が変わるが、一回の実行中に同じ文字には同じ出力しか出ない雰囲気。rand(3)を使っているところが初期化の一箇所だけで、しかも下位8bitしか使われない。rand(3)をLD_PRELOADでフックして256通りの値を試すと、TWCTFが問題文に書かれた出力になるのはrand(3)が214を返すとき。あとは換字表を作って変換すればよい。

[Crypto] Super Express (100pt)

ごちゃごちゃやっているけど結局入力の線形変換になるので、先頭をTWCTFとしたときの変換式を求めてデコードする。

[Crypto] Backpacker's cipher - easy mode (200pt)

pとqがわかったときにどうdecryptするか考える。mod p上でpubkeyの各要素をqで割ると、pubkeyのi番目の値は下から見てiビット目で初めて1が立つ値になる。messageをqで割ったものについて、下から順に1が立っているかどうかをチェックし、1が立っているときにpubkeyをqで割ったものを引くようにすると、DESで暗号化したビット列が得られる。

generate_keyのaの作り方から、pubkeyの最後の要素は2^1023*q%p、その一個前の要素は2^1022*q%pまたは3*2^1022*q%p。前者の場合にpが312桁の素数になってそれっぽい。2^1023の逆数を掛ければqも求まる。

[Crypto] Vigenere Cipher (200pt)

ASCIIのplain textをBase64エンコードしているので、必ず0が来るビットがある。全文についてこの性質が成り立つことを利用すると、keyの要素は繰り返し使われるので、keyの長さや範囲を絞ることができる。

この時点でkeyの長さが12、そのうち8要素はほぼ中身が確定するので、一度元の文字列らしきものを出してみると、最後のほうにflag is TWCTF{という文字列が来そうなので、残りのkeyも確定できる。

[Reverse] [PPC] Whiteout Mathmatics (200pt)

Whitespaceのプログラムを読むと、与えられた数値の間の各数について約数の和を求め、それの最大値を出力することがわかる。要は10^12までの数で約数の和が最大になる数の、その約数の和を答えればよい。

どうせそのような概念は既にあるだろうと約数Wikipediaを眺めたら、高度過剰数という概念がありOEIS経由でテーブルにたどりつけた。あとは995886571680をfactorして約数の和を求めればよい。

[PPC] Lights Out! (100pt / 300pt)

各マスを縦に、押したときに変化するマスを横にとった行列を作って、GF(2)上でAx=bを解けばよい。normalはガウス消去で十分速い。

lunaticはできていない。O(N^3)だと死んでしまうので、疎行列であることを利用して反復法で解くのかなとか考えていた。素因数分解でblock Lanczos法を使うように。

[Misc] glance (50pt)

情弱なのでWindows上でフリーソフトGIFを分解してBMPにしたのち、BMPのフォーマットを参考にしつつ各行を順に結合して新しいBMPを吐くプログラムを書いた。もう少し楽なやり方があったかもしれない。

[Misc] ninth (100pt)

zlibでIDATの中身をinflateすると、画像データのあとにflagが書いてあった。

2015-06-02 Piet golfでハマる

npiet(1.3d時点)のGIF周りのバグや未実装機能など。全ピクセルを愚直に圧縮せず、末端(最終行など右下方面)は書かないというのがゴルフ的な手法だが、ハマリポイントだった。

まず、npietはGIFのimage部分しか見ていないため、Background Color Indexは無視される。GIFの規格を読んだ感じでは、imageが割り当たっていないpixelの色はBackground Colorで塗りつぶされるらしいので、Pietコードをterminateさせるために作るL字領域の作成に便利なのだが。

次に、エンコードされたピクセル数が一行の幅に足りない場合。GIFLIBはエラーを返すが、npietはそれを握りつぶしている(握りつぶしてくれなかったら大変だ)。このとき足りなかったピクセルはnpietが用意した状態のままで、color index 0が埋まった状態になっているようだ。mallocしただけの領域なので、理屈の上では他の値になってもおかしくないが、ヒープの末端かどこかのサラピンの領域がもらえているのかな。なので、color tableを作るときに、image末端のエンコードサボる部分の色をcolor index 0にする必要がある。

さらにこれに関連してハマるポイントとして、ある行でピクセル数が足りずエラーが返ると、GIFLIBの内部ステート(ピクセルスタック)が変な状態で止まってしまい、次の行をnpietが処理したときに、先頭に(color index 0でなく)ゴミが描かれる場合がある。ゴミの正体は、複数ピクセルを表すコードを使ったときにエラーが返った行の上の行からエラーが返った行に持ち越したピクセル(長い)。たとえば以下の絵でいうと、右上のnB nRを一語にエンコードして、かつ、xxの部分で終了するようなソースコードを書いた場合、zzの部分はyy同様color index 0の色で塗られることを期待するが、実際はxxの行に持ち越したnRで塗られてしまう。

.. .. .. .. nB
nR .. xx yy yy
zz yy yy yy yy

2012-07-30 最近のあなごる

最近公開されたものなど。

619. Alphabet texture

一回ならともかく、二回もabs()と書くのは残念だなぁと思って、他の道を探ったのが功を奏して単独トップ。abs解で26周期にするのが思いつかず、自分のabsコードが長かったのもよかった。

文字コードの増減に着目すると、最初は13減、12増を繰り返して、真ん中で13減、13増となり、あとは12減、13増となる。これは、12.52周期だと思うとぴったりはまる。

// 88B
i=639;c=90;main(d){for(;i>14;i%25-14||puts(""))d=--i/12.52,d&1?c++:c--,printf(" %c",c);}

// 87B
i=625;c=90;main(d){for(;i--;i%25||puts(""))d=(i+14)/12.52,d&1?c++:c--,printf(" %c",c);}

// 84B
i=13;c=90;main(d){for(;i-638;)d=i/12.52,printf(i++%25-12?" %c":" %c\n",c-=d%2*2-1);}

doubleのままだと扱いにくいので分数に変えて整数演算に落とす。

// 80B
i=13;c=90;main(){for(;i-638;)printf(i++%25-12?" %c":" %c\n",c-=i*25/313%2*2-1);}

// 76B
i=13;c;main(){for(;c-=i*25/313%2*2-1;)printf(++i%25-13?" %c":" %c\n",c+90);}

// AC 74B
c;main(i){for(;c-=(i+12)*25/313%2*2-1;)printf(i++%25?"%2c":"%2c\n",c+90);}

// 79B
c='\nZ ';main(i){for(;c-=(i+12)*25/313%2*512-256,c%37;)write(1,&c,i++%25?2:3);}

// 78B
c;main(i){for(;c-=(i+12)*25/313%2*2-1;)printf("%2c%.*s",c+90,!(i++%25),"\n");}

// 74B
i=326;c;main(){for(;c+=i*25/313%2*2-1;)printf(i++%25?"%2c":"%2c\n",c+90);}

// 74B
i=326;c;main(){for(;~c;c-=i*50/313&2)printf(i++%25?"%2c":"%2c\n",90-++c);}

// AC 72B
i=326;main(c){for(;c++;c-=i*50/313&2)printf(i++%25?"%2c":"%2c\n",91-c);}

// AC 71B
i=326;main(c){while(c-=i*50/313&2)printf(i++%25?"%2c":"%2c\n",91-++c);}

途中、改行を出す部分が長く見えたので、writeや精度指定を使ってみたが逆に長くなってしまった。74Bのsubmit時に、スペースの数を悟られないように%2cにする小細工をしている。whileを使っているのはalnumを多くするため。

25周期でなく26周期でこの方針が使えると、文字列部分は3B短くなる。でも、改行を出すときは文字コードをいじらないとか入れると、結局長くなるか。

622. group elements

Cで馬鹿正直に書いてもLanguage Rankingの下のほうに沈むのが目に見えていたのでスルーしていたのだけど、公開まで24時間を切ってからnnさんが突撃していたので便乗してみた。いつも後出しじゃんけんですみません。

方針としては、単純に、前の数字を覚えておいて比較する形。改行文字も覚えておけば行頭の処理もできる。空白文字を覚えないように気をつける必要がある。

入力の最後に改行がついていない。改行契機に閉じ括弧を出すためには、この前のSimilarity Expansion同様、ループの中でgetchar()すればよい。

// AC 88B
p=10;main(c){while(~c)p=printf(c>32?p-c?"] [%c"+20/p:" %c":"]\n"+c/16,c=getchar())?c:p;}

// AC 87B
p=7;main(c){while(~c)p=printf(c>32?p-c?"] [%c"+20/p:" %c":"]\n"+c/16,c=getchar())?c:p;}

// AC 85B
main(p,c){while(~c)p=printf(c>10?p-c?"] [%c"+c/24-p/24:" %c":"]\n",c=getchar())?c:p;}

// AC 84B
c;main(p){~c&&main(printf(c>10?p-c?"] [%c"+c/24-p/24:" %c":"]\n",c=getchar())?c:p);}

// AC 84B
c;main(p){~c&&main(printf(c/22?c-p?"] [%c"+c/22-p/22:"%2c":"]\n",c=getchar())?c:p);}

スペースの処理や行頭の開き括弧は、フォーマット文字列でなんとかする方針。一番下は無駄に2を使ってみたもの。submit前に一呼吸おいてこういう遊びが入れられるようになりたい。

この問題は、最後に改行がある場合でもreadを使うようになるだけでバイト数が変わらないはず。

618. Bitwise Counting

55Bまでは来たけれどushたんの53B@binary1Bが相変わらず謎。今の自分のコードからはbinaryのにおいがしないので、方針から違うのではないか疑惑。追いつくのは大変だ。

没コード。きっとこの方針ではない。

// AC another 75B
main(i,s){while(--i>-3e6)write(strspn(s,"01")/8,s,sprintf(s,"%08o\n",-i));}

// AC another 61B (rand)
main(i,p){for(;~i--;p%9?main(1,p+1):puts(p-7))*(int*)p=48-i;}

2012-07-19 最近のあなごる

没コード集。

608. GCD Again

ケース数が鬱陶しい。ケース数の無視は、scanf("%d",gets(&x))が+6Bで典型だけど、行内に複数入力あったり、vprintfと組み合わせるために"%d\n"を使うと破綻する。変数増やしてprintfに条件をつけると+7B。

GCDは普通に割り算してswapが短いのかな。結果がゼロになったり、ゼロ割になったり、ループ統合と相性が悪い。

// AC 112B
p;main(N,g,d){for(;~scanf("%d",gets(&N));p=!printf("%d\n",g))for(g=999;N--;p=g)for(scanf("%d",&d);p%g+d%g;g--);}

// AC 110B
G,x,N,d;main(g){for(;~scanf("%d",x?!N--?d=G=d&&!printf("%d\n",g),&N:&d:&x);G=d?g:0)for(g=G?:999;G%g+d%g;)g--;}

// AC 108B
p,x,N,d;main(g){for(;~scanf("%d",x?!N--?d=p=d&&!printf("%d\n",g),g=999,&N:&d:&x);p=d?g:0)for(;p%g+d%g;)g--;}

// AC 105B
p,x,N,d;main(g){for(;~scanf("%d\n",x?!N--?d=p=d&&!vprintf(),g=999,&N:&d:&x);p=d?d=g:0)for(;p%g+d%g;)g--;}

// AC 101B
p,x,N,d;main(g){while(p%g+d%g?g--:~scanf("%d\n",x?!N--?d=p=d&&!vprintf(),g=999,&N:&d:&x,p=d?d=g:0));}

// AC 94B
p,x,N,d;main(g){for(;~scanf("%d\n",x?!N--?d=p=d&&!vprintf(),&N:&d:&x);p=d)for(;g=p;d=g)p=d%g;}

// AC 93B
p,x,N,d;main(g){while(p?g=p,p=d%p,d=g:~scanf("%d\n",x?!N--?d=p=d&&!vprintf(),&N:&d:&x,p=d));}

// AC 93B
p,N,d;main(g){while(d?g=d,d=p%d,p=g:~scanf("%d",!N--?d=p=p&&!printf("%d\n",p),gets(&N):&d));}

// AC 92B
p,N,d;main(g){while(d?g=d,d=p%d,p=g:~scanf("%d",N--?&d:gets(&N,d=p=p&&!printf("%d\n",p))));}

// AC 90B
p,N,d;main(g){while(d?g=d,d=p%d,p=g:~scanf("%d",N--?&d:gets(&N,p=p&&!printf("%d\n",p))));}

// AC 89B
p,x,d;main(N,g){while(d?g=d,d=p%d,p=g:~scanf("%d",!N--?p=x++&&!printf("%d\n",p),&N:&d));}

// AC 88B
p,x,d,g;main(N){while(d?g=p%d,p=d:~scanf("%d",!N--?p=x++&&!printf("%d\n",p),&N:&g))d=g;}

609. Fixed Rows

通らないだろうと思いながら何度かぽちぽち叩いてたらrandコードが通ってしまってごめんなさい。

606. Cross Product of two Strings

printfの位置指定を使うぐらいなら、putcharを三回呼んだほうが短いらしい。最初の試行でscanfの%nやstrchr(index)を使うと短くならない気がしていたのだけど、inaniwaさんの113Bではindexをうまく使っている。

ループ統合はぬるぽの予感がして考慮してなかった。よく考えるとwhileの5B分縮まるので、多少余計な項が入っても平気なのだった。

// 134B
char a[99],b[99];main(i,m,n){for(;~scanf("%s%n%s%n",a,&m,b,&n);)for(n+=~m,i=0;i<m*n;i++)printf("%c%c%c",a[i/n],b[i%n],m*n+~i?32:10);}

// 124B
main(i,n,a,b){for(;gets(a);)for(i=n=strlen(b=1+strchr(a,32));a+i/n<b;i++)printf("%.1s%.1s%c",a+i/n-1,b+i%n,a-~i/n<b?32:10);}

// 116B
char*a,*b;main(i,B){for(;~scanf("%s%s",a=B+16,b=B);)for(;printf("%c%c",*a,*b),!*++b?a++,b=B:0,putchar(*a?32:10)%5;)}

// 116B
char*a,*b;main(_,B){for(;~scanf("%s%s",a=B+16,b=B);)for(;*a;)printf("%3$c%2$c%1$c",*(!*++b?b=B,++a:a)?32:10,*b,*a);}

// 113B
char*a,*b;main(_,B){for(;~scanf("%s%s",a=B+16,b=B);)for(;_=*a;)printf("%c%3$c%c",_,*(!*++b?b=B,++a:a)?32:10,*b);}

// AC 112B
char*a,*b;main(_,B){while(~scanf("%s%s",a=B+16,b=B))while(*a)putchar(_++%3?_%3?*a:*b:*(!*++b?b=B,++a:a)?32:10);}

// AC 110B
char*a,*b;main(_,B){while(~scanf("%s%s",a=B+16,b=B))while(*a)putchar(_++%3?_%3?*a:*b:*++b||(b=B,*++a)?32:10);}

// AC 108B
char*a,*b;main(_,B){while(a&&*a?putchar(_++%3?_%3?*a:*b:*++b||(b=B,*++a)?32:10):~scanf("%s%s",a=B+16,b=B));}

610. Similarity Expansion

複数行入力で、最後の行だけ改行がついてないとかやめてほしい。

// uso 86B
b;main(c){char*p=&b;while(read(0,&c,1))c>10?!*p++|c>34?p[-1]=c,*p*=c<36:0:puts(p=&b);}

// WA 83B
main(c,b){char*p=b;while(read(0,&c,1))c>10?!*p|c>34?*p++=c,*p*=c<36:p++:puts(p=b);}

// AC 84B
main(c,b){char*p=b;for(;~c;c>10?!*p|c>34?*p++=c,*p*=c<36:p++:puts(p=b))c=getchar();}

15. Card Sharp

すごく縮んだ。五年前と今とで考え方が違うのかなぁ。バイナリ(たぶん\0)は使ってるようだし、テクニックとしては同じだと思うのだけど。

あなごるは-Oでコンパイルされることを初めて知った。ずっと-O0でテストしていて、-O1以上で通らないコードになっててハマった。

// WA
main(a,b){gets(&a);bを使ったコード...}

// AC
a,b;main(){gets(&a);bを使ったコード...} (グローバル変数の並び順は適当に)

618. Bitwise Counting

ushたんのバイナリ2Bが謎すぎる。大きい定数あったかなぁ。ASCIIで追いついたけど、もしかすると二人のコードを合わせたらもっと短くなるのかもしれない。

2012-06-25 最近のあなごる

約四年ぶりに書いてみる。あなごる321. add_sub_brainfuck_code以来二年ぶり。

590. Time Arithmetic

時間の足し算をする問題。64bitに8文字まとめてとって演算してからごにょごにょすることを考えたが、6進や10進ではビット演算が使えない上に、24進の処理に困ることが容易にわかったので諦めて、time_t的な何かにして足し算する方針に。この時点でこのあたりはライブラリ関数に任せたほうが短いと思い込んで、出力はstrftimeかなぁと思いつつctimeのmanを眺める。

strptime->mktime->足し算->gmtime->strftimeでchar[8]->int[9]->time_t->int[9]->char[8]と変化するコード。Cだとstruct tm(=int[9])とtime_tがあって面倒。

k[9];p;
t(){mktime(k,p=strptime(p,"%T+",k));}
main(b,c){
  for(k[5]=40;gets(p=&c);){
    b=t()+t()-21600;
    strftime(k,9,"%T",gmtime(&b));printf("%s=%s\n",&c,k);
  }
}

特筆すべきポイントは、k[5]=40でstruct tmのtm_yearに値を入れているところ。これがないとmktimeが発狂して-1を返す。あと、UTC+9環境なので、時刻をずらすための補正が必要で、変な項が増えている。cでなく&cになっているのは、ライブラリ関数環境変数を読む関係だったはず。

time_tからダイレクトにchar*にできるctimeを使えないか考えると、printfのフォーマットを使ってできることがわかる。これで締め切り前の122Bにだいぶ近いのだけど、ここから環境依存で詰める。不毛で楽しい作業。

p;
t(k){mktime(k,p=strptime(p,"%T+",k=&p-39));}
main(c){for(;gets(p=&c);printf("%s=%.8s\n",&c,ctime(&p)+11))p=t()+t()+9104;}

struct tmの初期化を嫌って、あらかじめtm_yearっぽい値が書かれているところを使う。手元の環境では39でなく38だった。補正項の9104は、time_tの和がオーバーフローする関係。3600の倍数でない意外性があってテンションが上がる。

と、ここまでがんばって、フタを開けてみると、この問題の最短を競い合ってきたkouさんのコードの入力処理の短さにびっくり。struct tm経由はやはり長かった。ループの終了条件など甘いところを詰めて、出力部分だけ自分のコードを使って115Bにたどりついた。

うーん、ライブラリ関数が短いと思い込んだ以前に、最初に二つに分けて処理しようとした時点でまずかったらしい。

593. fill dots

55B解に至ったところで出力文字を決めるロジックに無駄が見えなくなってしまって、これ以上無理に思えていたけれど、まだ制御部が短くなって53B。よく見たら典型的なパタンだった。

600. Regular polygon

%.fで出すだけかと思ったら-0に苦労する問題。負の値ならマイナスを出してもしょうがない。PI/2と3PI/2で両方正の値を出すためには、PIの値を変えてもだめで、答えを少しずらしてやらないといけない。マクロ関数の括弧のあとのスペースが要らないのは知っていたけれど、名前の直後に単項演算子が来てもいいのは初めて知った。

nn(kou)さんの84Bが美しすぎる。たしかに、これでうまくいくなぁ。

602. the same ArrayA as ArrayB

入力が弱い。埋め込みに見えるが敢えてxor+αか、とも思ったけれども、歴戦のあなごる戦士にチート的発想で勝てる気がしなかったのでパス。

598. ICUP

アツい。ここまで短くなるとは思っていなかった。

最初の観察で、番号順に見たときに左の人からの距離は広義単調減少するものの1/2にしていくだけではだめなことがわかったので、最大値から距離を減らしていくことにした。最初は、出力用の数値と次に数値が入っている要素までの距離のペアを持つ形式で230B。

a[99];b[99];
main(i,k,N,d){
  for(;~scanf("%d",&N);){
    printf("%d:",N);
    for(k=a[*b=d=N-1]=N>2?2:0,*a=1;d>1;d--){
      for(i=0;i<N;i++){
        b[i]>=d*2?b[i+d]=b[i]-d,b[i]=d,a[i+d]=++k:0;
      }
    }
    for(i=0;i<N;i++){
      a[i]=b[i]=!printf(a[i]?" %d":" _",a[i]);
    }
    puts("");
  }
}

全体的に無駄が多いけれども、あなごるトレンドとしては、とりあえずvprintf使うべきというところだろうか。

ロジックで何が悪いのか考えると、右端の2のための処理と、空白距離テーブルの更新に手間がかかっている。forが一つ増えるが、数値の配列をなめたほうがマシ。

a[99];
main(N,d,p,x,k,i){
  for(;*a=x=~scanf("%d",&N);){
    for(d=N;--d;){
      for(p=1;++p<N;){
        for(k=i=N;i--;){
          k*=abs(p-i)>d|!a[i];
        }
        k?a[p]=--x:0;
      }
    }
    printf("%d:",N);
    for(i=0;i<N;i++){
      a[i]=!printf(a[i]?" %d":" _",~a[i]);
    }
    puts("");
  }
}

配列の中身が負論理(?)になっている。absがカッコ悪いが198B。200Bを切って喜んでsubmitしたら、直前にushたんが195Bでトップならず。

その後の展開は以下のとおり。

// AC 196B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts("")){for(*a=~N,d=N;--d;)for(p=1;++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>d|!a[i];for(;d<N;)a[d++]=!printf(d?a[d]?" %d":" _":"%d: 1",~a[d]);}}

// AC 193B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;++d<N;)d>=0?a[d]=!printf(d?a[d]?" %d":" _":"%d: 1",~a[d]):({for(p=1;++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>-d|!a[i];});}

// AC 192B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(p=1;++p<N;d*k<0?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>-d|!a[i];}

// AC 191B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;++p<N;d*k<0?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>-d|!a[i];}

// AC 190B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<0&++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=(p-i)/~-d||!a[i];}

// AC 189B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=(p-i)/d||!a[i];}

printfをひとつにまとめて、生成と出力を一つのforで処理するようにして、absのところを除算にして、(ここでpost mortem)

// AC 184B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;k?a[p]=--x:0)for(k=i=d;++i+d;)k*=!a[p+i];}

// AC 177B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;i/d?a[p]=--x:0)for(i=-d;!a[p+--i];);}

// AC 176B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;i/d?a[p]=--x:0)for(i=d;!a[p-++i];);}

// AC 175B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;)for(;d<0?++p<N:!printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]);i>-d?a[p]=--x:0)for(i=d-1;!a[p-++i];);}

// AC 174B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;)for(;d<0?++p<N:!printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]);i>1-d?a[p]=--x:0)for(i=d;!a[p-i++];);}

// AC 173B
a[];main(x,N,d,p,i){for(;~scanf("%d",&N);x=puts(""))for(*a=d=N;p=--d>-N;)for(;d>0?++p<N:!printf(d?i?a[-d]=0," %d":" _":"%d: 1",i=a[-d]);i<~d?a[p]=++x:0)for(i=d;!a[p+i--];);}

// AC 174B
*b,a[];main(x,N,d,p,i){for(;~scanf("%d",&N);x=puts(""))for(*a=d=N;p=--d>-N;)for(b=a-d;d>0?++p<N:!printf(d?*b?*b=0," %d":" _":"%d: 1",*b);i<~d?a[p]=++x:0)for(i=d;!a[p+i--];);}

// AC 167B
*p,a[];main(x,N,d,i){for(;~scanf("%d",&N);x=puts(""))for(*a=d=N;--d+N;)for(p=a-d;d>0?++p<a+N:!printf(d?*p?*p=0," %d":" _":"%d: 1",*p);i<~d?*p=++x:0)for(i=d;!p[i--];);}

// AC 166B
*p,a[];main(x,N,d,i){for(;gets(a);x=puts(""))for(*a=d=N=atoi();--d+N;)for(p=a-d;d>0?++p<a+N:!printf(d?*p?*p=0," %d":" _":"%d: 1",*p);i<~d?*p=++x:0)for(i=d;!p[i--];);}

absだったところを番兵つきのループに変えて(a[0]で必ず引っかかる)、生成対象の配列要素と出力対象の配列要素を同じポインタで指せるようにして、166Bに。

出力フォーマットのせいとかでなく長めのコードになる問題は、やれることがいろいろあって、短縮のしがいがあって、楽しい。

(追記)puts(a)にできるパターンに気づいていなかった。

// AC 163B
*p,a[];main(x,N,d,i){for(;gets(a);x=puts(a))for(*a=d=N=atoi();--d+N;)for(p=a-d;d<1?*p=!printf(d?*p?" %d":" _":"%d: 1",*p):++p<a+N;i<~d?*p=++x:0)for(i=d;!p[i--];);}

599. tritri fixed description

どこまで書いていいものか。子の文字を決める部分はエンコードも何もせずにいたって普通が短いような感触。制御部はmain再帰が有利なのかな。手元で動くのは114Bまでで、112Bは若干運ゲー入っているので微妙。同じ114Bでも、nnさんはスペースが入っているので、環境非依存のロジックでまだ縮む余地があるのかもしれない…。

(追記)ロジック変更で、運ゲー要素を排除して111B。

588. Palindromic formula

一文字ごとに分けた出力のコストや、12,13,14,23,34の生成コストが大きくて迷走していた。結局普通にやるのが短いのかな。