Zenn
🐡

ビット全探索を理解する！練習問題(7~9問目)【Haskellで競技プログラミングがしたい！ Part4】

2023/11/14に公開4件
Haskell
AtCoder
Codespaces
アルゴリズム×数学
tech

はじめに

少しずつ進んできましたね。この調子で頑張ります！
さて今回は7~9問目について回答してみましょう。
https://atcoder.jp/contests/math-and-algorithm/tasks

7問目

問題

N 以下の正の整数の中で、X の倍数または Y の倍数であるものの個数はいくつありますか？

解答

isMultiple :: Int -> Int -> Int -> Int
isMultiple x y n
    | n `mod` x == 0 || n `mod` y == 0 = 1
    | otherwise = 0

solve :: Int -> Int -> Int -> Int
solve x y n = sum $ map (isMultiple x y) [1..n]

main:: IO ()
main = do
    input <- getLine
    let [n, x, y] = map read (words input) :: [Int]
    print $ solve x y n

解説

どのように計算するか迷ったのですが、今回思いついたのはガード条件を使った倍数判定です。
これを使うと関数のパターンマッチングにおいて条件を指定することができます。
isMultipleは、今回だとxまたはyで割ったときのあまりが0の時に1を返し、それ以外の時は0を返すように実装しました。
次にこの関数を使ってsolveを実装します。
1からnまでに対してisMultipleを適用して1になったものの合計をとると個数が数えられそうと思いつき、

  • mapで[1..n]までの値にisMultipleを適用する
  • この処理の返り値のリストにsumして計算

としました。
最後に標準入力ですが、変数に値をBindするときもパターンマッチングが使えます。
なので入力が3個であることが事前にわかっているので、[n, x, y]として値を受け取れました。

8問目

問題

赤・青のカードが各1 枚ずつあり、あなたはそれぞれのカードに 1 以上 N 以下の整数を 1 つ書き込みます。
カードに書かれた整数の合計が S 以下となる書き方は、いくつありますか？

解答

solve :: Int -> Int -> Int
solve n s = sum [1 | i <- [1..n], j <- [1..n], i + j <= s]

main:: IO ()
main = do
    input <- getLine
    let [n, s] = map read (words input) :: [Int]
    print $ solve n s

解説

総当たりで計算したかったのでリスト内包表記を使いました。
内包表記とはもともと数学の集合に関する仕組みで、既存の集合から新たな集合を作るために使われるそうです。[1]
今回は2種類のカードがあり、それぞれ最大nまでの値をとるので、それぞれのカードがとる数字の集合、つまりリストは[1..n]で表現することができます。
またこの内包表記には条件を設定することができ、この条件がTrueになったものだけ新しいリストに追加されます。
今回はs以下が条件なので、2種類のカードの数字の合計i+jがs以下ならTrueとなりリストに1が追加されます。
最後にこの処理によって新しいリストが生成されるので、sumして組み合わせの数を合計しています。

標準入力は前のものと同様にパターンマッチングで変数にBindしました。

9問目

問題文にあった注意書き

全探索で解いても 1000 点中 500 点しか得られず、満点（AC）にならないことに注意してください。（本に記されている通り、一部の大きいケースでは現実的な時間で答えが求まらないからです）

問題

N 枚のカードが横一列に並べられています。左からi 番目

{{(1≤i≤N)}}
のカードには整数
{{A_i}}
が書かれています。
カードの中からいくつかを選んで、合計がちょうど S となるようにする方法はありますか。

解答

intToBits :: Int -> [Bool]
intToBits 0 = []
intToBits n = (n `mod` 2 == 1) : intToBits (n `div` 2)

genBits :: Int -> [[Bool]]
genBits n = [intToBits i | i <- [1..2^n]]

selectedSum :: [Int] -> [Bool] -> Int
selectedSum nums bits = sum $ zipWith (\b x -> if b then x else 0) bits nums

check :: Int -> [Int] -> [Bool] -> Bool
check s nums bits = s == selectedSum nums bits

output :: Bool -> String
output bool = if bool then "Yes" else "No"

main:: IO ()
main = do
    input <- getLine
    let [n, s] = map read (words input) :: [Int]
    input <- getLine
    let nums = map read (words input) :: [Int]
    let allBits = genBits n
    putStrLn $ output $ any (==True) $ map (check s nums) allBits

解説

最初どのように実装すればわからず、だいぶ苦戦しました・・・
この問題で設定されたnの値で計算完了するには動的計画法(DP)が必要になるのですが、自分はまだこの実装方法がよくわかっていません。
ただ全探索でも部分点があるということなので、まずは全探索で実装することを考えました。
この本のコラムにビット全探索で求めることができるとのことなので、この方法で実装を進めました。
(ビット全探索でより良い・または楽な実装方法がある場合は教えていただけると嬉しいです)

ビット全探索とは、ビット演算を使って可能な組み合わせを表現する方法です。
今回だとn枚あるカードの中からどれを選び、どれを選ばないかについてビットを使って表現します。
この手法を用いて最終的な計算結果(Yes or No)を求めるには以下の処理が必要になってきます。

  • 特定の数をビット表現に変換する
  • ビットとカードの情報を組み合わせて、選ばれたカードのみを抽出する
  • 選ばれたカードのリストから合計値を計算する
  • 合計値が指定する値と一致するかチェックする
  • カードがn枚あり、それぞれを選ぶ・選ばないという条件の時パターンは2^n個あるので、そのすべてのパターンについてビット表現に変換する
  • すべてのパターンにおいて、指定する値と一致するものが1つ以上あればYesを返し、そうでない場合はNoを返す

