67と68のリビジョン間の差分

そんなdefineで大丈夫か？一番短いコードを頼む

鶴亀算
PKU 1006
1. Before:
2. After:
四則演算と剰余
ICPC2010 インターネット予選 A問題
3文字の文字列の反転
ツリーの表示
2011年度センター試験　数学IIB 第6問 C移植版
完全数を求める
Shortest Palindrome

鶴亀算

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:

   1 #define P;printf("%s%s "
   2 #define S;scanf("%d",
   3 s="鶴と亀の",y="足の本数の合計";main(n,l){P"? ",s,y+6)S&n)P"? ",s,y)S&l)P"%d\n%s%s %d\n鶴 %d 羽, 亀 %d 匹\n",s,y+6,n,s,y,l,n*2-l/2,l/2-n);}

(187B)

ポインタの関係で32bitでないと動かない。intが16bitの環境でも動かない。
EUC-JPでないとポインタの演算が合わないのでy+6を書き換える必要アリ。

Revised (ytoku):

   1 #define P;printf("%s%s "
   2 #define S y);scanf("%d",
   3 s="鶴と亀の",y="足の本数の合計";main(n,l){P"? ",s,6+S&n)P"? ",s,S&l)P"%d\n",s,y+6,n)P"%d\n鶴 %d 羽, 亀 %d 匹\n",s,y,l,n*2-l/2,l/2-n);}

