yukicoder No.509 塗りつぶしツール

また、白でも黒でもない3つ目の色を赤と呼ぶことにする。
領域を「背景」「文字」「穴」の3つの領域に呼び分ける。
背景を塗りつぶすのは1回、文字をすべて塗りつぶすには文字数回、穴をすべて塗りつぶすには穴の個数回の操作が必要。

・背景を1回だけ塗りつぶす場合
背景の色は「白→黒」と変更されるので、そのとき文字の色は赤になっていなければならない。
すなわち各文字の色は2回以上変更されるので、全体では最低でも2*(文字数)+(穴数+1)回の操作が必要。
実際に「文字をすべて赤にする→背景と穴をすべて黒にする→文字をすべて白にする」という手順で最小回数を達成できる
・文字を1回だけ塗りつぶす場合
文字の色は「黒→白」と変更されるので、そのとき背景及び穴の色は赤になっていなければならない。
すなわち背景及び穴の色は2回以上変更されるので、全体では最低でも2*(穴数+1)+文字数回の操作が必要。
実際に「背景と穴をすべて赤にする→文字をすべて白にする→背景と穴をすべて黒にする」という手順で最小回数を達成できる
・背景,文字をどちらも2回以上塗りつぶす場合
最低でも2*(文字数)+(穴数)+2回の変更が必要なのでこれは1番目のパターンより必ず回数が多くなる

ということで、結局min{2*(文字数)+(穴数+1),2*(穴数+1)+文字数}が答えになることがわかる。

#define min(p,q)(p<q?p:q)
a[]={1,0,0,0,1,0,1,0,2,1};
s,h,x;
main(){
	while(1){
		x=getchar();
		if(x=='\n')break;
		s++;
		h+=a[x-'0'];
	}
	printf("%d",min(2*(h+1)+s,2*s+h+1));
}

縮める際の肝は上のコードで配列に保存していた部分をどうするか。
方針としては2通りあって、「いい感じの式をつくる」「bitでやる」
文字の入力の受取も、getchar()-10、~getchar()、read()、などいろいろ考えられるのでいい感じになるものを探す

s,x;main(h){for(;x=getchar()-10;s++)h+=3&397569>>x*2-12;printf("%d",s+h+(s<h?s:h));}
s,x;main(h){for(;x=getchar()-10;s++)h+=x/46-~x%2-!(x%8);printf("%d",s+h+(s<h?s:h));}
h,x;main(s){for(;x=~getchar();s--)h+=3&1446145>>~x*2;printf("%d",h-s+(-s<h?-s:h));}
h,x;main(s){for(;x=~getchar();s--)h-=x/57+x%2+!(x%17);printf("%d",h-s+(-s<h?-s:h));}
h,x;main(s){for(;read(0,&x,1);s--)h+=3&1446145>>x*2;printf("%d",h-s+(-s<h?-s:h));}
h,x;main(s){for(;read(0,&x,1);s--)h+=x/56-~x%2-!(x%25);printf("%d",h-s+(-s<h?-s:h));}
s,x;main(h){for(;read(0,&x,1);s++)h+=x/56-~x%2-!(x%10);printf("%d",h+--s+(s<h?s:h));}

int型に対するbitshiftはmod32で計算される仕様と'0'*2 mod 32が0であることがうまく噛み合って、bitの方が短くなった。
82B

メモ

yukicoderでゆるふわgolf

yukicoder No.509 塗りつぶしツール