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))