🍅

競プロ鉄則 Haskell AtCoder 振り返り1

2024/07/31に公開

どーも yokop です
「競技プログラミングの鉄則」といふ本を知り
やってみよーといふことではじめました
この本に關するページが

にあり登録するとコードを提出したりテストコードを實行したりといろいろできます
提出したコードをふりかへり
あれこれ考へたり
手なおしして再提出したりするきっかけになればと思ってます

A1

問題：整数 N が与えられるので、一辺の長さが N であるような正方形の面積を出力するプログラムを作成してください。
制約：N は 1 以上 100 以下の整数

提出したコード

main = do
  a <- getLine
  print ((read a :: Int)^2)

結果

AC(Accepted)

警告

app/Main.hs:1:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature: main :: IO ()
  |
1 | main = do
  | ^^^^

app/Main.hs:3:25: warning: [-Wtype-defaults]
    • Defaulting the type variable ‘b0’ to type ‘Integer’ in the following constraints
        (Integral b0) arising from a use of ‘^’ at app/Main.hs:3:25
        (Num b0) arising from the literal ‘2’ at app/Main.hs:3:26
    • In the first argument of ‘print’, namely ‘((read a :: Int) ^ 2)’
      In a stmt of a 'do' block: print ((read a :: Int) ^ 2)
      In the expression:
        do a <- getLine
           print ((read a :: Int) ^ 2)
  |
3 |   print ((read a :: Int)^2)
  |                         ^

考察

いろいろ注意されました
やっぱ main函數の上にちゃんと型注釈を書いたはうがいいっぽいです
あとべき乗の2はちゃんと Int型に指定したはうがいいんだと思います

再提出

main :: IO ()
main = do
  a <- getLine
  print ((read a :: Int)^(2 :: Int))

結果

警告がなくなりました!

實驗

べき乗を使はないで單にかけ算をしたら速度はどうなるのでせうか
ちなみに上の實行時間は 1ms です

main :: IO ()
main = do
  a <- getLine
  print ((read a :: Int)*(read a))

テストケースの9, 83, 92が實行時間 2ms になってしまひました
read を二回つかってゐるのがよくなかったでせうか
いちど別の變數に束縛したらどうなるでせうか

main :: IO ()
main = do
  a <- getLine
  let b = read a :: Int
  print (b*b)

テストケースの5, 46, 53, 60, 75, 90, 92で實行時間 2ms になりました
なんかべき乗が効率よかったっぽいです

付記

Haskellを全く知らない人にすぐ上のコードを説明するとしたらどんな風にしたらいいかな〜
main といふのは函數の名前です
函數といふのは何らかの「値」を入れたらひとつ「値」を出すやうな機能をもった「モノ」です
ここで「値」といふのは「型」によってどんな「値」なのかを決められます
・・・
やばい長くなりさうなので手短に
一行目 main 函數は IO () といふ型であることを明示してゐます(なくても動く)
二行目 main はプログラムを實行させる特殊な函數でそれは do 以下のことをします
三行目 a といふ變數に入力からの文字列(一行分)を指定します
四行目 b といふ變數は a を Int といふ型として讀み替へた値であるとします (たとへば文字列の "12" が整数の 12 として bに指定されます
五行目 b*b (bとbのかけ算) を文字列にして出力します
そろそろ次行ってみやう〜!

B1

問題: 整数 A と B が与えられます。
A+B の値を出力してください。
制約:

A は 1 以上 100 以下の整数
B は 1 以上 100 以下の整数

入力:
A B

提出したコード

main :: IO ()
main = do
  a <- getLine
  let as = map read $ words a :: [Int]
  print (sum as)

結果

AC 實行時間：2ms 警告なし

考察

次のやうにしたら實行時間に影響あるでせうか

main :: IO ()
main = do
  as <- getLine >>= return . map read . words
  print $ sum (as :: [Int])

結果

最初のコードではテストケース 1,2,4,5,6,7 で 2ms
次のコードではテストケース 1,2,3,5 で 2ms でした
若干速くなったのかな？

付記

たぶんHaskellを知らない人の「謎ポイント」であらうことを予想します!
「$」ってなんじゃ!!
map read $ words a といふのは
map read (words a) と書くのと同じです
これは a (入力として一行分の文字列が入ってゐる) に words といふ函數を適用することで
まづ文字列のリストをつくります
たとへば a = "12 35" だったら
words a は ["12","35"]
となります
このそれぞれの要素に read 函數を適用するのが map 函數の役割です〜
だから最終的に
[12, 35] といふリストになります
でもこの12 とか 35 とかは Int型とも見れるし Integer型とも見れるし Double型とも見れちゃいます(他にもある)
だから :: [Int] とかくことでこれは「Int型の數字のリストとして見やうね!」と指定してゐます
なんで Int型にするのかといふとたぶんメモリの面で効率がいいんぢゃないかと思ふからです (扱ふメモリの量があらかじめ決まってるからたぶん効率いい)
すごい大きな整数とか扱ひたいときは Integer型ぢゃなきゃダメだと思ひます〜
それから
map read (words a) と書くのは
(map read . words) a とも書けます
これは a に words と map read を合成した「函數」を適用するといふ意味です
わーー! なに「<-」これ! なに「>>=」これ!!
って声が聴こへてきさうなので・・・
getLine が出力するのは IO String といって IO文字列型です
IO といふのは入出力に關係したもんだよ〜みたいなことでそのIOが String(文字列)を中に入れてる感じです
IO が冷蔵庫だと思ってくださいこれにはいろんな機能があります
冷やしたり冷やしたり・・冷やしたり・・・
このなかに入ったものは冷えてゐます
IO に入った文字列は冷えた文字列です
その冷えてゐる文字列から「文字列」だけ取りだして變數(ここでは a とか as)に指定するのが <- です
コップに冷蔵庫から取り出した不二家のレモンスカッシュ(結構すき)を入れる感じです
でもまってください <- をやるまえにやることがあります
>>= です
まづ冷蔵庫(IO)から文字列を出すまえに冷蔵庫の中の文字列だけに
map read . words を適用します
冷蔵庫の中でいろんな操作をすることは難しいので一旦取り出すのですが
必ず冷蔵庫の中に返さなければなりません (返さないとダメよ!! とママから怒られます)
この「返す」といふのが return です
return をしたものはもはや文字列ではなく數字のリストになってゐるのですがそれは冷蔵庫の中にあります
で! それを <- をつかって取り出すんです

as <- getLine >>= return . map read . words

なので as は數字のリストなのですがほんとはこの時點では數字かどうかも判断できません
read函數は「數字として讀む」といふ函數ではありません
いふなれば「適切に讀まうね」みたいな函數です
次の行

print $ sum (as :: [Int])

は print (sum (as :: [Int])) と同じことですが
as を Int型のリストとしてねといってリストの要素をぜんぶ足す sum といふ函數が適用されてゐます
ここで Haskellのコンパイラーはかしこいので「あーそっか Int型にしたいのね」と解釈して read 函數の結果はInt型になるんだと私は思ってゐます
あ〜なんかダラダラと長くなってしまひました
そんぢゃあ競技プログラミングの鉄則 Haskell 問題1 の振り返りを終はります

A1

提出したコード

結果

警告

考察

再提出

結果

實驗

付記

B1

提出したコード

結果

考察

結果

付記

Discussion