競プロ鉄則 Haskell AtCoder 振り返り5
A5
問題：
赤・青・白の3枚のカードがあります。
太郎君は、それぞれのカードに1以上
3枚のカードの合計を
制約：
-
N -
K
入力：
出力：
答えを整数で出力してください。
提出コード
calc :: (Int,Int,Int) -> Int
calc (a,b,c)
| a==b && b==c = 1
| a==b || b==c || a==c = 3
| otherwise = 6
main :: IO ()
main = do
ints <- getLine >>= return.map read.words
let n = head ints
let k = last ints
let nl = [1::Int,2..n]
print $ sum $ map calc [(a,b,c)|a<-nl,b<-[a..n],c<-[b..n],a+b+c==k]
結果
AC 時間：1411ms 警告なし
試行
ints <- getLine >>= return.map read.words
let n = head ints
let k = last ints
の部分は
[n,k] <- getLine >>= return . map read . words
とかけます
面白いことに ここらへんのコードを interact を使って
main :: IO ()
main = interact $ \inp -> (map read . words) inp & \ls ->
case ls of
[n,k] -> show $ sum $ map calc [(a,b,c)|a<-[1::Int,2..n],b<-[a..n],c<-[b..n],a+b+c==k]
_ -> ""
のやうにすると 實行時間が2秒を越えてしまひ 失敗します
いろいろと試したので main函數のコードと 實行結果を載せてをきます
1
main = interact $ \inp -> (map read . words) inp & \[n,k] ->
show $ sum $
map calc [(a,b,c)|a<-[(1::Int)..n],b<-[a..n],c<-[b..n],a+b+c==k]
時間： 2213ms
警告
app/Main.hs:10:52: warning: [-Wincomplete-uni-patterns]
Pattern match(es) are non-exhaustive
In a lambda abstraction:
Patterns of type ‘[Int]’ not matched:
[]
[_]
(_:_:_:_)
|
10 | main = interact $ \inp -> (map read . words) inp & \[n,k] ->
| ^^^^^^^^^^...
2
main = interact $ \inp -> (map read . words) inp & \ls ->
case ls of
[n,k] -> show $ sum $ map calc [(a,b,c)|a<-[1::Int,2..n],b<-[a..n],c<-[b..n],a+b+c==k]
_ -> ""
時間：2208ms 警告なし
3
main = interact $ \inp -> (map read . words) inp & \ls ->
case ls of
[n,k] -> let nl = [(1::Int)..n]
in show $ sum $ map calc [(a,b,c)|a<-nl,b<-[a..n],c<-[b..n],a+b+c==k]
_ -> ""
時間： 2207ms 警告なし
4
main = interact $ \inp -> (map read . words) inp & \ls ->
case ls of
[n,k] -> let nl = [1::Int,2..n]
in show $ sum $ map calc [(a,b,c)|a<-nl,b<-[a..n],c<-[b..n],a+b+c==k]
_ -> ""
時間： 2210ms 警告なし
5
main = do
[n,k] <- getLine >>= return.map read.words
let nl = [1::Int,2..n]
print $ sum $ map calc [(a,b,c)|a<-nl,b<-[a..n],c<-[b..n],a+b+c==k]
AC 時間：1421ms 警告なし
6
main = do
[n,k] <- getLine >>= return.map read.words
let nl = [(1::Int)..n]
print $ sum $ map calc [(a,b,c)|a<-nl,b<-[a..n],c<-[b..n],a+b+c==k]
時間：2207ms 警告なし
7
main = do
[n,k] <- getLine >>= return.map read.words
print $ sum $ map calc [(a,b,c)|a<-[(1::Int)..n],b<-[a..n],c<-[b..n],a+b+c==k]
時間：2207ms 警告なし
8
main = do
[n,k] <- getLine >>= return.map read.words
print $ sum $ map calc [(a,b,c)|a<-[1::Int,2..n],b<-[a..n],c<-[b..n],a+b+c==k]
AC 時間：1421ms 警告なし
考察
結果が變はった原因は 2つの条件に絞られました
ひとつは interactを使って書いたときと 書かなかったとき
この場合 interactを使って書くと もうひとつの条件がどんな場合でも 2秒を越えます
まうひとつは 連続した整数のリストをつくるときに
(A) [1::Int,2..n] と書いたときと
(B) [(1::Int)..n] と書いたとき
interactを使はなくても (B)のやうに書くと 2秒を越え失敗します
このリストを一度變數に束縛した場合(nl)と さうしなかった場合の2通りをそれぞれ試しましたが 結果は ほとんど變はりませんでした
これらの原因は 私には分かりません
多分Haskellコンパイラーの もっと詳しい内部を理解してゐないと これを説明するのは難しいのではないでせうか
ただ (B)の場合の遅れについて ちょっと予想できるのは 1..n と書いたとき 1の次が2である といふことをコンパイラーが判断するために何かしらの計算がなされてゐるだろう といふことで
それに對して (A) は 1,2..n と 1の次が2であることが明示されてゐるので 1の次が2であることを確定するための計算をする必要がない ・・・のかな なんて思ひました
あと interact についてですが これは 外部から文字列をとってきて 純粋な計算として利用できるやうにするための函數 という風に考へられます
だから とってきた純粋な文字列を出発點として いろいろな操作を加へていきます
ですが getLine からパターンマッチで 純粋な整数のリストを取り出すやうな
[n,k] <- getLine >>= return.map read.words
といった書き方だと 純粋なものとして扱ふ對象が はじめから 整数のリストだけです
つまり interactを使ふと 純粋な計算の對象が 文字列から始まるのに對し 初めからパターンマッチをした場合は 純粋な計算の對象が 整数のリストから始まることになり それだけ對象が制限されてゐるために 計算速度も速くなるのではないでせうか
こんなふうに考へると interactはなるほど便利な函數なのですが 入力された文字列情報を 色々な形に變換してから パターンマッチして計算する場合 ただ自分の欲しいパターンを書いただけだと 他のパターンはどうすんねん と警告されるし case文で場合分けするのは 何かちょっと 美しくない といふか 面倒臭いやうな感じになってしまふことが ちょっと分かった氣がしました
Discussion