(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:

   1 #define p(x) printf("%d%s%d=%d\n",a,#x,b,a x b);
   2 a;main(b){scanf("%d%d",&a,&b);p(+)p(-)p(*)b&&p(/)b&&p(%)}

(107B)

defineは1つで十分だった。可読性もささやかに向上
printf("%d"#x"%d=%d\n",a,b,a x b)として1Bの節約を図ったら、p(%)で%d%%d=...と展開された結果残念なことになった

Revised (renda):

   1 #define p(x)printf("%d%s%d=%d\n",a,#x,b,a x b);
   2 a;main(b){scanf("%d%d",&a,&b);p(+)p(-)p(*)b&&p(/)b&&p(%)}

(106B)

p(x)の後のSpaceいらないよね！
- 一応hijiri(x86_64)のgccで通ることは確認。sunやnestだとどうでしょう
  - そうか、気付かなかった...sunでもnestでも通りました

Revised (ytoku):

   1 #define p(x)&&printf("%d%s%d=%d\n",a,#x,b,a x b)
   2 a;main(b){scanf("%d%d",&a,&b)p(+)p(-)p(*),b p(/)p(%);}

(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:

   1 #include <stdio.h>
   2 
   3 int main(void)
   4 {
   5     char str[4], rts[4];
   6 
   7     printf("文字列を入力してください ");
   8     scanf("%3s", str);
   9 
  10     rts[0] = str[2];
  11     rts[1] = str[1];
  12     rts[2] = str[0];
  13     rts[3] = str[3];
  14 
  15     printf("%s %s %s %s \n ", str, rts, str, rts);
  16 
  17     return 0;
  18 }

(299B)

After:

   1 #define P(x);printf("%s ",x);
   2 #define S(i);r[i]=s[2-i]
   3 char str[4],rts[4],*s,*r=rts;main(){P("文字列を入力してください")s=gets(str)S(0)S(1)S(2)P(s)P(r)P(s)P(r)P("\n")}

(168B)

main関数の中にセミコロンが1つもないCのコードである。Pの汎用性は計りしれない
- Pの効果はprintfが3つ以上現れたときに発揮される
  - 引数に特定のパターンがあればもっと効果を発揮する
グローバル変数は0で初期化される
warning: this program uses gets(), which is unsafe.

Revised (ytoku):

   1 #define P(x)printf("%s ",x);
   2 #define S(i)r[i]=s[2-i];
   3 char str[4],rts[4],*s,*r=rts;main(){P("文字列を入力してください")P(s=gets(str))S(0)S(1)S(2)P(r)P(s)P(r)P("\n")}

(166B)

最初のstrの表示は反転処理の前に行うことができるので、getsした足でそのまま表示で1文字削減
さらに、これによってPとS以外の文が消えたのでセミコロンをマクロの最後において1文字削減

Revised (ytoku on the dark side):

   1 #define P(x)printf("%s ",x);
   2 #define S r[i]=s[2-i++]
   3 char str[4],rts[4],*s,*r=rts;i;main(){P("文字列を入力してください")P(s=gets(str))S;S;S;P(r)P(s)P(r)P("\n")}

(161B)

ダークサイドに落ちた結果がこれだよ＼(^o^)／
どうみても動作未定義です。本当にありがとうございました。

Revised (ytoku):

   1 #define P(x)printf("%s ",x);
   2 char str[4],rts[4],*s,*r=rts+3;main(){P("文字列を入力してください")for(P(s=gets(str))*s;)*--r=*s++;P(r)P(str)P(r)P("\n")}

(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

   1 #include <stdio.h>
   2 int main(){
   3         int i,m,n,c;
   4 
   5         scanf("%d",&m);
   6         for(i = 1;i <= m;i++){
   7                 c=0;
   8                 n=i;
   9                 while(n > 1){
  10                         if(n / 2 * 2 == n){
  11                                 n /= 2;
  12                         }else{
  13                                 n = n * 3 + 1;
  14                         }
  15                         c++;
  16                 }
  17                 if(c <= 10) printf("F(%d)=%d\n",i,c);
  18         }
  19         return 0;
  20 }

(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

出力例1

Before

   1 #include <stdio.h>
   2 
   3 int main(void){
   4     int i, j, n, m;
   5 
   6     scanf("%d", &m);
   7 
   8     for(i = 2;i <= m;i++){
   9         n = 0;
  10         for(j = 1;j < i;j++){
  11             if(i%j == 0){
  12                 n += j;
  13             }
  14         }
  15         if(i == n){
  16             printf("%d\n", i);
  17         }
  18     }
  19     return 0;
  20 }

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 }

CategoryContest

-  ⇤ ← 2013-03-04 01:15:10時点のリビジョン67 → 
  サイズ: 14294
  編集者: nomeaning
  コメント:
+   ← 2013-05-18 23:48:44時点のリビジョン68 → ⇥
  サイズ: 15314
  編集者: nomeaning
  コメント:
-削除された箇所はこのように表示されます。
+追加された箇所はこのように表示されます。
 行 464:
+= Shortest Palindrome =
== 問題 ==
10文字以下の英大文字のみからなる文字列が与えられる。文字列の後ろになんらかの文字列を足して回文にするとき、最短となる文字列を答えよ。

== 入出例 ==
||<ROWCLASS="header"> 入力 || 出力 ||
|| ABA || ABA ||
|| APB || APBPA ||
|| ABAB || ABABA ||

== Before ==
{{{#!highlight c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int is_palindrome(const char *s){
  int i, j;
  for(i = 0, j = strlen(s) - 1; i < j; i++, j--){
    if(s[i] != s[j]){
      return 0;
    }
  }
  return 1;
}

int main(void) {
  char str[15];
  int i, len, j;
  scanf("%10s",str);
  
  for(len = strlen(str); len < 100; len++){
    char s[100];
    s[len] = '\0';
    for(i = len - 1, j = 0; str[j]; i--, j++){
      s[i] = str[j];
    }
    memcpy(s, str, strlen(str));
    if(is_palindrome(s)){
      puts(s);
      return EXIT_SUCCESS;
    }
  }
  return EXIT_FAILURE;
}
}}}

鶴亀算

Before:

After:

Revised (ytoku):

PKU 1006

Before:

After:

四則演算と剰余

Before:

After:

Revised (renda):

Revised (ytoku):

ICPC2010 インターネット予選 A問題

Before:

After:

Revised (nomeaning):

3文字の文字列の反転

Before:

After:

Revised (ytoku):

Revised (ytoku on the dark side):

Revised (ytoku):

Revised (nomeaning):

ツリーの表示

Before

After (clear):

Revised (renda):

Revised (ytoku):

Revised (nomeaning):

2011年度センター試験 数学IIB 第6問 C移植版

Original

Before

After

Revised (ytoku):

Revised (nomeaning):

Revised (nomeaning):

完全数を求める

問題

入力

出力

入力例1

出力例1

Before

After (ytoku):

Revised (ytoku):

After (nomeaning):

Revised (ytoku):

Revised (nomeaning):

Revised(nomeaning):

Revised(nomeaning):

Shortest Palindrome

問題

入出例

Before

2011年度センター試験　数学IIB 第6問 C移植版