ABC#011 C.123引き算
Haskellで挑戦したけどダメで、C++で書いても間違えるという・・・
問題
数字Nについて、1,2,3の中から好きな数値を引く操作を100回まで行える。
最終的に0にできるかどうかYES/NOで返す。
ただし、NG数字が3つあり、その数字に一時的にでもなってしまってはいけない。
考え方
Haskellで再帰を書いたらメモ化の仕方がよくわからず・・・そもそもメモ化するような書き方をしない気がするけどわからない・・・
0から逆に増やす方向に、毎ターン、前ターンまでで行けてた数値から1,2,3を足した部分を行けるようにする。それを100ターン分繰り返す。300まで*100ターン=30000回程度しかループしないので、問題ない。
または、greedyに3,2,1の順序で優先的にいけるだけいって調整するようなやりかたで十分。
Haskellで解いた
import Control.Applicative import Control.Monad import Data.List remove_in :: [Int] -> [Int] -> [Int] remove_in [] ng = [] remove_in (x:xs) ng | x `elem` ng = remove_in xs ng | otherwise = x : remove_in xs ng add123 arr ng = arr' where arr' = remove_in (nub $ (map (+1) arr) ++ (map (+2) arr) ++ (map (+3) arr)) ng make_table :: [Int] -> [Int] -> Int -> [Int] make_table arr ng itr | itr < 0 = [] | otherwise = nub $ arr ++ (make_table arr' ng (itr-1)) where arr' = add123 arr ng main :: IO () main = do n <- readLn ng <- replicateM 3 readLn -- print $ (make_table [0] ng 100) putStrLn $ if n `elem` make_table [0] ng 100 then "YES" else "NO"
remove_inじゃなくてfilterで書きたい。
無駄なのが多いけどうまい書き方がまだわかってない・・・
-- notElemがあった add123 arr ng = filter (`notElem` ng) (nub $ (map (+1) arr) ++ (map (+2) arr) ++ (map (+3) arr))