例題メモ - Rokiのチラ裏

問題を作成したのでそのメモ。

Q

整数 $a_s \ast 1,a_s \ast 2...,a_s\ast n$ という数列がある。その数列中からいくつかを選び、その和を ${ \displaystyle k }$ とする。

任意の整数 ${ \displaystyle s }$ 、 ${ \displaystyle n }$ 、 ${ \displaystyle k }$ を入力(任意の数値が設定できるのであれば何でもいい)し、上記の関係の数列であるか判別しなさい。

解法

この問題の解法は、BFSもしくはDFS法等が考えるのに容易である。例としてDFSでの解法を以下に示す。

#include<iostream>
#include<vector>
#include<type_traits>
#include<srook/mpl/interval_sequence.hpp>
#include<boost/type_index.hpp>
#include<sprout/random.hpp>

template<class Operator,int interval,int random_min,int random_max,class Sequence=std::integer_sequence<int>>
using make_random_interval_sequence=
    srook::mpl::make_interval_sequence<
        srook::mpl::interval_sequence::Exp<
            Operator,
            sprout::random::combine(sprout::random::minstd_rand0(SPROUT_UNIQUE_SEED),sprout::random::uniform_smallint<int>(random_min,random_max))()
        >,
        interval,
        Sequence
    >;

template<class Range>
bool dfs(Range&& ar,int n,int k,int i,int sum)
{
    return i==n ? sum==k : 
        dfs(std::forward<Range>(ar),n,k,i+1,sum+ar[i]) ? true :
            dfs(std::forward<Range>(ar),n,k,i+1,sum) ? true : false;
}

int main()
{
    using random_interval_sequence_type=make_random_interval_sequence<srook::mpl::interval_sequence::plus,5,1,100>; // 任意の整数、この例では5を基準、間隔値として、1~100の区間のコンパイル時乱数(sに該当する)を用いて整数のシーケンスを生成

    std::cout<<boost::typeindex::type_id<random_interval_sequence_type>().pretty_name()<<std::endl; // 生成されたシーケンスの出力
    auto v=srook::mpl::make_range_from_sequence<std::vector>(random_interval_sequence_type()); // 生成されたシーケンスを任意の範囲の初期値として与え生成
    std::cout<<std::boolalpha<<dfs(std::move(v),3,16,0,0)<<std::endl; // 結果
}

回答としては動的でも静的でも構わないのだが、不定な間隔のシーケンスの生成はコンパイル時に行っている。乱数生成にはsprout.randomを使わせて頂いている。一定の間隔のシーケンスの作成には、~~srook.mpl.interval_sequence~~srook.mpl.constant_sequence.interval_sequenceを使っている。

余談となってしまうが、一応これの使い方は以下の通りである。

#include<srook/mpl/interval_sequence.hpp> #include<vector> #include<iostream> #include<iterator> #include<boost/range/algorithm/copy.hpp> int main() { using namespace srook::mpl; auto v=make_range_from_sequence<std::vector>(make_interval_sequence<interval_sequence::Exp<interval_sequence::plus,2>,5>()); // 5を始点に2の間隔で5つの要素のベクターを生成 auto v1=make_range_from_sequence<std::vector>(make_interval_sequence<interval_sequence::Exp<interval_sequence::multiply,2>,10>()); // 10を始点に2の積数の間隔で10つの要素のベクターを生成 boost::copy(std::move(v),std::ostream_iterator<decltype(v)::value_type>(std::cout," ")); // 5 7 9 11 13 boost::copy(std::move(v1),std::ostream_iterator<decltype(v)::value_type>(std::cout," ")); // 10 20 40 80 160 320 640 1280 2560 5120 }

※追記
汎用性を高めるため若干実装を変更した。よって使い方が少し異なる。

#include<srook/mpl/constant_sequence/interval_sequence.hpp>
using type=srook::make_interval_sequence<srook::interval_sequence::plus,0,3,10>; // 0を始点に3ずつ加算される間隔で10個の要素を持つシーケンスを生成する