2010年09月30日 木曜日
■ [SPOJ]TWOSQRS(2)
なんか知らないけど同じコードを実行してもC++の方が２倍くらい速い...
ただ、実行時間的にもっと良いやりかたがあるようだ...
フォーラムのコードそのまんまなんだけど...
#ifdef WIN32 #define INPUT "%I64u" #define _CRT_SECURE_NO_WARNINGS #else #define INPUT "%lld" #endif #include <cstdio> #define N 1000000 typedef unsigned long long ull_t; int sieve[N]; ull_t primes[100000]; int main(int argc, char* argv[]) { ull_t n; int T, i, j; int index = 0; for(i = 2; i < N; i++) if(!sieve[i]){ primes[index++] = i; for(j = i * 2; j < N; j += i) sieve[j] = 1; } scanf("%i", &T); while(T--){ int done = 0; scanf(INPUT, &n); if(n > 0){ for(i = 0; i < index; i++){ int count = 0; while(n % primes[i] == 0){ if(primes[i] % 4 == 3) count++; n /= primes[i]; } if(count % 2 != 0){ printf("No\n"); done = 1; break; } } } if(!done) puts(n % 4 != 3 ? "Yes" : "No"); } return 0; }
■ [SPOJ]TWOSQRS(3)
Haskellでやってみたけど、素数生成でTLEしてしまう。比較的速いData.Seive.ONeillのコードを貼り付けたり、STでエラトステネスの篩を書いたけど、素数生成で精一杯で、その後の80000弱 * 100の走査をする時間がない。出力だって遅いのに勘弁...
他の方法で尺取りメソッドというのを使うと解けるらしいとのことだったのでやってみた。尺取りメソッドとは...、なんか検索しても見つからない？？？
せめて英語でなんて呼ぶかわかれば情報収集できそうだが、それすらわからない。が、方向性はわかったので、なんとか素数使わずにC/C++ならACするコードが書けた。
で、それをHaskellに移植、結果はTLEだった。untilとか使ってるので、ここをベタに書けば通るかもしれないし、x86コードにして埋め込めば確実にパスするけど、もう嫌になった。C/C++で0.8秒くらい掛かってるから、0.1秒くらいで解くようなアルゴリズムでないとHaskellでは厳しい...
多分、こんな感じでしょう...
#ifdef WIN32 #define INPUT "%I64u" #define _CRT_SECURE_NO_WARNINGS #else #define INPUT "%lld" #endif #include <cstdio> #include <cmath> typedef unsigned long long ull_t; bool check(ull_t n){ ull_t x(0), y(static_cast<ull_t>(floor(sqrt(static_cast<double>(n))))); for(;; x++){ while(x * x + y * y > n) --y; while(x * x + y * y < n) ++x; if(y < x) break; if(x * x + y * y == n) return true; } return false; } int main(int argc, char* argv[]) { ull_t n; int T; scanf("%i", &T); while(T-- > 0){ int done = 0; scanf(INPUT, &n); printf("%s\n", check(n) ? "Yes" : "No"); } return 0; }
Haskell...
なんかuntil使ってる辺りでTLEの臭いがプンプンする...
{-# LANGUAGE BangPatterns #-} import Control.Applicative import Control.Monad import Data.Int check :: Int64 -> String check n = calc 0 . floor . sqrt . fromIntegral $ n where calc !x !y = do let y' = until ((<= n) . (+ x ^ 2) . (^ 2)) (subtract 1) y x' = until ((>= n) . (+ y'^ 2) . (^ 2)) (+ 1) x case () of _ | y' < x' -> "No" | x' ^ 2 + y' ^ 2 == n -> "Yes" | otherwise -> calc (x' + 1) y' main :: IO () main = do loop <- replicateM_ <$> readLn loop $ readLn >>= putStrLn . check
■ [SPOJ]STAMPS
入力がでかいとビビルけど、この問題は大丈夫...だった...
つか、問題になってない...
{-# LANGUAGE OverloadedStrings #-} import Control.Applicative import Control.Monad import Data.List import Data.Maybe import qualified Data.ByteString.Char8 as BS main :: IO () main = do let readInts :: IO [Int] readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine t <- readLn forM_ [1 .. t] $ \caseNo -> do stamps : n : _ <- readInts friends <- scanl1 (+) . sortBy (flip compare) . take n <$> readInts let answer = case findIndices (stamps <=) friends of x : _ -> BS.pack . show $ x + 1 _ -> "impossible" BS.putStrLn $ BS.concat ["Scenario #", BS.pack $ show caseNo,":"] BS.putStrLn $ answer BS.putStrLn ""
■ [ネタ](演習)Haskellで正規表現を使いたい...orz(1)
Haskellで正規表現を使いたい。高機能じゃなくていいから、サクっと使える奴を作りたい。HackageDBに行けば、Regex.PosixとかRegex.TDFAとかあるけど、OJ(Online Judge)では使えないので貼り付けることができるような奴が欲しい...
低機能でも汎用性が欲しいので、Parsecとか標準かどうか微妙なライブラリは使わずに書く。出力としては、マッチした文字列の開始と終了インデックスを全てリストで返すことができれば十分とする。OJで使うかもしれないので、NFA(非決定性有限オートマトン(Non-Deterministic-Finite-Automaton))エンジンではなく、DFA(決定性...(Deterministic...))エンジンの奴でないと意味ない。NFAだとTLE確実だから...
Stringで作る方がパターンマッチとか使えてHaskellらしく書けると思うけど、遅すぎては意味がないのでByteStringを使う...
とりあえず、構文木を作る → NFAに変換 → DFAに変換の順で。参考書は「Ｃプログラマのためのアルゴリズムとデータ構造((著)近藤嘉雪)」位しか見当たらないないのだが、Haskellでも多分組めるでしょう...組めると思いたい...
まず、pureな正規表現(|、*、連結)が正しく処理できるようにする。(+、.、!、文字クラス、{n,m})とかは、前者を組み合わせるだけなので後で。入力はASCII限定でおｋ。エンコーディングとか考える必要なし(DFAなので２バイト文字は状態的に扱いたくない)...
要件はこれくらいかなぁ...
ただ、すごく長くなりそう...
■ [ネタ][QuickCheck](演習)Haskellで正規表現を使いたい...できるかなぁ(2)
とりあえず、入力を１文字ずつ読み込んで構文木を構築するパーザを作る。と言っても、Haskell的なやり方が全くわからないのだが、C/C++で再帰降下する感じでやるつもり。Parsecがこの辺は得意なんだけどなぁ...
で、入力を処理していって、成功ならJust(構文木)、途中で失敗したらNothingを返すようにしたいのだが、普通に関数で書こうとするとメンドイ...
だから、モナドにして処理の面倒な部分は(>>=)に押し込む。
それってStateTのベースモナドをMaybeにすればできなくね？？？
→ 書き終えてから気が付いた...orz。でも、failとか独自に定義したいかもしれないから、まぁいいや...
{-# LANGUAGE OverloadedStrings, ScopedTypeVariables, TypeSynonymInstances #-} import Control.Applicative import Data.List import qualified Data.ByteString.Char8 as BS import Test.QuickCheck import Test.QuickCheck.Checkers import Test.QuickCheck.Classes import Data.Typeable type BString = BS.ByteString newtype TreeBuilder a = TreeBuilder (BString -> Maybe (BString, a)) instance Monad TreeBuilder where return x = TreeBuilder $ \s -> Just (s, x) (TreeBuilder f) >>= k = TreeBuilder $ \s -> do let next (s', x') = g s' where TreeBuilder g = k x' f s >>= next fail _ = TreeBuilder $ \_ -> Nothing runTreeBuilder :: TreeBuilder a -> BString -> Maybe a runTreeBuilder (TreeBuilder f) pattern = do snd <$> f pattern getToken :: TreeBuilder Char getToken = TreeBuilder $ \s -> do if BS.null s then Nothing else Just (BS.drop 1 s, BS.head s)
IOやSTみたいに怪しいことするわけじゃなく、ただの関数合成を書きやすくしてるだけだからモナド則は基本的に成り立つはずだが、一応チェックする...
instance forall a. (Typeable a) => Show (TreeBuilder a) where show _ = "show: TreeBuilder - " ++ show (typeOf (undefined :: a)) instance Arbitrary BString where arbitrary = BS.pack <$> arbitrary instance CoArbitrary BString where coarbitrary s = coarbitrary $ BS.unpack s instance (Arbitrary a) => Arbitrary (TreeBuilder a) where arbitrary = TreeBuilder <$> promote (`coarbitrary` arbitrary) instance EqProp a => EqProp (TreeBuilder a) where (TreeBuilder f) =-= (TreeBuilder g) = property $ (=-=) <$> f <*> g instance EqProp BString where a =-= b = property $ a == b checkMonadLaws :: IO () checkMonadLaws = mapM_ quickBatch $ [ monad (undefined :: TreeBuilder (Int, Int, Int)) , monad (undefined :: TreeBuilder (String, Maybe Int, Int)) , monad (undefined :: TreeBuilder (Char, [Int], (Int, Char)))] -- $> checkMonadLaws -- monad laws: -- left identity: +++ OK, passed 500 tests. -- right identity: +++ OK, passed 500 tests. -- associativity: +++ OK, passed 500 tests. -- monad laws: -- left identity: +++ OK, passed 500 tests. -- right identity: +++ OK, passed 500 tests. -- associativity: +++ OK, passed 500 tests. -- monad laws: -- left identity: +++ OK, passed 500 tests. -- right identity: +++ OK, passed 500 tests. -- associativity: +++ OK, passed 500 tests. -- (18.12 secs, 5209363436 bytes)
おｋです...
これでdo記法を使ってコードが書ける。pureな正規表現は先読みする必要ない(と思う)から、多分コレで十分...
parse :: BString -> Maybe Bool parse s = (`runTreeBuilder` s) $ do c1 <- getToken c2 <- getToken return $ c1 == 'A' && c2 == 'B' test :: IO () test = do print $ parse "abcde" print $ parse "ABCDE" print $ parse "" -- $> test -- Just False -- Just True -- Nothing -- (0.00 secs, 0 bytes)
こういうコードはHaskellは異様に書きやすい...
続くかもしれないし、心が折れるかもしれない...