epoch@まつやまの予選通過！

通らないと思ってたepochの予選が去年についで今年も無事通過しました。予想外なのでかなりうれしい。なぜ通らないと思ってたかはあとから書きます。
相方は@wand125(id:w125)で、チーム名はもふもふあるぱか。去年のチーム名はふわふわどーなつでした。由来はtwitterのアイコンから。
予選問題のコードは6~7割くらい僕が書きました。詳細は以下。

問題1

sortしてごにょごにょするだけ。
最初自分が書いた時は変なことをしててかなり遅かったので、相方のコードをちょっとだけ変えて送りました。この問題に限らず、入力はfgetsのほうがscanfより断然速い。

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define SIZE 500000
#define INF 1000000

int main(void){
  int N;
  int data[SIZE+1];
  int once[SIZE+1];
  int idx = 0;
  int max_of_twice = INF;
  char buf[256];

  fgets(buf, 256, stdin);
  N = atoi(buf);
  for(int i = 0; i < N; i++){
    fgets(buf, 256, stdin);
    data[i] = atoi(buf);
  }

  sort(data, data + N);
  for(int i = 0; i < N; i++){
    if(i + 1 < N && data[i] == data[i+1]){
      max_of_twice = data[i];
      while(i + 1 < N && data[i] == data[i+1]) i++;
    }else{
      once[idx++] = data[i];
    }
  }

  printf("%d\n",once[idx - min(max_of_twice,idx)]);
  return 0;
}

問題2

コード汚いです。（今ちょっとだけ直した。）下から順番に見てstackに入れていく感じ。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

char str[100001][256]; 

//1-insert 2-delete 3-change 4-same 0-none
int judge(const char* str1, const char* str2){
  int s1 = strlen(str1);
  int s2 = strlen(str2);
  int diff = abs(s1 - s2);
  int misscount = 0;
  if(diff > 1){
    return 0;

  }else if(diff == 1){
    bool swaped = false;
    if(s1 < s2){
      swap(str1,str2);
      swaped = true;
    }
    while(*str1 && *str2){
      if(*str1++ == *str2){
        str2++;
      }else{
        misscount++;
      }
      if(misscount > 1) break;
    }
    if(!*str2){
      return (swaped)?1:2;
    }

  }else if(diff == 0){
    while(*str1){
      if(*str1++ != *str2++){
        misscount++;
      }
      if(misscount > 1) break;
    }
    return (misscount)?3:4;
  }

  return 0;
}

int main(void){
  int N;
  int ope;
  long long ans = 0;
  stack<int> operation;
  char buf[1024];

  fgets(buf, 1024, stdin);
  N = atoi(buf);
  for(int i = 0; i < N; i++){
    fgets(str[i], 1024, stdin);
    str[i][strlen(str[i]) - 1] = '\0';
  }

  for(int i=N-1; i-1>=0; i--){
    if( !(ope = judge(str[i-1], str[i])) ){
      break;
    }
    operation.push(ope);
  }

  while(!operation.empty()){
    ope = operation.top();  operation.pop();
    switch(ope){
      case 1:
        ans += 1;
        break;
      case 2:
        ans += -1;
        break;
      case 3:
        ans += 2;
        break;
      case 4:
        ans *= 2;
        break;
    }
  }

  printf("%lld\n",ans);

  return 0;
}

問題3

「最上位桁に 0 が現れてもよい」。この条件が入ってるせいで難しかった。これがなければ桁数から簡単に探索できるのだけど、この問題だとうまく工夫しないといけない。で書いたコードがこれなのだけど、これだと100011111121のようなケースで誤判定する。これに気づいたのが予選が終わった日の夜ぐらいで、相方に教えてもらって絶望してた記憶がある。ちなみに提出したコードはこれじゃなくて、相方が書き換えて速くしてくれました。

#include <cstdio>
#include <cstdlib>
#include <cstring>

void printexp(char str[], int i, int j, int len){
  for(int l = 0; l < len; l++){
    if(l == i) putchar('+');
    if(l == j) putchar('=');
    putchar(str[l]);
  }
  putchar('\n');
}

bool equal(char str[], int i, int j, int len){ 
  //[0,i)+[i,j)=[j,len)
  int idx1, idx2, idx3, dig, up; //dig:各桁の値 up:繰り上げの値
  if(!(0 < i && i < j && j < len)){
    return false;
  }
  for(idx1 = i-1,  idx2 = j-1,  idx3 = len-1, up = 0, dig = 0;
      idx1 >= 0 || idx2 >= i || idx3 >= j ||  up != 0;
      idx1--,idx2--,idx3--,dig = 0){
    dig += up; up = 0; //繰り上げ処理
    if(idx1 >= 0) dig += (str[idx1]-'0');
    if(idx2 >= i) dig += (str[idx2]-'0');
    if(dig >= 10){
      up = dig/10;
      dig %= 10;
    }
    if(idx3 >= j) dig -= (str[idx3]-'0');

    if(dig != 0){
      return false;
    }
  }
  return true;
}

bool judge(char str[]){
  int len = strlen(str);
  int rcnt = 0; //右辺の桁数
  int initialZero = 0; //頭のゼロの数
  for(int i = 0; i < len; i++){
    if(str[i] == '0'){
      initialZero++;
    }else{
      break;
    }
  }

  if(initialZero == len) return true; //すべての桁が0
  
  for(int j = len - 1; j - 1 > 0; j--){
    if(str[j] != '0'){
     rcnt = (len - j);
    }
    if( equal(str, initialZero + (rcnt - 1), j, len) ||
        equal(str, initialZero + rcnt , j, len) ||
        equal(str, j - (rcnt - 1), j, len) ||
        equal(str, j - rcnt, j, len) ){
      return true;
    }
  }

  return false;
}

int main(void){
  int N;
  int ans = 0;
  char str[1024];

  fgets(str, 1024, stdin);
  N = atoi(str);

  while(N--){
    fgets(str, 1024, stdin);
    str[strlen(str) - 1] = '\0';
    if(judge(str)) ans++;  
  }

  printf("%d\n",ans);

  return 0;
}