Zenn
🍇

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

2024/08/09に公開
Haskell
AtCoder
tech

A4

問題：
整数Nが10進法表記で与えられます。
Nを2進法に変換した値を出力するプログラムを作成してください。
制約：

  • Nは1以上1000以下の整数

入力：
N

出力：
Nを2進法に変換した値を、10桁で出力してください。
桁数が足りない場合は、左側を0で埋めてください。

提出コード

toBin :: Int -> Int -> String
toBin 0 _ = "" 
toBin i n
  | n < 2 = toBin (i-1) 0 <> show n
  | otherwise = let d=div n 2; r=mod n 2 in toBin (i-1) d <> show r
  
main :: IO ()
main = do
  n <- getLine >>= return.read 
  putStr $ toBin 10 n

結果

AC 時間：1ms 警告なし

考察

前回ちょっと触れた interact をここで試してみやうかな と思ふ
interactは次のやうな型をもつ

interact :: (String -> String) -> IO ()

つまり interactに渡すのは ひとつの函數で その函數は 文字列をとって文字列を返す
文字列はどこから取るのかといへば IOから取る つまり入力文字列をとる
文字列をどこに返すのかといへば IOに返す つまり出力文字列を返す
だから 入力文字列をとって問題を解くための「整数のデータ」に變換し 問題を解いて 最後に解答を文字列に變換する といふ一連の流れを ひとつの「函數のまとまり」として記述できる
今回入力は一行だけなので getLineだけでも 十分簡潔なのだけれど 今後入力が増えていくと活躍するはずだ

再提出

toBin :: Int -> Int -> String
toBin 0 _ = "" 
toBin i n
  | n < 2 = toBin (i-1) 0 <> show n
  | otherwise = toBin (i-1) (div n 2) <> show (mod n 2) 
  
main :: IO ()
main = interact $ toBin 10 . read

結果

AC 時間：1ms 警告なし

付記

toBin :: Int -> Int -> String
toBin 0 _ = "" 
toBin i n
  | n < 2 = toBin (i-1) 0 <> show n
  | otherwise = toBin (i-1) (div n 2) <> show (mod n 2)

について
例へば13を10桁の二進数にしたい場合 toBin 10 13 を評価することになります
二行目の toBin 0 _ = "" といふのは もしtoBin に渡される第一引數が 0 であれば ""(空の文字列)を返す といふことなので toBin 10 13が與へられた場合 スルーされます
三行目 toBin i n に toBin 10 13がパターンマッチされ i=10, n=13と定まります
四行目 もし n < 2 であれば 結果が toBin (i-1) 0 <> show n となるのですが n=13 なので スルーされます 五行目 otherwiseは 「それ以外の場合」といふことです なのでtoBin (i-1) (div n 2) <> show (mod n 2)のi=10, n=13が適用されtoBin 9 (div 13 2) <> show (mod 13 2)となりますdiv 13 2は 13割る2の商であり 6 ですmod 13 2は 13割る2の余りであり 1 です だから 上の式はtoBin 9 6 <> show 1となります これはtoBin 9 6に 文字列 "1" を連結したものです 同様に考へるとtoBin 9 6の結果はtoBin 8 3に 文字列 "0" をつなげたものとなりtoBin 8 3の結果はtoBin 7 1に文字列 "1" をつなげたものとなりtoBin 7 1の n=1 だからn < 2の条件に引っかかって 三行目が適用されtoBin 6 0の結果に 文字列 "1" をつなげたもの となり それ以降は ずっと n=0 なのでtoBin 6 0 toBin 5 0 toBin 4 0 toBin 3 0 toBin 2 0 toBin 1 0 の6回は 全部 文字列 "0" をつなげるものとなり 最後にtoBin 0 0となるので 二行目のパターンマッチが適用されて 結果は空の文字列となります 以上のことから 全體の結果は"" <> "0" <> "0" <> "0" <> "0" <> "0" <> "0" <> "1" <> "1" <> "0" <> "1"であり0000001101` となります
というやうな つたない説明は 「ほら かうやって考へたら ちゃんと結果を出してるのが分かるでしょ」といふことを だらだらと書いたものなのですが
かういった 「再帰函數」のコードを書くとき このやうに考へてから書くわけではないです 少なくとも私は
まづ ざっくり次のやうに考へました
「10桁で埋めなきゃいけないんだから 1桁づつ なんらかの計算をして 10回くり返すんだな」
「といふことは 10 から始めて それを 1 づつ 減らしていって 最後に 0 になったら終了させたい」
「1桁づつの計算は "0" か "1" の文字列を生むことにして それを連結させれば 最終的な結果になるよな」
「つまり 結果は文字列になるから 整数(桁數)と整数(變換する10進數)をとって 文字列を返すわけだから・・・」
といふわけで 一行目に 型の情報を書き 二行目に終了状態を書き 三行目以降に 1桁づつの計算部分を書く とふ感じでやってみて
エラーが出たり 結果がおかしかったら 計算部分について見直してみて 「あっ そっか ここはかう書いてやるといいよな」みたいな感じで 正しい結果にもっていく
私としては かういふ考へ方といふのは すべての「操作」をイメージして 計算を「処理」していくより 壓倒的に 頭を使はなくて済む(なんといふか 頭のリソースを使はなくて済む)氣がします
言葉を變へれば 面倒臭いことを いちいち細かく考へなくて済む
ぢゃなくて 「これって 要は かういふことをしてるよね」といふやうな 本質的な部分を考へてみて それが動いたときは 「やべ! オレ天才!」みたいに調子に乘れるし
動かなかったとき 「あっ さうか さういふことか〜」みたいな氣づきがあって なんか自分が 頭よくなったやうな氣がするし といふか コンピュータから 知恵を授けてもらったやうな氣になる
といふわけで まあ 要は Haskellが好きといふことを言ひたいわけです〜
ちょっと全然違ふ話になるかもなんだけど 頭の「得意な」働かせ方みたいなのがある と思ふんだよね
これは 先天的な能力の部分もあると思ふし 生きてる間の鍛へ方にもよるんだと思ふんだけど
いはば「瞬發力」と「熟考力」
この2つは 両立しないことが多い氣がする
つまり 物事を瞬時に判断してこなせる人は あまり深く考えるのが苦手だったりするし
物事を深くじっくり考へるのが好きな人は 何かを瞬時に判断して實行するのが苦手だったりする
これは 向き 不向き みたいな話で 仮に みんなで集まって何かやるなら それぞれ自分に向いてゐることをやっていくと プロジェクトがうまく進む といふことなんだらうけど
ここに 道具として「コンピュータ」がある場合 こいつの壓倒的な能力って たぶん「瞬発力」の部分なんだよね
瞬時に計算して結果を出す
だから コンピュータがすごく發達して AIなんかも すごいレベルに行きつつあるやうな昨今なんかは ぼくら人間の側には 特に「熟考力」が求められるんぢゃないかな〜 と思ふ
よく 「仕事ができる」と見做されるやうな人って とりわけ「瞬発力」に優れてゐる人が多いと思ふ
とくに 人にサービスを提供するやうな仕事は 「決められたことを・きちんと・はやく・効率よく・合理的に」提供することが求められるから そもそも 物事を深く考へる必要性が あんまない
でもこれから 壓倒的なレベルで AI がさういふことをやってくれる時代になると思ふ
それこそ アート作品みたいなものだって AIが速く 効率的に なんかちゃんとしたものを提供できる
でも さうなれば さうなるほど
「結局人間の強みってなんだらう」
といふことを 多くの人が考へるやうになって
「決められてゐないことを・適當に・じっくりと・深く」やっていくことの価値が 再認識されるんぢゃないかな
「決められてゐない」といふことは ルールにとらはれない といふことで
個人個人が 全然別々の価値基準をもって 物事を考へたり 行動したりすることが これまで以上に自由になっていって それでも全體がうまくまとまる みたいな世の中になっていく といふか なっていくといいな〜 って思ってゐる
たとへば こんなことが起きたらワクワクするな〜 みたいなもののひとつは
學校(みたいなもの)にゐる算數の先生 ひとりひとりが 全然違った教へ方をしてゐて 各自の「流派」なんてあったりして ある「流派」の「先生」が好きな人たちが その「先生」の下に集まる とか
なんか江戸時代みたいな感じだけど 時代の逆行ではなくて 新しい時代が さういふ多様性にあふれた 面白い時代になってくといいし さうなりつつあるんぢゃないかな〜って思ってゐます (ちなみに昨今言はれてゐる多様性とかダイバーシティみたいな言葉は本質的には「均質化」を意味してゐて 価値観を統一したい意圖しか感じない かういふ偉い政治家のおっさんや おばはんの観念はまう「さういふ考へかたもあるよね〜」みたいに見做されていくと思ふ)
「みんなが やりたいことを自由にやり出したら 世の中めちゃくちゃになる」
といふ観念は まう通用しなくなる ってかぶちこわしてみせる!
だから私は やりたいことを自由に とことんやっていく といふ道を進む
でも
「やりたくないことを 一生懸命やる」人がいたって 全然いいぢゃん
たぶん 今 やりたくないことを 頑張ってやってゐる人も
「やりたいことを 自由にやる」人がいたって いいぢゃん
と思ってゐる人が きっと昔よりずっと多くなってる氣がする〜

B4

問題：
2進法表記で表された整数Nが与えられます。
Nを10進法に変換した値を出力するプログラムを作成してください。
制約：

  • Nの長さは1文字以上8文字以下
  • Nは0と1からなる
  • Nの先頭の桁は1である

入力：
N

出力：
答えを整数で出力してください。

次のコードは WA(答へが間違ひ)でした(AC×7, WA×13)

提出コード

toDec :: String -> Int 
toDec bi = foldr (\(b,i) acc -> if b=='1' then acc+2^i else acc) 0(zip bi [0::Int,1..])
  
main :: IO ()
main = do
  bin <- getLine 
  print $ toDec bin

これは zip bi [0::Int,1..] のところがおかしかった
これだと 與へられた二進数の一番上の桁にインデックス0が對應してしまふことになります
zip (reverse bi) [(0::Int)..]
にするか もしくは
zip bi (reverse [(0::Int)..])
として 二進数の一番下の桁とインデックス0が對應するやうにしてやらないといけない
ただ 後者のコードだと 前者にくらべて 1000倍以上時間がかかりました

再提出

toDec :: String -> Int 
toDec bi = foldr (\(b,i) acc -> if b=='1' then acc+2^i else acc) 0 (zip (reverse bi) [(0::Int)..])
  
main :: IO ()
main = getLine >>= print . toDec

結果

AC 時間：2ms 警告なし

Discussion