それぞれの機能を実装したのが解答になります。
簡単にそれぞれ実装した関数についての説明です。

intToBits

  • Int型の引数を受け取って、その余りが1ならTrue、0ならFalseになり、それをconsでつないでいく。
  • 再帰的に関数を定義してdivで2ずつ割っていく。
  • リストの最初は一番最初の2のあまりなので2^0の項が出てきて、次再帰で実行されるときは2^1の項が出てくる
  • これで引数が0になったら空のリストを返し、今まで出力してきたTrue、Falseが入ったリストが返ってくる
  • 最終的な返り値は通常のビット表現を左右反転したものとなるが、組み合わせを全列挙できれば良いので問題ない

genBits

  • 組み合わせが2^nパターンあり、このパターン数分だけビット表現に変換する必要がある
  • リスト内包表記を使ってIntのリストからビット表現のリストに変換した
  • selectedNum
  • ここではzipWithを使って、2つのリストを組み合わせて関数を適用した新たなリストを生成する
  • ラムダ関数を使い、ビットの値がTrueの時はカードの値を返し、Falseの時は0を返す
  • これによって選ばれたカードの数値だけが入ったリストが完成する
  • 最後にこのリストの値をsumで合計する

check

  • 指定の値sを引数にとって、先ほどのselectedNumの値と一致しているかどうか判定する

output

  • もしリストにTrueがあればYesを返し、そうでない場合はNoを返す

最後のprintするときの処理

  • map (check s nums) allBitsとして、checkに部分適用してBoolを受け取って値を返す形にしてmapを使う
  • これによって作られたリストは、選んだ組み合わせが指定の値と一致しているかどうかの結果が入っているもの
  • このなかにどれか1つでもTrueがあるかどうかチェックしたいので、any (==True)とする
  • 最後にこの値をoutputの引数に渡すことで無事目的の文字列が取得できる

という結果で、これで全探索することができました。
難しかったですがなんとかやり切れてうれしいです。

終わりに

なかなかこのような処理を日常考えていないので実装するのに結構時間がかかり大変でしたが、何とかなったのは少し自信になりました。
しかしこれはまだ入門でここからこの問題を時間内に計算を終わらせるアルゴリズムがあるので、そこも引き続き学んでいきたいです！
少しずつ重量が増えてきたので毎回3個ずつ解答を上げるのが難しくなるかもしれませんが、継続して解いていきたいと思っているので今後もこつこつ進めていきます。
今回も見てくれてありがとうございました！

参考

内包表記で参考になった記事

https://zenn.dev/masahiro_toba/articles/67c1b3c9e3b809

GitHubで編集を提案

Discussion

Nobuo YamashitaNobuo Yamashita

9問目は、（containersパッケージにあるData.IntSetモジュールの集合演算を使えばACになりそうですが）
ビットパターンを使うなら、type Bit = Bool ではなくて、type Bit = Int としておく方がすっきりするかもしれませんね。

module Main where

import Data.Bool
import Data.List

main :: IO ()
main = interact (encode . solve . decode)

decode :: String -> [[Int]]
decode = map (map read . words) . lines

encode :: [String] -> String
encode = unlines

solve :: [[Int]] -> [String]
solve dss = case dss of
  [n,s]:as:_ 
    -> bool ["No"] ["Yes"] (any (s ==) [selectedSum as bs | bs <- genBits n])

type Bit = Int

intToBits :: Int -> Int -> [Bit]
intToBits d n = snd (mapAccumL divMod n (replicate d 2))

genBits :: Int -> [[Bit]]
genBits d = [intToBits d i | i <- [0 .. 2^d-1]]

selectedSum :: [Int] -> [Bit] -> Int
selectedSum as = sum . zipWith (*) as
Nobuo YamashitaNobuo Yamashita

8問目は、

solve n s = sum [ min n (s - i) | i <- [1 .. min n (s-1) ]

などでどうでしょう。

Nobuo YamashitaNobuo Yamashita

7問目は、リストを生成しなくてもよい気がします。

solve n x y = div n x + div n y - div n (lcm x y)
シンシン

それぞれの問題についてコメントありがとうございます！

  • 7問目
    たしかに集合の演算すれば配列使わなくてよいので早くなりますね！
  • 8問目
    この計算も自分は愚直にリスト2個つかって内包表記していましたが、カードの数字を片側決めれば、そのパターン数は指定の数Sから引いた数に等しくなるということですかね。
    確かにオーダーがO(N)になって早くなりますねーありがとうございます！
  • 9問目
    使ったことない関数が多くまだ理解できていませんが、確かにtype Bit = Intとすることで掛け算をするだけでシンプルに選ばれたカードの数を抽出できますね、ありがとうございます！
    後は色々な関数の合成が使われていたりinteractを使っていたりとあるので、ここらへんは少しずつ使いながら学んでいきます。
    また、Data.IntSetでACできるらしいということについてもありがとうございます。
    集合を使ってどのように解くかについても考えてみようと思います！