Contents
鶴亀算
Before:
1 #include <stdio.h>
2
3 int main(void)
4 {
5 int num,leg,tsuru,kame;
6 printf("鶴と亀の数の合計 ? ");
7 scanf("%d",&num);
8 printf("鶴と亀の足の本数の合計 ? ");
9 scanf("%d",&leg);
10 kame = (leg - 2 * num) / 2;
11 tsuru = num - kame;
12 printf("鶴と亀の数の合計 %d\n",num);
13 printf("鶴と亀の足の本数の合計 %d\n",leg);
14 printf("鶴 %d 羽, 亀 %d 匹\n",tsuru,kame);
15
16 return 0;
17 }
After:
(187B)
- ポインタの関係で32bitでないと動かない。intが16bitの環境でも動かない。
- EUC-JPでないとポインタの演算が合わないのでy+6を書き換える必要アリ。
Revised (ytoku):
(185B)
- 最後のprintfを分割して"%s%s "部分の省略を図ったのと、Sにy)を取り込んだので、それぞれ1B稼げました。
PKU 1006
http://poj.org/problem?id=1006
Before:
1 #include <stdio.h>
2
3 #define C_PHY 23
4 #define C_EMO 28
5 #define C_INT 33
6
7 int findpeak(int a, int ca, int b, int cb)
8 {
9 a -= b;
10 while (a % cb != 0) {
11 a += ca;
12 }
13 return a+b;
14 }
15
16 int main()
17 {
18 int n;
19 for (n = 1; ; n++) {
20 int p, e, i, d;
21 scanf("%d %d %d %d", &p, &e, &i, &d);
22 if (p == -1) break;
23
24 int tmp;
25 tmp = findpeak(e, C_EMO, i, C_INT);
26 tmp = findpeak(tmp, C_EMO*C_INT, p, C_PHY);
27
28 tmp -= d;
29 if (tmp <= 0) tmp += C_EMO*C_INT*C_PHY;
30 else if (tmp > C_EMO*C_INT*C_PHY) tmp -= C_EMO*C_INT*C_PHY;
31
32 printf("Case %d: the next triple peak occurs in %d days.\n", n, tmp);
33 }
34 return 0;
35 }
- golf版にアルゴリズムを合わせてあります
After:
1 main(n,p,e,i,d){for(;scanf("%d%d%d%d",&p,&e,&i,&d),p+1;printf("Case %d: the next triple peak occurs in %d days.\n",n++,(i-d+21251)%21252+1))while((i-p)%23|(i-e)%28)i+=33;}
(171B)
- ホールインワンは157Bらしい
- Googleで検索するとそのコードが最上位に出てくるけれどもうちょっと考えたいところ
- mainの第一引数 == 1 (コマンドライン引数がなければ)
四則演算と剰余
Before:
1 #include <stdio.h>
2
3 int main(void)
4 {
5 int a, b;
6
7 printf("input two numbers\n");
8 scanf("%d%d", &a, &b);
9 printf("%d+%d=%d\n", a, b, a + b);
10 printf("%d-%d=%d\n", a, b, a - b);
11 printf("%d*%d=%d\n", a, b, a * b);
12 if (b) {
13 printf("%d/%d=%d\n", a, b, a / b);
14 printf("%d%%%d=%d\n", a, b, a % b);
15 }
16
17 return 0;
18 }
After:
(107B)
- defineは1つで十分だった。可読性もささやかに向上
- printf("%d"#x"%d=%d\n",a,b,a x b)として1Bの節約を図ったら、p(%)で%d%%d=...と展開された結果残念なことになった
Revised (renda):
(106B)
- p(x)の後のSpaceいらないよね!
- 一応hijiri(x86_64)のgccで通ることは確認。sunやnestだとどうでしょう
- そうか、気付かなかった...sunでもnestでも通りました
- 一応hijiri(x86_64)のgccで通ることは確認。sunやnestだとどうでしょう
Revised (ytoku):
(104B)
b&&が二回出てくるのが気になって一つの式に納められないか考えたらすんなり
ICPC2010 インターネット予選 A問題
Before:
あとで (1103B)
After:
1 #define K scanf("%d",
2 #define I(x)for(x=N;--x;)
3 #define L(a,b,c)I(i)I(j)if(k[i][j])b=b>a?b:a,c=a<c?a:c;b-=c-1;
4 N=404;main(c,i,j,l,e,f,g,h,n,d){int k[N][N],m[N],o[N];for(;c;){I(i)I(j)l=k[i][j]=m[j]=o[j]=0;e=g=m[0]=o[0]=(f=h=N)/2;K&c);if(k[e][e]=c){for(;--c;K&d),d/2?i=3-d,j=2-d:(i=d-1,j=d),d=m[n]+i,n=o[n]+j,k[d][n]=m[++l]=d,o[l]=n)K&n);L(i,e,f)L(j,g,h)c=printf("%d %d\n",e,g);}}}
(380B)
- 変数名を機械的に振ったところ解読不能になった。
- cは例によって1以上で初期化される
Revised (nomeaning):
1 n,x[200],y[200],a,s,d,f,k,l,q[]={1,0,-1,0};main(i){for(;scanf("%d",&n),n;a=s=d=f=!printf("%d %d\n",s-a+1,f-d+1))for(i=0;++i<n;a=fmin(a,x[i]),s=fmax(s,x[i]),d=fmin(d,y[i]),f=fmax(f,y[i]))scanf("%d%d",&l,&k),x[i]=x[l]+q[k],y[i]=y[l]+q[k^1];}
(239B)
- アルゴリズムを変えて,マクロを消した.
3文字の文字列の反転
Before:
(299B)
After:
(168B)
- main関数の中にセミコロンが1つもないCのコードである。Pの汎用性は計りしれない
- Pの効果はprintfが3つ以上現れたときに発揮される
- 引数に特定のパターンがあればもっと効果を発揮する
- Pの効果はprintfが3つ以上現れたときに発揮される
- グローバル変数は0で初期化される
- warning: this program uses gets(), which is unsafe.
Revised (ytoku):
(166B)
- 最初のstrの表示は反転処理の前に行うことができるので、getsした足でそのまま表示で1文字削減
- さらに、これによってPとS以外の文が消えたのでセミコロンをマクロの最後において1文字削減
Revised (ytoku on the dark side):
(161B)
ダークサイドに落ちた結果がこれだよ\(^o^)/
- どうみても動作未定義です。本当にありがとうございました。
Revised (ytoku):
(151B)
- 実は#define Sよりも単純にforの方が短かったという罠(155B)
- さらにポインタでコピーすることでiが消えました
- ついでにforの初期化部分に前のPを突っ込んで;を消去
Revised (nomeaning):
1 char a[9],b[];i;main(){printf("文字列を入力してください ");for(gets(a);i<3;i++)b[i]=a[2-i];printf("%s %s %s %s \n ",a,b,a,b);}
(126B)
- マクロを使わない方が短かった.
最初のbの宣言は若干コンパイラ依存.動作はnestとIdeOneとMinGWで確認.
- a[9]の9を消してもnestなら動作する.
- 後は工夫も何も無い残念なコード.
ツリーの表示
コマンドラインから整数n(n>=0を仮定してよい)を受け取り、n段のツリーを表示する。nが与えられなかったとき、およびn=0のときは何も表示しない。次に示す例はn=5のときである:
* * * * * * * * * * * * * * *
Before
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 int main(int argc, char **argv)
5 {
6 int i, j, n;
7
8 if (argc > 1) {
9 n = atoi(argv[1]);
10 for (i = 0; i < n; ++i) {
11 for (j = 0; j < n - i - 1; ++j)
12 putchar(' ');
13 for (j = 0; j < i + 1; ++j)
14 printf(j == i ? "*\n" : "* ");
15 }
16 }
17
18 return 0;
19 }
(387B)
After (clear):
1 i,n;main(int a,char**v){for(n=a>1?atoi(v[1]):0;i<n;++i){for(a=n-i-1;a--;)putchar(32);while(a++<i)printf(a==i?"*\n":"* ");}}
(124B)
- 2010/12/24-25の浜見寮におけるNabeでのゴルフ(参加者約1名)の成果物
- 上に飾りを付けたり、下に幹を付け足そうかと思ったけれど面倒なのでやめた
- 64bit環境を見捨てるのはやめておいた
Revised (renda):
1 i,n;main(int a,char**v){for(n=a>1?atoi(v[1]):0;i<n;++i){for(a=n-i-1;a--;)putchar(32);while(a++<i)printf(a-i?"* ":"*\n");}}
(123B)
- とりあえず条件分岐を最適化してみた
Revised (ytoku):
1 i,n;main(int a,char**v){for(n=a>1?atoi(v[1]):0;i++<n;){for(a=n-i;a--;)putchar(32);while(++a<i)printf(a-i+1?"* ":"*\n");}}
(122B)
++iをi<nに吸収させて1byte稼ぎました
Revised (nomeaning):
1 i;main(a,b){for(i=a=atoi(*((int*)b+a-1));i--;)for(b=0;b++<a;)printf(i<b?b-a?"* ":"*\n":" ");}
(93B)
- 変数を消したりいろいろ
2011年度センター試験 数学IIB 第6問 C移植版
Original
100 INPUT M 101 FOR N=1 TO M 110 LET I=N 120 LET C=0 130 IF I=1 THEN GOTO 210 140 IF INT(I/2)*2=I THEN 150 LET I=I/2 160 GOTO 190 170 END IF 180 LET I=3*I+1 190 LET C=C+1 200 GOTO 130 210 IF C<=10 THEN PRINT "F(";N;")=";C 211 NEXT N
- 典型的なINTを用いた割りきれるかどうかの判定
- まさかのFOR出現で戸惑った受験生も多いだろう
- 210行のPRINTの回数を数える問題は回数が平和的
- 全体的には昨年より簡単だった印象
Before
(257B)
- 完全移植したので無駄なループも残る
- 一度ループで計算したF(x)は覚えておくともっと早く出るだろう
After
1 c,i,n;main(m){scanf("%d",&m);for(;++i<=m;c=0){for(n=i;n>1;c++)n=n&1?n*3+1:n/2;if(c<11)printf("F(%d)=%d\n",i,c);}}
(115B)
n & 1は偶数の時0,奇数の時1
Revised (ytoku):
1 c,i,n;main(m){scanf("%d",&m);for(;i++<m;c=0){for(n=i;n>1;c++)n=n&1?n*3+1:n/2;if(c<11)printf("F(%d)=%d\n",i,c);}}
(114B)
- インクリメントの順序で不等号から等号を除去
Revised (nomeaning):
1 c,i;main(n,m){for(scanf("%d",&m);i++<m;c=0){for(n=i;n>1;c++)n=n&1?n*3+1:n/2;c<11&&printf("F(%d)=%d\n",i,c);}}
(109B)
- if文を消去.
- 入力にgets(m),atoi(m)を用いると1byte短くなるが,5桁以上の整数の時に落ちるので断念.
Revised (nomeaning):
1 c,i;main(n,m){for(scanf("%d",&m);i++<m;c=c<11&&!printf("F(%d)=%d\n",i,c))for(n=i;n>1;c++)n=n&1?n*3+1:n/2;}
(106B)
c=0とc<11&&printf("F(%d)=%d\n",i,c);を統合して,{}のペアを一つ除去
完全数を求める
問題
N以下の完全数を全て求め、昇順に出力せよ。
入力
N(≦10000)を含む1行で与えられる
出力
完全数を1行ごとに、降順に出力せよ。
入力例1
9999
出力例1
6 28 496 8128
Before
After (ytoku):
1 j,n,m;main(i){for(scanf("%d",&m);i++<m;i-n||printf("%d\n",i))for(n=j=0;++j<i;i%j||(n+=j));}
(91B)
Revised (ytoku):
1 j,n,m;main(i){for(scanf("%d",&m);i++<m;n||printf("%d\n",i))for(n=j=i;--j;n-=i%j?0:j);}
(86B)
- チェックを減少方向に行うようにして条件式部分で稼いだ
- ||(...)よりも?:と代入を組み合わせたほうがよい
After (nomeaning):
1 m,j=6;main(i){for(scanf("%d",&m);j<=m&&printf("%d\n",j);j=(2<<i*2)-(1<<i))i=(i&6)+2;}
(85B)
- 回答埋め込みよりは若干短い
Revised (ytoku):
1 m,j=6;main(i){for(scanf("%d",&m);j<=m;printf("%d\n",j),j=2<<i*2,j-=1<<i)i=(i&6)+2;}
(83B)
- printfの移動
- 括弧の消去
Revised (nomeaning):
1 m,j;main(i){for(scanf("%d",&m);j=2<<i*2,j-=1<<i,i;j>m||printf("%d\n",j))i=i+2&6;}
(81B)
- iの更新式の変更
- 終了条件の変更
Revised(nomeaning):
1 m,j=6;main(i){for(scanf("%d",&m);j<=m;j-=1<<i++*2)printf("%d\n",j),j=2<<i*4;}
(77B)
- j=6を活用することにより,更新式を簡略化
Revised(nomeaning):
1 i,j=7;main(m){for(scanf("%d",&m);j<=m;j=2<<++i*4)printf("%d\n",j-=1<<i*2);}
(75B)
- j=7にするとprintfの中で数字を引ける!
Shortest Palindrome
問題
10文字以下の英大文字のみからなる文字列が与えられる。文字列の後ろになんらかの文字列を足して回文にするとき、最短となる文字列を答えよ。
入出例
入力 |
出力 |
ABA |
ABA |
APB |
APBPA |
ABAB |
ABABA |
Before
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4
5 int is_palindrome(const char *s){
6 int i, j;
7 for(i = 0, j = strlen(s) - 1; i < j; i++, j--){
8 if(s[i] != s[j]){
9 return 0;
10 }
11 }
12 return 1;
13 }
14
15 int main(void) {
16 char str[15];
17 int i, len, j;
18 scanf("%10s",str);
19
20 for(len = strlen(str); len < 100; len++){
21 char s[100];
22 s[len] = '\0';
23 for(i = len - 1, j = 0; str[j]; i--, j++){
24 s[i] = str[j];
25 }
26 memcpy(s, str, strlen(str));
27 if(is_palindrome(s)){
28 puts(s);
29 return EXIT_SUCCESS;
30 }
31 }
32 return EXIT_FAILURE;
33 }
ICPC 国内予選2013 C問題
After (ytoku): (Perl)
perl -MList::Util=sum -pe'INIT{<>}s/^,// while s%\[(,?)([,\d]+)]%@s=sort{$a-$b}split/,/,$2;",".($1?sum@s[0..@s/2]:$2+1>>1)%ge'
126bytes
After (nomeaning): (Ruby)
ruby -lpe'BEGIN{gets};$_.strip!while$_.gsub!(/\[( )?([ \d]+)\]/){" #{a=$2.split.map(&:to_i);$1?a.sort[0..a.size/2].inject(:+):a[0]/2+1}"}'
138bytes
- 7/22の放課後にytoku先輩と一緒にゴルフしてました。
After (nomeaning): (Ruby)
ruby -ne'def f(*a);a[1]?a.sort[0..a.size/2].inject(:+): a[0]/2+1;end;p eval$_.gsub("[","f(").gsub("]","),")[0..-3] if$.>1
122bytes
- 正規表現無しの方が短かった。
Revised (nomeaning): (Ruby)
ruby -ne'def f(*a);a[1]?a.sort[0..a.size/2].inject(:+):-~a[0]/2;end;p eval$_.gsub(?[,"f(").gsub(?],"),")[0..-3]if$.>1
118bytes
"a" -> ?a
a+1 => -~a
After (nomeaning): (Goruby)
goruby -ne'def f(*a)a[1]?a.so[0..a.sz/2].ij(:+):-~a[0]/2;end;p v$_.gs(?[,"f(").gs(?],"),")[0..-3]if$.>1'
102bytes
After (ytoku): (Perl)
perl -MList::Util=sum -lpe'INIT{<>}sub f{@_-1?sum@_[0..@_/2]:1+pop>>1}s/\[/f(sort{\$a-\$b}/g,s/]/),/g,$_=eval'
(110B)