HackerRank Weekly Challenges - Week 4 1問目 - Palindrome Index

Source

HackerRank Weekly Challenges - Week 4 1問目
problem statement(コンテストページ)
problem statement

問題概要

長さ $N$ のアルファベット小文字のみからなる文字列 $S$ が与えられる.
$S$ から高々 $1$ 文字を削除して回文にしたい.
削ると回文になるのは何文字目か(または $1$ 文字も削らなくても良いか)を求める問題.
答えが複数あるならば,どれを出力しても良い.
高々 $1$ 文字削ると回文にできることは保証されている.

解法

$S$ の中で,$k$ 文字目と $N-k+1$ 文字目が一致しないという最小の $k$ を見つけてくる.
そのような $k$ が存在しなければ,既に回文である.
また,$S$ の中で $k$ 文字目と $N-k+1$ 文字目の間を削っても,この不一致が解消されることはなく回文にならない.
$k$ 文字目より前,または,$N-k+1$ 文字目より後を削って回文になることはあるかもしれないが,それで回文になるなら,$k$ 文字目または $N-k+1$ 文字目を削っても回文になるので,$k$ 文字目を削ってみて回文になっているかを調べて,回文になっていないなら $N-k+1$ 文字目を削れば良い.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int T;
int N;
char S[1100000];

int isOK(int k){
  int a = 0, b = N-1;
  for(;;){
    if(a==k) a++;
    if(b==k) b--;
    if(a >= b) break;
    if(S[a] != S[b]) return 0;
    a++; b--;
  }
  return 1;
}

int main(){
  int i, j, k;

  reader(&T);
  while(T--){
    N = reader(S);
    rep(i,N) if(S[i]!=S[N-1-i]) break;
    if(i==N){
      writer(-1, '\n');
      continue;
    }
    if(isOK(i)) writer(i, '\n');
    else        writer(N-i-1, '\n');
  }

  return 0;
}

Current time: 2017年07月21日13時33分32秒
Last modified: 2014年09月23日00時46分41秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w4
トップページに戻る

Logged in as: unknown user (not login)

ログイン: