結果

問題 No.225 文字列変更(medium)
ユーザー infer496infer496
提出日時 2017-07-02 16:13:07
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 7,370 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 34,944 KB
実行使用メモリ 9,356 KB
最終ジャッジ日時 2024-10-05 08:32:13
合計ジャッジ時間 1,396 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 4 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 1 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 AC 4 ms
8,740 KB
testcase_13 AC 5 ms
9,356 KB
testcase_14 AC 5 ms
9,136 KB
testcase_15 AC 4 ms
8,756 KB
testcase_16 AC 4 ms
8,836 KB
testcase_17 AC 4 ms
8,808 KB
testcase_18 AC 4 ms
8,540 KB
testcase_19 AC 4 ms
8,832 KB
testcase_20 AC 5 ms
8,508 KB
testcase_21 AC 4 ms
8,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
#define MOD 1000000007
#define END printf("\n");return 0;
#define QS09(how_data,data) qsort(data,how_data,sizeof(long),(int (*)(const void *,const void *))qsort_09);
#define QS90(how_data,data) qsort(data,how_data,sizeof(long),(int (*)(const void *,const void *))qsort_90);
#define I(a) long a;scanf("%ld",&a);
void input_array(long how_data,long *data);
void output_array(long how_data,long *data);
void input_array2(long first , long second , long data[][2]);
void format_array(long how_data ,long *data,long what);
long get_random(long min, long max);
long factorial(long n);
long fibonacci(long n);
int qsort_09(const int *sys1 , const int *sys2);
int qsort_90(const int *sys1 , const int *sys2);
long sel_max(long a , long b);
long sel_min(long a , long b);
long array_max(long how_data,long *data);
long array_min(long how_data,long *data);
long can_DP(long how_data,long *data,long how_can,bool *can);
long array_sum(long how_data,long *data);
long Leven_dist(char *now , char *target);
void prime_fact(long target, long *data);
long get_digit(long target);
long ncr(long n , long r);
long npr(long n , long r);
long nhr(long n , long r);

long loop1,loop2,loop3,loop4,loop5,i_temp;
char c_temp;

typedef struct{
    long from;
    long to;
    long omomi;
} wdg; //WeightedDirectedGraph
long BellmanFord(long how_tyouten,long how_hen,long start_ten,long goal_ten,wdg hen_data[]);

int main(void){
    char S[1001],T[1001];
    scanf("%d %d\n");
    scanf("%s\n%s",S,T);
    printf("%d",Leven_dist(S,T));
    END;
}
 

 
void input_array(long how_data,long *data){
    long loop;
    for(loop=0;loop<how_data;loop++){
        scanf("%ld",&data[loop]);
    }
    return ;
}
void output_array(long how_data,long *data){
    long loop;
    for(loop=0;loop<how_data;loop++){
        printf("%ld ",data[loop]);
    }
    return ;
}
 
void input_array2(long first,long second,long data[][2]){
    long loopA,loopB;
    for(loopA=0;loopA<first;loopA++){
        for(loopB=0;loopB<second;loopB++){
            scanf("%ld",&data[loopA][loopB]);
        }
    }
    return ;
}
void format_array(long how_data ,long *data,long what){
    long loopA;
    for(loopA=0;loopA<how_data;loopA++){
        data[loopA]=what;
    }
    return ;
}
 
long get_random(long min, long max){   //指定の範囲から乱数を1つ返すやつ
    //srand((unsigned int)time(0));   //現在時刻で疑似乱数初期化
    rand();rand();rand();rand();    //乱数を空打ち
    return (rand()%(max+1-min))+min;
}
 
 
long factorial(long n){//n!のMOD10^9+7を返すやつ
    unsigned long long int ret=1;
    for(long i=1;i<=n;i++)ret=(ret*i)%1000000007;
    return (long)ret;
}
 
int qsort_09(const int *sys1 , const int *sys2){ //小さいのが上にくるやつ
    //qsort(data,how_data,sizeof(long),(int (*)(const void *,const void *))qsort_09);
    if(*sys1<*sys2){
        return -1;
    }else if(*sys1==*sys2){
        return 0;
    }else{
        return 1;
    }
}
 
int qsort_90(const int *sys1 , const int *sys2){ //大きいのが上にくるやつ
    //qsort(data,how_data,sizeof(long),(int (*)(const void *,const void *))qsort_90);
    if(*sys1<*sys2){
        return 1;
    }else if(*sys1==*sys2){
        return 0;
    }else{
        return -1;
    }
}
 
