torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Regular Contest #022, A : スーパーICT高校生

問題概要

 文字列 S が与えられる。S が部分列として "ICT" を含んでいるかどうか求めよ。ただし、大文字と小文字は区別しない。

解法

 まず、capitalize に関する面倒事を避けるための常套手段で、全て大文字(または全て小文字)に予め変換しておきます。
 さて、S が部分列として "ICT" を含むとは、S 中に "ICT" がこの順に出現することと言い換えられます。従って、S を先頭から走査して、次に出現して欲しい文字が出現したところでカウントを一つ増やすという処理が考えられます。S の操作が終わったあと、カウントが 3 になっていれば S は "ICT" を部分列として含みます。

コード

which a b f = if f then a else b

main = putStrLn . which "YES" "NO" . ( `contains` "ICT" ) . map toUpper =<< getLine

_ `contains` [] = True
[] `contains` _ = False
(a:as) `contains` bb@(b:bs)
	| a == b = as `contains` bs
	| otherwise = as `contains` bb