競プロ鉄則 Haskell AtCoder 振り返り3
A3
問題：
赤いカードが
また、青いカードが
太郎君は、赤いカードの中から1枚、青いカードの中から1枚、合計2枚のカードを選びます。
選んだ2枚のカードに書かれた整数の合計が
制約：
-
N -
K - $P_1,P_2,⋯,P_Nは1以上100以下の整数
- $Q_1,Q_2,⋯,Q_Nは1以上100以下の整数
入力：
提出コード
import Control.Monad (replicateM)
inputLines :: Int
inputLines = 3
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n getLine >>= return.(map ((map read).words))
resBool :: Bool -> IO ()
resBool b = putStr (if b then "Yes" else "No")
isCondition :: Int -> [(Int,Int)] -> Bool
isCondition _ [] = False
isCondition k ((p,q):xs) =
if k == p+q then True else isCondition k xs
main :: IO ()
main = do
a <- inputIntList inputLines
let k = (head a)!!1
let ps = a!!1
let qs = a!!2
let pairList = [(p,q)|p<-ps,q<-qs]
let b = isCondition k pairList
resBool b
結果
AC 時間：3ms 警告なし
考察
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n getLine >>= return.(map ((map read).words))
について
いろいろ手直しできると思ふ
まづ map read は それ自體結合の優先度が高いので 括弧はいりません
それと replicateM で getLine を n 回くり返して得た行のリストそれぞれに對して(map) 文字列のリストをつくり(words) そのリストの要素それぞれに對して(map) 適切な型に變換する(read) とやるよりも
getLine で得た一行分の文字列を 文字列のリストにし(words) そのそれぞれに對して(map) 適切な型への變換をする といふ作業を n 回 くり返す (replicateM n) のはうが 簡潔に表現できる氣がしました
inputIntList n = replicateM n $ getLine >>= return . map read . words
それから
let k = (head a)!!1
let ps = a!!1
let qs = a!!2
といふ部分は パターンマッチで より簡潔に
let [[_,k],ps,qs] = a
と書けるだらうし 「!!」でリスト要素を檢索しないぶん 速くなるのではと思ひます
あと isCondition函數も any函數で表現できるかなと
再提出
import Control.Monad (replicateM)
inputLines :: Int
inputLines = 3
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n $ getLine >>= return. map read .words
resBool :: Bool -> IO ()
resBool b = putStr (if b then "Yes" else "No")
main :: IO ()
main = do
[[_,k],ps,qs] <- inputIntList inputLines
let pairList = [(p,q) | p<-ps, q<-qs]
resBool $ any (\(p,q) -> k==p+q) pairList
結果
AC 時間：2ms 警告なし
雑談
「初心者」っていふ言葉と同じく 「基礎」っていふ言葉にも 普遍性はないって感じる
人それぞれ 學びの道筋は違ってゐて 「あれをやっておいたから これが理解できた!」みたいなものがあるけど 人によって「あれ」も「これ」も違ふ
だから その人にとっての「基礎」といふのはあるかもだけど 誰にでも通用する「基礎」といふのはないし あまり「基礎」にとらはれると 何かを實際にやってみるとき 「自分は基礎ができてゐない」といふ思いが 實行する際の障害になったりすると思ふ
interact といふ函數を知ったとき「すげーー!」と思った
家からコンビニまでの近道を見つけた とかいふものではなく 家とコンビニをつなぐ ワームホールを發見したみたいな(おおげさ)
ここでも たぶん次の記事には使ってみやうと思ふけど interact を先に知ってゐる人からすれば replicateM より interactの方が基本的なんぢゃないかな
私にとっては わざわざ別のモジュールをインポートして函數を使ってゐたのが もともとある函數で 入出力のやりとりを一氣に書けてしまふ といふのは感動でしかない
だから もしHaskellをやったことのない人に Haskellを語るんであれば 私の感動したところを傳へられたら嬉しい
まあ 人の感じ方も千差万別だから なかなか難しいと思ふけど
ラピュタのオープニングのピアノ旋律で既に泣いてしまふオレの感動を 人に傳へるなんて 無理すぎるみたいに
昔は ただ かういった感動するものを創る人って ほんとすごい!!と思ふだけだったけど
實は みんながみんな感動するものではないし 感動する深さも違ふ
深く感動できる といふことは たぶん 感動したその自分に その方面の能力といふか 適性がある といふことだと思ってゐる
私は 自分の創ったもの(歌とかゲームとか文章とか授業とか)に 誰かひとりでも感動してくれたら 大成功だと思ってゐる
それは 自分の感動(思ひ)が 少なくとも ひとりには傳はった といふことだから
付記
let pairList = [(p,q) | p<-ps, q<-qs]
について
ghci (HaskellコンパイラGHCのREPL(對話型實行プログラム))で
[(p,q) | p<-[1,2], q<-[3,4]]
とかやると
[(1,3),(1,4),(2,3),(2,4)]
といふ結果が返ってきます
B3
この問題は 最初 WA(Wrong Answer) になりました
問題文のサンプルケースについては テストが通ったのですが
他のテストケースで 引っかかりました
それを 先に示して どのやうに改良したか お話していかうと思ひます〜
問題：
異なる3つの商品を選び、合計価格をピッタリ 1000 円にする方法は存在しますか。
制約：
3≤N≤100 1≤A_i≤1000 - 入力はすべて整数
入力：
提出コード1
import Control.Monad (replicateM)
inputLines :: Int
inputLines = 2
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n getLine >>= return.(map ((map read).words))
resBool :: Bool -> IO ()
resBool b = putStr (if b then "Yes" else "No")
main :: IO ()
main = do
inp <- inputIntList inputLines
let as = inp!!1
let b = or [p+q+r==1000|p<-as,q<-as,r<-as]
resBool b
結果
WA (テストケース12) 時間：11ms 警告なし
考察
間違へた原因は
let b = or [p+q+r==1000|p<-as,q<-as,r<-as]
の部分です
「異なる3つの商品」なので リストas から同じ要素が p にも q にも r にも指定されてしまふ このやうなコードは駄目でした
これを pやqやrが 同値をとらないやうに手直しすると(他の部分もA3にならって直します)
import Control.Monad (replicateM)
inputLines :: Int
inputLines = 2
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n $ getLine >>= return. map read .words
resBool :: Bool -> IO ()
resBool b = putStr (if b then "Yes" else "No")
main :: IO ()
main = do
[_,as] <- inputIntList inputLines
let b = or [p+q+r==1000|p<-as,q<-as,r<-as,p/=q,p/=r,q/=r]
resBool b
となり この結果は AC,時間10ms,警告なし でした
けれども p, q, rが同じでない といふのは 必ずしも as から「同じ要素を選んでゐない」といふことにはならない筈です
多分テストケースは asがすべて違ふ値段に設定されてゐたために 正解となっただけではないでせうか
例へば as が [200,300,300,400] だった場合 200+300+400/=1000 ですが 300+300+400==1000 になるので 上記のコードでは不正解となる筈です
そこで as のそれぞれの要素にインデックスをつけ そのインデックスが被らないやうに p,q,rを指定する といふコードを書きました
import Control.Monad (replicateM)
inputLines :: Int
inputLines = 2
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n $ getLine >>= return. map read . words
resBool :: Bool -> IO ()
resBool b = putStr (if b then "Yes" else "No")
main :: IO ()
main = do
[_,as] <- inputIntList inputLines
let asP = zip as [(0::Int)..]
let b = or [p+q+r==1000|(p,ip)<-asP,(q,iq)<-asP,(r,ir)<-asP,ip/=iq,ip/=ir,iq/=ir]
resBool b
これで 結果 AC,時間11ms,警告なし でした
付記
zipは リストとリストをくっつけて タプル(a,b)のリスト にします
例へば
zip [1,2,3] [7,8,9] なら
(1,7),(2,8),(3,9) となります
おもしろいのは
zip ['a','b','c'] [1..]' とかすると [('a',1),('b',2),('c',3)'] といふ感じで結果が出るといふことです
[1..] といふのは 1,2,3,4.. と續く いはゆる「無限リスト」ですが
zipが適用されることで 「あっ ここまで必要なのね!」 といふことで 1,2,3 だけが使はれます
基本的に 必要になるまで 評価が後まはしにされる といふ「遅延評価」は 私のHaskell好きポイントのひとつです
もちろん すぐ評価させることもできますが あくまで「標準は」遅延評価で これを 英語で lazy evaluation といひます
別に 英語の知識をひけらかすために書いたのではなく lazy といふのは 「怠けもの」みたいな意味ですよね？ 私は さういふ言葉が Haskellといふ言語に使はれてゐるのが 面白くもあり 好感がもてるんです
自分自身が ほぼあらゆることに關して 基本的に好きなことしかせず 「本當にせっぱつまった時」「必要にかられた時」にしか物事を實行しない 本當の意味で 怠けものなんで
私の自慢は そんなんで今まで生きて來た といふことです!
なんと 今日で 生まれてから 18002日目です(さういへば この記事を書き出したのが 二日前だったので ちょうど一萬八千日目の記念日でした!)
あっ この記事は 好きだから書いてるだけで 仕事のために必要 とか 誰かに言はれて とか 全然ありません
それこそ ほとんど衝動みたいな感じで 續くかわからんけど やってみてる といふしだいです
それでは 今回はここまでといたします〜
Discussion