long fibonacci(long n){
    switch(n){
        case 0:return 0;
        case 1:return 1;
        default :return fibonacci(n-1)+fibonacci(n-2);
    }
}
 
long sel_max(long a,long b){
    if(a>b)return a;
    return b;
}
 
long sel_min(long a,long b){
    if(a>b)return b;
    return a;
}
 
long can_DP(long how_data,long *data,long how_can,bool *can){//Typical DP Contest A
    //data内で組み合わせられる和をcanに0 or 1で入れる
    //返り値はパターン数
    long loopA,loopB;
    long ret=0;
    for(loopA=0;loopA<how_can;loopA++){//初期化
        can[loopA]=0;
    }
    can[0]=1;//絶対にありえる
    for(loopA=0;loopA<how_data;loopA++){
        for(loopB=how_can-1;loopB>=0;loopB--){
            if(can[loopB]==1 && loopB+data[loopA]<how_can){
                can[loopB+data[loopA]]=1;
            }
        }
    }
    for(loopA=0;loopA<how_can;loopA++){
        if(can[loopA]==1){
            ret++;
        }
    }
    return ret;
}
long array_max(long how_data,long *data){
    long loop;
    long ret=data[0];
    for(loop=0;loop<how_data;loop++){
        if(ret<data[loop])ret=data[loop];
    }
    return ret;
}
long array_min(long how_data,long *data){
    long loop;
    long ret=data[0];
    for(loop=0;loop<how_data;loop++){
        if(ret>data[loop])ret=data[loop];
    }
    return ret;
}
long array_sum(long how_data,long *data){
    long ret=0;
    long loop;
    for(loop=0;loop<how_data;loop++){
        ret+=data[loop];
    }
    return ret;
}
long Leven_dist(char *now , char *target){
    long loopA,loopB;
    //レーベンシュタイン距離を求める
    // 参考文献
    // http://nw.tsuda.ac.jp/class/algoB/c13.html  (アルゴリズム理解)
    // http://d.hatena.ne.jp/ohnishiakira/20090809/1249845529  (実装)
    long len_now=strlen(now)+1;
    long len_target=strlen(target)+1;
    long d[len_now][len_target]; //計算用
    for(loopA=0;loopA<len_now;loopA++) d[loopA][0]=loopA;
    for(loopA=0;loopA<len_target;loopA++) d[0][loopA]=loopA;
    for(loopA=1;loopA<len_now;loopA++){
        for(loopB=1;loopB<len_target;loopB++){
            long cost=(now[loopA-1]==target[loopB-1] ? 0:1);
            d[loopA][loopB]=sel_min(sel_min(d[loopA-1][loopB]+1,d[loopA][loopB-1]+1),d[loopA-1][loopB-1]+cost);
        }
    }
    return d[len_now-1][len_target-1];
}
void prime_fact(long target, long *data){
    long loopB=0;
    long loopA=2;
    long moto_target=target;
    while(target!=1){
        loopA-=1;
        while(1){
            loopA++;
            if(loopA>=sqrt(moto_target)+100){
                data[loopB]=target;
                target=1;
                break;
            }
            if(target%loopA==0){
                data[loopB]=loopA;
                target/=loopA;
                loopB++;
                break;
            }
        }
    }
    return ;
}
long get_digit(long target){
    return (long)(log10(target)+1);
}
long ncr(long n , long r){
    //パスカルの三角形
    long loopA,loopB;
    long pascal[100][102]={{0}};
    pascal[1][0]=1;
    pascal[1][1]=1;
    for(loopA=2;loopA<100;loopA++){
        pascal[loopA][0]=1;
        for(loopB=1;loopB<loopA;loopB++){
            pascal[loopA][loopB]=pascal[loopA-1][loopB-1]+pascal[loopA-1][loopB];
        }
        pascal[loopA][loopA]=1;
    }
    return pascal[n][r];
}
long npr(long n, long r){
    return ncr(n,r)*factorial(r);
}
long nhr(long n , long r){
    return ncr(n+r-1,r);
}


long BellmanFord(long how_tyouten,long how_hen,long start_ten,long goal_ten,wdg hen_data[]){
    long dist[100000];
    format_array(100000,dist,10000000000);
    dist[start_ten]=0;
    
    for(int loopA=0;loopA<how_tyouten;loopA++){
        for(int loopB=0;loopB<how_hen;loopB++){
            if(dist[hen_data[loopB].from]+hen_data[loopB].omomi<dist[hen_data[loopB].to]){
                dist[hen_data[loopB].to]=dist[hen_data[loopB].from]+hen_data[loopB].omomi;
            }
        }
    }
    
    return dist[goal_ten];
}
0