AtCoder Beginner Contest #017 B問題 - choku語

Source

AtCoder Beginner Contest #017
問題文

問題概要

空文字列はchoku語であり，choku語の末尾に $\verb|ch|$，$\verb|o|$，$\verb|k|$，$\verb|u|$ のいずれかの文字列を連結したものもchoku語である．
また，以上のルールでchoku語であると言い切れないものはchoku語ではない．
長さ $N$ のアルファベット小文字のみからなる文字列 $S$ が与えられるので，文字列 $S$ がchoku語かどうかを判定する問題．

解法

先頭からでも末尾からでも文字列の端が $\verb|ch|$，$\verb|o|$，$\verb|k|$，$\verb|u|$ のいずれかであれば，それを取り除き同じように繰り返す．
空文字列になればchoku語だし，途中で端が $4$ 種類のどれでもないようなものになればchoku語ではない．
消したつもりになって判定すれば時間計算量 $O(N)$ で，実際に消していっても高々 $O(N^2)$ 程度．

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)

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;}c[s]='\0';return s;}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N;
char S[100];

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

  N = reader(S);
  i = 0;
  while(i < N){
    if(S[i]=='c' && S[i+1]=='h'){ i+=2; continue; }
    if(S[i]=='o' || S[i]=='k' || S[i]=='u'){ i++; continue; }
    break;
  }

  writerLn(i==N?"YES":"NO");

  return 0;
}

Current time: 2024年04月20日20時27分41秒
Last modified: 2015年01月21日00時49分38秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC017 ABC_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：