epoch@まつやま プログラミングコンテスト予選突破！

epoch@まつやま　プログラミングコンテストの予選を突破しました。

プログラミングコンテストに出場をした事がないので、本当にうれしいです。愛媛県といえば、みかん。早く本場のみかんを食べたいですね。予選を突破できたのは一緒に参加したT君のおかげです。

ここで、自分が一番解くための考えを詰め込んだ問題2のソースコードをのせる事にします。

まずは問題の説明からですね。問題が長いので、簡単に説明しますと、

長さLの文字列Sがあり、次の三種類の変換を定義します。
・追加 : Sの先頭、末尾または途中に一文字だけ追加する
・削除 : Sから一文字だけ削除する。
・変更 : Sの中の一文字だけを別の文字に変更する。

N個の文字列が順番に与えられるとして、連続した文字列の間で上述のいずれかの変換が行われているかを見ます。始めの得点は０点で、追加されると１点、削除は−１点、変更は２点で得点が加算されます。同じ文字列が連続してあれば得点が２倍、変換や、同じ文字列ではなかった場合は得点が０点になります。N個の文字列を最後まで操作したら、得点を表示するプログラムを作成せよという問題です。



プログラムを作成するにいたってのポイントは、

・変換や、同じ文字列がある場合は得点が加算されたら、得点は増加していくが、全く関係のない文字列であった場合、得点が０点になるので、０点に成るまでの計算は無駄になってしまいます。なので、文字列を全て読み込んで、最後から得点が０に成るまでの文字列を確認していく事になります。変更なら２、追加なら１と、文字列ごとの関係を他の配列に格納し、最後に計算します。

・次に追加などの文字列の関係を調べるのは、始めに文字列の長さを調べます。こうするのは、追加、削除、変更、同等のどの場合でも、文字列の長さは１しか変わらないからです。あとは、文字列が１つ減っていたら、削除の可能性が。１つ増えていたら、追加の可能性が。文字列長が同じならば、同等の可能性があるので、文字を一個ずつ確かめ合わせてみていきます。

文字列の関係を調べるのは、一個ずつ見ていくだけなので、他に良いアルゴリズムがあるのかなあと思いましたが、結局見つからず。そのままにしておきました。次に、ソースコードをのせておきます。＊デバッグ用の余分なのが入っています。ブログの背景のせいで見難いですが、ご了承ください。 また、コメントが長く突き出ているところがあります。
*********************************************************************************
 // 問題２
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N 255

int main(void)
{
  int i, j, k;     //ループカウンタ
  int a = 0;       //文字列カウンタ　文字が異なった際に＋1される
  int n;           //文字列の数
  char **str;      //文字列
  int *stlen;      //文字列長
  int *counter = (int*)calloc(100000, sizeof(int));    //判定カウンタ　追加:1  削除:-1  変更:2  同等:3  それ以外:-2
  long long point = 0;   //ポイント
  clock_t start, end;
  start = clock();

  //文字列の数をnに格納
  scanf("%d", &n);

  //文字列長を動的確保
  stlen = (int*)calloc(n, sizeof(int));

  //文字列を動的確保
  str = (char**)malloc(sizeof(char*) * n);
  for (i = 0; i < n; i++) {
    str[i] = (char*)malloc(sizeof(char) * (N+1));
  }

  //文字列と文字列長を配列に格納
  for (i = 0; i < n; i++) {
    scanf("%s", str[i]);
    stlen[i] = strlen(str[i]);
  }

  //読み込んだ文字列群の後ろから見ていく（例外だった場合、0になるため、後ろから見る方が効率が良いため)
  for (i = n - 1; i > 0; i--) {
    //追加
    if (stlen[i] > stlen[i-1] && (stlen[i] - stlen[i-1]) == 1) {
      for (j = 0, k = 0; j < stlen[i]; j++, k++) {
    if (str[i][j] != str[i-1][k]){
      k--;
      if (a == 1) {
        counter[i] = -2;
      }
      a++;
    }
      }
      if (a == 1 || a == 0) {
    counter[i] = 1;
      }
      a = 0;
    }

    //削除
    else if (stlen[i] < stlen[i-1] && (stlen[i-1] - stlen[i]) == 1) {
      for (j = 0, k = 0; j < stlen[i]; j++, k++) {
    if (str[i][k] != str[i-1][j]){
      k--;
      if (a == 1) {
        counter[i] = -2;
      }
      a++;
    }
      }
      if (a == 1 || a == 0) {
          counter[i] = -1;
      }
      a = 0;
    }

    //変更　同等　
    else if (stlen[i] == stlen[i-1]) {
      if (strcmp(str[i], str[i-1]) == 0)
          counter[i] = 3;
      else {
        for (j = 0; j < stlen[i]; j++) {
          if (str[i][j] != str[i-1][j]) {
            if (a >= 1) {
              counter[i] = -2;
              a++;
              break;
            }
            a++;
          }
        }
        if (a == 1)
          counter[i] = 2;
        a = 0;
      }
    } else {     //なにも当てはまらなかった場合
      counter[i] = -2;
    }
   
    //例外が出たらbreak
    if (counter[i] == -2)
      break;
  }

  //counter変数からポイントを計算
  for (j = i; j < n; j++) {
    if (counter[j] == 1)
      point++;
    else if (counter[j] == -1)
      point--;
    else if (counter[j] == 2)
      point = point + 2;
    else if (counter[j] == 3)
      if (point != 0)
          point = point * 2;
  }
 
  end = clock();
  //解答
  printf("%lld\n", point);
  printf("%f秒\n", (double)(end - start)/CLOCKS_PER_SEC);

  //後処理
  free(stlen);
  free(counter);
  for(i = 0; i < n; i++) {
    free(str[i]);
  }
  free(str);

  return 0;

}
**********************************************************************************

 本戦は時間との勝負になるので、自分の考えた事をすばやく作れるようにしないといけないですね。C++より、Cの方が実行速度は速いらしいですが、コードの作成は、豊富なアルゴリズムのライブラリがあるC++の方が早く作成できるような気がしますね。しかし、C++はあまり触った事がないので、悩みどころです。

本戦はプログラミングをしている人に会える機会なので、楽しみですし、少し今想像して緊張してしまいますw