2020-02-23

■

C++ plant

久々に生存報告を兼ねて。最近忙しいとかで個人的なプログラミングがほぼできていないので悲しい。

C++だと f(A)=>g(T)=>h(A) ？みたいな呼び出しができるけど(Aは任意の型、Tはテンプレート型)

C#だとテンプレートを呼び出しに挟んでしまうと、多重定義の解決をしてくれないっぽい？リフレクションでTがA型の時は…みたいにも書けるだろうけど美しくないので...。
文字列だからフォーマットで回避できなくはないけどそうじゃない時どうすればいいだろう。
A型に戻せるようなAny型に置き換える？こういうやり方でやること自体が間違いなのかな。

C++ wandbox.org

C# wandbox.org

最近競プロできてない。モチベーションが上がらない理由みたいなのは一応把握していて
日曜日の夜遅くにやる&&たくさんやらないと点は上がらない（やったら上がるとは言っていない）
あたりなんだろう。

というかもっと言ってしまうと実はもう||今はやりたくなくて、そこにすごく都合のいい上記の理由があった
というだけかもしれないな？

プログラミングではない趣味が最近は相対的に面白くなってきていて、今は個人レベルで真菌や植物の無菌培養や増殖ができなくはなさそうなのでちょっとやってみようかなぁとか考えている。具体的には以下のリンクのようなこと。

洋蘭の無菌播種

今の課題は滅菌処理とそれに耐える容器などをそろえるのがしんどいということ。失敗するのはまだいいとして、上手くいかないことが分かってただ場所をとるゴミになってしまうかもしれないガラス瓶を50個や100個の単位で1万円以上だして買うのは結構勇気がいる。20個でもちょっとやってみるのには多いくらいだ。試験管かフラスコ + フタは綿, アルミホイル, コルク等で、とも考えたけれどオートクレーブ処理に耐えるかどうか、個人向けに試験管を販売するページに書いてないことが多い。普通の人はビー玉いれたり一輪挿しに使うくらいで高温にはさらさないらしい。企業や研究室向けだと50本とかの単位での販売になってしまう。うーん。フラスコは少数でも買えそうだけれど高い。一個600円では買えない。ジャム瓶でいいか、とも思ったけどフタが圧力なべによる処理を想定しているものがなさそう。そもそも高温に短い時間さらすのが限度というのがジャム瓶のフタの想定された用途のようで。

理想的にはフタが高温上記滅菌に耐えて、それなりに透明で採光性や観察に支障がないと嬉しい。

あと個人レベルの無菌培養の話はあんまググっても新しい情報がないような気がする。
みんな隠してるのかやっている人がいないのか。

2019-09-05

stateパターン

C++

stateパターンってどうなんだろうと前から思っている。
C++でゲームのコードを考える時によく出てくるように思うけれど
結局switchやifが消えてないように思うし、それぞれの子クラスが大きくならないか？って思う。
かといって子クラスがある程度肥大化するたびに共通部分を切り出して親クラスの共通処理に書くのも限度がある。 stateパターンを継承した子クラスは、遷移しうる状態の集まりのうちの1つであるはずだけれど、本当にすべての状態が持つべき共通の性質ってそんなにあるんだろうか。とりあえず最低限は今自分の状態が何で、次の状態が何で、その2つが違うかどうかがわかる実装を前書いたなぁ。

初期化時には今==次
今==次なら切り替えないで維持
今!=次なら切り替える
state内部で切り替えるべき条件が揃ったら’次’を今ではなくて次の遷移先にする

オーバーロードとかで分岐したほうがきれいなんだろうか。

そして子クラス間でデータを共有する方法も良くわからないし。 Data型を継承したData子クラスとかでうまいことできるんだろうか？

StateAとStateBがそれぞれInputDataA/OutPutDataA, InputDataB/OutputDataBで外部とやり取りするようなことを考えると StateA->StateBのデータの受け渡しでは
StateA->OutPutDataA->InputDataB->StateB のような流れになるのだと思う。
ここでStateA->StateCのような経路のやり取りを足すとなると同様に
StateA->OutPutDataA->InputDataC->StateC が増える。

結局これって
"「すべてのState」が持ちうるデータの和集合をStateの分岐をするマネージャクラスあたりに置いておいて、そこからStateのsetterやctorで入れてやる”
ような方法をわざわざ複雑怪奇にしたもののように思える。
これを簡潔にやれるようにしたのがDIコンテナというものではないのか？知らんけど。
DIコンテナみたいなことはC++だとJavaやC#でいうreflectionがなかったりで面倒な印象がある。

とりあえずシンプルで愚直なstateパターンを書いた。
これくらいの差異しかないと継承ではなくctorに別の引数を与えたインスタンスでもいいけど。
今日は時間がないのでここまでにして、今後ここから考えてみる。
Haskellみたいに状態をpair<状態, 次の状態を得る関数> (？)で管理するのも面白そうだけど、そのためにもなるべく状態そのものを小さく扱ったほうが良いように感じるんだよなぁ。難しい。

#include<iostream>
#include<memory>
#include<string>

namespace my
{

    class state
    {
        private:
            const std::string name_;

        public:
            state( const std::string& name_ )
                :name_{ name_ }{}

            auto name()const{ return name_; }

            virtual void exec()const {
                std::cout << this->name() << "\n";
            };

            virtual ~state(){}

    };

    class initial :public state
    {

        private:
        using super = state;

        public:
        initial()
            : super{ "initial" }{}

    };

    class running :public state
    {
        private:
        using super = state;

        public:
        running()
            :super{ "running" }{}

    };

    class exit :public state
    {

        private:
        using super = state;

        public:
        exit()
            :super{ "exit" }{}


    };

}


int main(){

    using my::state;
    using my::initial;
    using my::running;
    using my::exit;

    std::unique_ptr<state> sp{};

    sp.reset( new initial{} );
    while( sp != nullptr && sp->name() != "exit" )
    {
        sp->exec();

        if( sp->name() == "initial" )
            sp.reset( new running{} );
        else if( sp->name() == "running" )
            sp.reset( new exit{} );
    }

    sp->exec();
    sp.reset();

    std::cout << "finished all\n";


    return 0;
}

2019-07-26

gitlab CIのメモ [ C++ / cmake ]

C++ CI cmake

前書き

gitlab.com

C++の環境構築？のためにgitlab CIとかcmakeとか少し触ったのだけど、しばらく触らないかもしれないし、忘れないうちにメモしておこうと思う。
申し訳ないけれど何をやったのか気になる方はいっそリンク先の .gitlab-ci.yml を見てほしい。その方がはやい。
長い時間が空かない限りは自分は読めると思うし、それを細かく解説する気力はないです。。。
少なくとも自分は特殊な知識や技能でこれを成し遂げたわけではなくググって何とかしたのでググればできるはず。

とりあえず得た教訓

詳細

こんなところか？

git push は取り消せる
pushをトリガーにしてテスト回すのは割に合わない？
cmakeのversionはどれにするかよく考えたほうがいいかもしれない
BoostTestはBoostの一部

_1. について
addやcommitは消せるのは知っていた。pushを消すのは作業中には思いつかなかった。一方でrebaseで問題が起きるケースがあるのは知っていた( Git - リベース )。
rebaseはほぼ使わないのだけどコミットログをきれいにする用途で使うのかなぁくらいに思っていた。
リモートのブランチのログをきれいにする(rebaseする)と問題が起きるならできないってことか、くらいに思ってた。
けどできるらしいので次回はもっときれいにしましょうね( git pushを取り消す2つの方法 - Reasonable Code )。

_2. について
gitlabにpushしてbuildやtestの成否を待つのは大変苦しい。やってみて分かったけれど、今回のケースではそんなにメリットが感じられない。ローカルのdockerでやるのが難しいとかなら良いのかもしれないけどどうなんだろう。他の人にリポジトリが有効で、その有効の判断はどの環境/テストコードに基づいている、と明示できるというのは良いのかもしれないけどうーん。小規模ならローカルでテスト回して通ったらpushで良いのでは？と思う。分かんないけどbashなりbatなりでtestが通ったらmasterにcommit/push/merge&topic branchのdelete; 通らないならdev/hotfixのbranchにcommit/push みたいなことはできるんじゃなかろうか。いや分からんけど。

_3. について
gitlabにpushしてもbuildでコケる。ローカルでは上手くいく。何度もpushするのは面倒だし、gitlab上のdockerで何が起きているのかを逐一echoしようかと思ったら上手くできなかったり。そもそもechoで色々知れてもpushを繰り返すことになりそう。なのでローカルのdockerにgitを入れてgitlabからcloneしてbuildなりtestなりして調べることにした。

そしてcmakeのバージョンの差異が原因の1つだとわかった。 apt/apt-getでubuntu:18.04やdebianがインストールするcmakeはcmake 3.7 (?)で、ローカルのcmakeは3.15。
(今調べたらとりあえずubuntu18.04のcmakeは3.10.2みたいだ。
記憶違いかもしれない。debianもubuntuとcmakeのバージョンは同じだった気がするので3.10.2かもしれない?)

cmakeにはいろんな書き方があるらしい。
そしてsetや謎の変数${...}を多用する比較的古い書き方を回避できるらしいのも調べるうちに分かったのでなるべく新しい書き方にすることにして作業を進めていた。
情報が少ないのでかなりしんどかったけれど、古い書き方よりもCMakeLists.txtを書くのは楽だった。すっきりしてるように感じる。

そして取り入れた新しい書き方の1つにCMP0076の使用があった。
( CMakeとIDEを連携させる - Qiita

CMP0076 — CMake 3.13.5 Documentation )

残念ながらubuntuでデフォルトで入るcmakeは3.13に満たないので落ちていたらしい。 curlでcmake 3.15をDLしてtar, make, configureして...これでbuildは通るようになった。代わりにgitlab上でのbuild時間は一気に伸びてしまった。新しいcmakeを使えるようにするこの工程は時間をかなり食うらしい。
もうこの時点でサクサク開発するのとはかけ離れている。 cacheとかで回避できるんだろうか。

_4. について
考えてみれば当たり前の話なのだろうけど、BoostTestリポジトリだけclone/submoduleしても動かない。残念ながら”とりあえず試してみよう”というタイミングでこれに気づくことはできなかった。
ローカルにはBoostがあるから足りない分は多分そっちで解決されたのだろう。確かにCMakeLists.txt書いているときにUITESTの設定と比べてなんかDirectoryの設定が少し雑でも許されるなぁ?とは思っていた。

BoostTestを使うならローカルに持っておいてそれを参照するようにする。それでgitの管理に含めないのが想定された使用法なんだろうなぁと思った。 IUTESTもそうできるんだろうけど、今回はgitlabのCIでtestする+ヘッダオンリーの手軽さが重要だったので考えなかった。

次に似たようなことをやるならこれ参考にしたい。カバレッジも出したい。ローカルでtestしてその結果使ってgitlab/githubでカバレッジ見るとかもできそう？

Gitlab - Creating C++ applications with Gitlab CI from Uilian Ries

www.slideshare.net

2019-07-26

LIS ( Longest Increasing SubSequence )

ABC134-Eが解けない。解いている途中。 E - Sequence Decomposing

解説ではLIS（最長増加部分列）と同等のものを調べることでACできるとある。
LISは結構前に1度、かなり苦労して解けたのだけど解けなくなっていたので復習しないといけない。
てことで他の方のコードを見ていたら面白い解答があったので載せてみる。

Submission #6447713 - AtCoder Beginner Contest 134

何か要素数が大きい数列を構築するようなとき、追加と消去を繰り返すようなやり方では遅くなる傾向があって、その対策でLISでは2次元配列等に計算結果を記録していくのだと思っていたが通る場合もあるのか。(大抵vectorとかで作ったときの記憶なので遅いのは仕方ない)

でも考えてみると * erase ... O(1) * lower_bound/upper_bound ... O( log2 (ms.size()) ) * emplace/insert ... O(log (ms.size()) ) ?

なのでせいぜい O(N * log N) くらいなんだろうか。それだと通りそう。解説もO(N logN)だ。とりあえず O(N²)だと10¹⁰回ループしてTLEするので、それ以下に落とさないといけないのは分かる。

https://wandbox.org/permlink/uYEAlfaUcGHYNoNI

#include<iostream>
#include<set>
#include<algorithm>
#include<cstddef>
#include<vector>
#include<iterator>

using ui32 = std::uint32_t;
using ui64 = std::uint64_t;

//
//Longest Incresing SubSequence
//By multiset
int main(){
    ui32 n;
    std::cin >> n;


    std::vector<ui32> an(n);
    
    for( auto& e : an )
        std::cin >> e;


    auto solve1 = [&]()
    {
        std::multiset<ui32, std::greater<>> ms;
        // a1 > a2 > a3 > ...;
        auto p = [&]( auto it_ )
        {

            std::cout << "*it = ";
            if( it_ == std::end( ms ) )
                std::cout << "null";
            else
                std::cout << *it_;

            std::cout << ";\t";

            std::cout << "size = " << ms.size() << ";\t";

            std::cout << "ms:";
            for( auto e : ms )
                std::cout << e << " ";
            std::cout << "\n";
        };



        for( const auto e : an )
        {
            //upper_boundは最初に登場する e より大きい値のイテレータを返す
            //したがって x1 < x2 が成り立つ部分列をmsが構築していくことになる
            const auto it = ms.upper_bound( e );
            p(it );


            //最大値でないなら消す。
            //つまり max(ms) < e を満たす e の場合だけ ms.size() は増加する
            if( it != ms.begin() )
                ms.erase( std::prev( it ) );

            ms.emplace( e );
        }

        p( std::end( ms ) );

        std::cout << "LIS:" << ms.size() << "\n";
    };


    auto solve2 = [&]()
    {
        std::multiset<ui32> ms;
        // a1 < a2 < a3 <...
        auto p = [&](auto it_ ) {
            if( it_ == std::end( ms ) )
                std::cout << "null";
            else
                std::cout << *it_;

            std::cout << "\tsize = " << ms.size();
            
            std::cout << "\tms:";
            for( const auto e : ms )
                std::cout << e << " ";
            std::cout << "\n";

        };

        for( const auto e : an )
        {
            const auto it = ms.upper_bound( e );
            p( it );
            if( it != std::end( ms ) )
                ms.erase( it );

            ms.emplace( e );
            
        }

        p( std::end(ms) );

        std::cout << "LIS = " << ms.size() << "\n";

    };

    solve2();

    return 0;
}

2019-06-23

ABC131(A-E)

C++ python competitive programming

atcoder.jp

全体的に問題文が優しかったような気がする。
問題の難度も普通かそれよりも優しいものが多い印象。
その所為か提出速度でパフォーマンスが決まる感が強かったような。
いつもこんな感じなんだっけ。

A - Security

Si : 文字列Sの i 文字目
SiとSi+1を比較して一度でも==ならBad
i+1を| S |-1以下に収めないと範囲エラーに注意。こういうのってforなしでスマートに書けないのかな。
Submission #6054840 - AtCoder Beginner Contest 131

s = input()

is_bad = False
for i in range(1,len(s)):
    if s[i-1] == s[i]:
        is_bad = True
        break

print('Bad' if is_bad else 'Good')

B - Bite Eating

リンゴ i の味はL+i-1 Lはどのリンゴでも等しい定数。
i はリンゴが何番目か。
アップルパイの味への影響が最小となるリンゴ1つをつまみ食いする。
つまみ食いされたリンゴ以外のリンゴからできるアップルパイの味を出力する。

リンゴの味の総和からリンゴの味の絶対値が最小のものを減算すればよさそう。

Submission #6057024 - AtCoder Beginner Contest 131

n, l = map(int, input().split())


low = 9999
ans = 0
for i in range(n):
    taste = l+i
    low = min(taste, abs(low))
    ans += taste


print(ans - low)

C - Anti-Division

時間かかった。ifで結構時間をかけてしまった。
解説見ると後でifで1か0を追加するよりも(a-1//c)としたほうがスマートっぽい。
多分動くだろうし。
f(B) - f(A-1)は典型なので思いつきたい。
(思いついたのは少し違う。 f(B) - f(A) でAをカウントしても良いなら+1する)

途中でc*dではなくlcmが必要だと気づいて、pythonならどこかにあるでしょうってことで調べたらmathとfractions(3.4以前)と出てきた。
Atcoderのpython3は3.4.3なので以前ではない・・・よな、と思ってmathで提出したらREですね。
Atcoder python3( 3.4.3)ではfractionsを使いましょう。

Submission #6068902 - AtCoder Beginner Contest 131

import fractions

a, b, c, d = map(int, input().split())
c, d = min(c,d), max(c, d)

ans = b - a + 1 

if d%c == 0:#4 8 4 2
    ans -= b//c - a//c + (0 if a%c != 0 else 1)

else:
    x = b // c - a//c + (0 if a%c != 0 else 1)
    y = b // d - a//d + (0 if a%d != 0 else 1)

    lcm = c*d // fractions.gcd(c,d)
    t = b //lcm - a//lcm + (1 if a >= lcm and a%lcm ==0 else 0)

    ans = ans -x-y+t
#    print(x,y,t,lcm,ans)

#    ans += t 


print(ans)

D - Megalomania

Dっぽくない。いっそCより簡単だと思う。
罠かと思って色々考えたんだけど罠ではないっぽい...

とりあえず時刻 t は0から単調増加する。
締め切りについて昇順ソートすると、締め切りの単調増加を時刻の単調増加が追い越すのかを調べればいい。
反対に締め切りを降順ソートすると、昇順ソートでは処理できるのにこっちだとできないケースがありそうなので不適でしょう。
締め切りXが等しい仕事Wが複数があったとして、締め切りXを過ぎるまでにWsがすべて完了していないといけない。
つまり締め切りが等しい仕事同士の順番は結果に影響しない。たぶん。

とか考えると締め切りでソートしたら解けるっぽい。

pythonだと結構時間かかってるのでちょっと肝が冷えた。
1回目のソートは多分いらんのだろうけどそこ以外で早くなるのかなぁ。
itemgetter使ってみたけどlambdaと時間あまり変わらない。

Submission #6071150 - AtCoder Beginner Contest 131

n = int(input())

abn = [list(map(int,input().split())) for _ in range(n)]


#abn.sort()#これは本当はいらない
abn.sort(key = lambda x:x[1])


#print(abn)

ts = 0 # time_stamp
enable = True
for abi in abn:
    a, b = abi

    if not ts + a <= b:
        enable = False
        break
    else:
        ts += a

print('Yes' if enable else 'No')

E - Friendships

Eにしては簡単な気がする。
要求する前提知識がとても少ないので取り組みやすい。
問題文が何を言いたいのか理解するまで少しかかった。
手元の紙にいろいろ書いて試すのに時間がかかってコンテスト中に提出はできなかったのは残念だけど解けたのはうれしい。
AC 23:16:35なのでCをもっと早く実装できてたら行けたかもしれないのかなぁ…。

n = 2 k = 0 => 1-2  
n = 2 k > 0 => -1  

n = 3 k = 0 => 三角形  
n = 3 k = 1 => 1-2-3  
n = 3 k > 1 => -1

n = 4 k = 0 => 四角形+ ×  
n = 4 k = 1 => 四角形+ /  
n = 4 k = 2 => 四角形  
n = 4 k = 3 => 1-2; 2-3; 2-4  (NH3：アンモニアみたいな)
n = 4 k > 3 => -1  

n = 5 k = 0 => 五角形 + 星
n = 5 k = 1 => 五角形 + 星 - /
...
n = 5 k = 4 => 五角形 + /
n = 5 k = 5 => 五角形     
n = 5 k = 6 => 1-2; 2-3; 2-4; 2-5 (CH4 : メタンとか？)
n = 5 k > 6 => -1

ここまで試した。 n k => できるgraph;という感じで見てほしい。
できるグラフがわかればその辺の数Mもわかるはず。

kの上限 : (n-1) * (n-2)/ 2 で表せそう。
できるグラフの辺の本数M : n * (n - 1) / 2 - k で表せそう。

kが上限を超えたら-1
kがちょうど上限ならグラフはstar（星、ウニともいうらしい; すべての辺がある1つの頂点から出ている）
kが上限未満なら完全グラフからk本の辺を引いたもの
(完全グラフ : すべての頂点間に辺がある)
(除いていく辺は図形の輪郭以外のもの; 図形の内側にある辺に限る)

#include<vector>
#include<iostream>
#include<cstddef>

using si = std::int32_t;
si main(){

    si n, k;
    std::cin >> n >> k;

    si max_ = ( n - 1 ) * ( n - 2 ) / 2;
    if( max_ < k )
    {
        std::cout << -1 << "\n";
        return 0;
    }
    
    /*
   if( n == 3 && k == 1)
   {
       std::cout
           << 2 << "\n"
           << 1 << " " << 2 << "\n"
           << 2 << " " << 3 << "\n";
       return 0;
   }*/

    std::cout << n*(n-1)/2 - k << "\n";
    if( k == max_ )
        for( si i{ 1 }; i < n; ++i )
            std::cout << 1 << " " << i + 1 << "\n";
    else

        for( si i{}; i<n; ++i )
            for( si j{}; j < i; ++j )
            {
　　　　　　　　　　　　　　//条件文; 図形の内側にある辺なら
                if( k > 0 && (i - j != 1 || i-j != n-1) )
                    --k;
                else
                    std::cout << i + 1 << " " << j + 1 << "\n";
            }

    return 0;
}

2019-06-10

ABC129

atcoder.jp

久々にかく。ちなみに少し前から形式が変わって問題が6問になっている。
寝起きとはいえCで3ペナはだめ。
やっぱり少し準備しないとしっかり考えてから書くということがまだできないらしい。夜遅いのでとりあえずBまで。 C-Dは気が向いたら。

A: Submission #5838156 - AtCoder Beginner Contest 129 簡単に言えば経路を2つ選んでそのコストの最小の和はいくつでしょう、になるんだろうか。

いろんな書き方があるだろうけど、とりあえず足してみてその中から最小を選ぶやり方。

a,b,c = map(int,input().split())

ans = min(a+b,b+c,c+a)
print(ans)

B: Submission #5843918 - AtCoder Beginner Contest 129
制約が緩いので愚直に2重ループでも通るはず。
でも工夫すれば1回のループ(入力受付を除く)だけで解ける。
今回のコードだとsumで1回余分に回っているけどそんなに影響はないはず。

考え方は今まで見てきた範囲の和(変数 l )とまだ見ていない範囲の和(変数 r )を使う。ループを進めるたびに比較して差の最小値を出していく。 Wiに負数、0はないのでループが進むにつれてlは単調増加、rは単調減少するのでdisがこれ以上小さくならないとわかったらbreakしても良い(してないけど)。

こういうやり方はより難しい問題で当たり前に要求されるのでこういうところで練習を兼ねたい。寝起きでぼんやりしていて勘で書いてしまってひどく時間がかかった。

n = int(input())
wn = list(map(int, input().split() ) )


r = sum(wn)
l = 0
dis = r
index_ = 0
for i in range(len(wn)):
    r -= wn[i]
    l += wn[i]
    t = abs(r-l)
    if t < dis:
        dis = t
        index_ = i
#        print(l,r,dis)

print(dis)

Submission #5852752 - AtCoder Beginner Contest 129

300点にしては難しいけど400点もらえるかというと微妙な気もするのでやっぱり300点なのか…。

階段がN段のとき、移動方法は何通りあるのかをN=0から考えてみる。ちょっと面倒なのでテキストベースで書く。 (1<=N<=10⁵なので0はなくてもいい) ()内の.は1段,-は2段移動を示す。 0 => 1 (ない) 1 => 1 ( . ) 2 => 2 ( .. | - ) 3 => 3 ( ... | .- | -. ) 4 => 5 ( .... | ..- | .-. | -.. | -- ) 5 => 8 ( ..... | -... | ...- | -.- | ..-. | --. | .-.. | .-- )

このあたりからフィボナッチ数列らしいことがわかるし、手で書いて生成するのが面倒になってくる。ここでN段の結果はN-1段の結果から生成できそうと考える。フィボナッチなら当然できるだろう。 N-1の移動パターンの先頭に.を追加して、戦闘が..になった場合は..と-の2通りがある。そうでないならそのまま1通り。
つまりはN-1段のパターンで先頭に.があるなら+2、そうでないなら+1するとN段目のパターン数になる。 (2→3のとき　3=12+1; 3→4のとき 5 = 22+1; 4→5のとき 8 = 3*2+2 )

漸化式で表される数字を答えの算出に使えそうだが、何度も大きな値を計算すると計算コストが大きくなるだろう。ということでDPというかメモ化というか、フィボナッチをテーブルに記録しておく。ここでfib[x]としたときにx番目のフィボナッチ数が返ってくるようにするとわかりやすいと思う。

これでAmを除いた範囲をfibのindexにしてやると答えは出る。ただし、最後はn自身も含める必要があるので+1する。多分もっとスマートに書けるはず。

「移動方法は何通りなのか？」という問題なので、通れないところの前後の移動方法は乗算する。掛け算なのでそのたびにmodで割って構わないはず。

n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True


if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+10)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)

2019-06-01

Compositeパターンを書いてみた

まだまだ設計やデザインパターン、それらに使う継承などに弱いと思う。今回はcompositeパターン？を書いてみた。（ずっとcomponentパターンだと思ってたけど違う？） MVCが自力で書けるようになりたいね。

ファイルなどの階層構造をクラスの階層構造で表現する。
検索で出てくるコードには、個人的には「アンチパターンじゃないのか？」という書き方があったりして、納得がいかなかったので書いてみた。時間はかかったが、個人的には木構造や双方向リストのようなものが作れるわりにはnull pointerのエラーが少なくて済むように思う。コンテナ使っているのも大きい。どちらかというとコードも追いやすいかもしれない。

楽しくなってdirectoryの関数を増やしすぎてしまったので、すでにサンプルには向かない気がしているけれど折角書いたので。

共通項については親/基底である抽象クラス/インターフェイスが持つのは問題ない。まとめて基底型として管理して、ある時には任意の派生型のみを取り扱いたい、なんてことがきっとあるだろうけど、どうやるのが良い方法なのかよくわからない。とりあえずざっくり2通りだろう。

派生型が持つメソッドはすべて基底型も持つ
基底型が持つのは最低限の共通部分だけで、派生型それぞれが必要な分だけメソッドを持つ
基底型とすべての派生型が同じメソッドのみを持つ

(1. )は良くないだろう。基底型はすべての派生型を抽象的に表現したものだろうから、どちらかというと派生型を基底型の枠にはめ込むほうが良いはずだ。だから(2.)が望ましいと思う。(3.)は継承を使わずに、すべて同じ型で良いだろう。 (2.)をベースになるべくシンプルに(1.)から遠ざけて、(3.)に近づけるつもりで考えればいいのか。。。？

基底型は派生型がどういうものかは知らないが、基底型自身がうまく定義されている限りは派生型であればそれなりにどれでも、うまく取り扱うことができるはずだ。そう期待していいはずだ。

しかし、例えば今回のコードでは基底クラスがis_dirとis_fileの 2つの関数を持っている。これはある意味、基底が派生型を知っていることになってしまうのできっと良くないやり方だ。（もし第3の派生型が生まれたら、基底クラスを書き換える必要が出るんじゃないか？）一方で、componentから派生した型であればそれが何かを調べることができる、というのもある意味では共通した性質に思えるので、どうにか比較する方法が基底型からサポートされていても良さそうな気がする。ただ、錯覚というか、これは間違っている気がする。
　基底型からするとどんな派生型も基底型と同一であって区別するとかしないとかそういう話じゃない、という考え方をしたほうがいいのだろうか。 show関数は仮想関数にして派生型ごとに書き換えるのにベストな関数なんだろうなぁとは思う。 Java、C#のToString、pythonのstrに近いものだろうし、型によって中に持っているデータの量や種類、重要度は異なるだろうから。

　もともと古いパターンの1つであって、今なお素晴らしいといえるものかどうかは分からないので、そもそもこのデザインパターンが良いのかはわからない気がしてきた。継承無しでdirectoryの再帰+directoryがfile(再帰しない要素)の配列を持つような実装なら継承いらないんだよなぁ・・・

やはり継承はうまく使うのが難しい。

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

//main.cpp

#include<string>
#include<iostream>
#include<list>
#include<memory>
#include<queue>
#include<map>
//#include<optional>

class directory;
class file;

class component
{
    std::string name_;
    int depth_ = 0;
    const component* parent_ptr;

protected:
    auto& parent(const component* new_ptr ){
        parent_ptr = new_ptr;
        return *this;
    }
    auto& depth( int new_depth ){
        depth_ = new_depth;
        return *this;
    }

public:
    component( const std::string&name_v ,int depth_v,const component*parent_ptr_v = nullptr)
        :name_{ name_v }
        , depth_{ depth_v}
        , parent_ptr{parent_ptr_v}
    {}
    
    auto depth()const{ return depth_; }
    auto parent()const{ return parent_ptr; }

    auto& rename( const std::string& new_name_ ){
        name_ = new_name_; return *this;
    }

    auto name()const{ return name_; }
    
    virtual auto is_file()const->bool = 0;
    auto is_dir()const->bool{ return !this->is_file(); }




    auto show()const->void{
        std::cout
            << ( parent() == nullptr ? "None" :parent()->name() ) << "\t"
            << name() << "\t"
            << depth() << "\t"
            << (is_dir() ? "Dir" : "File" )
            << "\n";
    }

    auto show_format()const{
        std::cout << "parent" << "\t" << "name" << "\t" << "depth" << "\t" << "dir/file\n";
    }

    virtual ~component() = default;
};


class file final :public component
{
    using super = component;
    std::string file_type_;
    public:
    file( const std::string& name_, int depth_v
          , const component* parent_ptr_v, const std::string& file_type_v )
        :super{ name_,depth_v,parent_ptr_v }, file_type_{ file_type_v }
    {}

    auto is_file()const->bool override{ return true; }
};





class directory final:public component
{
    using super = component;
    std::map<std::string,std::unique_ptr<component>> children;

protected:

    template<class T, class ...Args>
    auto& add( const std::string&name, Args&&...args ){
        auto t
            = std::make_unique<T>(
                name
                , depth()+1
                ,static_cast<const directory*>(this)
                ,std::forward<Args>( args )... 
            );

        children.emplace(name, std::move(t) );
        return *this;
    }


public:
    directory( const std::string& name_, int depth_v,const component*parent_ptr_v = nullptr )
        :super{ name_,depth_v,parent_ptr_v }
    {}
    
    auto size()const{ return children.size(); }

    /*
   auto& add( const component& comp ){
       children.emplace_back( comp );
       return *this;
   }*/
    auto is_file()const->bool{ return false; }


    auto& add_file( const std::string& name_, const std::string& file_type_){
        return 
            add<file>( name_, file_type_ );
    }

    auto& add_dir(const std::string& name_ ){
        return
            add<directory>( name_);
    }

    auto& as_map()&{
        return this->children;
    }

    auto& as_map()const&{
        return this->children;
    }

    template<class F>
    auto as_map_if( F&&f )const&{
        std::map<std::string, component*> t;
        for( const auto&e : children )
        {
            if( f(*e.second) )
                t[e.first] =  e.second.get() ;
        }
        return t;
    }

    auto files()const&{
        auto&&t = as_map_if( []( auto&x ) { return x.is_file(); } );
        std::map<std::string, file*> ret;
        
        for( auto&&e : t )
            ret[e.first] = std::move( dynamic_cast<file*>( e.second ) );
        
        return ret;
    }

    auto dirs()const&{
        auto&& t = as_map_if( []( auto&x ) { return x.is_dir(); } );

        std::map<std::string, directory*> ret;
        for( auto&&e : t )
            ret[e.first] = std::move( dynamic_cast<directory*>( e.second ) );
        
        return ret;

    }



    /*
   after C++ 17
   auto find( const std::string& name )const{

       auto it = children.find( name )
           ;
       return      
           it != std::end( children )
               ? std::make_optional( *it )
               : std::nullopt;
   }
   */

    auto find( const std::string& name )const{

        auto it = children.find( name )    ;

        return
            it != std::end( children )
            ? it->second.get() : nullptr;
    }

    auto find_dir( const std::string& name )const{
        auto ptr = find( name );
        return 
            ptr != nullptr && ptr->is_dir()
                ? static_cast<directory*>(ptr)
                : nullptr ;
    }


    auto find_file( const std::string& name )const{
        auto ptr = find( name );
        return
            ptr != nullptr && ptr->is_dir()
            ? static_cast<file*>( ptr )
            : nullptr;
    }

    auto& print_bfs()const{

        std::cout << "___BFS___\n";
        show_format();
        
        std::queue<const component*> que;
        que.emplace(this);

        while( !que.empty() )
        {
//         std::cout <<"DEBUG:"<< que.size() << "\n";
            auto&&here = que.front(); que.pop();
            here->show();
            
            if( here->is_dir() )
            {
                auto&& mp = dynamic_cast<const directory*>( here )->as_map();
                for( auto&child : mp )
                    que.emplace(
                        child.second.get()
                    );
            }
        }
        std::cout << "___BFS___\n";
        return *this;
    }

    auto& print_dfs()const{
        std::cout << "___DFS___\n";
        auto& p = print_dfs_impl();
        std::cout << "___DFS___\n";
        return p;
    }

    template<class F>
    auto map_dfs( F&&f )->void{

        f( this );

        for( auto&e : this->children )
        {
            auto ptr = e.second.get();
            
            if( ptr->is_dir() )
                dynamic_cast<directory*>( ptr )->map_dfs( f );
            else
                f( ptr );
        }
    }

private:
    auto print_dfs_impl()const->const directory&{

        this->show();

        for(const auto&child :this->children )
        {
            //child.second->show();
            if( child.second->is_dir() )
                static_cast<directory*>( child.second.get() )->print_dfs_impl();
            else
                child.second->show();
        }
        return *this;
    }

};


auto check( component* cp){
    std::cout << "component : " << cp->name()<<"\n";
}

auto check( directory* dp ){
    std::cout << "directory : " << dp->name()<<"\n";
}

auto check( file* fp ){
    std::cout << "file : " << fp->name() << "\n";
}

int main(){

    directory root{ "root",0 };

    root.add_dir( "user" ).add_dir("program");

// if( root.find_dir( "user" ) == nullptr )
//     std::cout << "none\n";

    root.find_dir( "user" )
        ->add_dir( "Alice" )
        .add_dir( "Bob" )
        .add_dir( "Cris" );

    root.find_dir( "program" )
        ->add_dir( "mine" )
        .add_dir( "text" );

    root
        .find_dir( "user" )
            ->find_dir( "Alice" )
                ->add_file( "diary","txt" )
                .add_file( "memento","image" );
    /*
   for( auto&&e : root.as_map() )
   {
       std::cout << e.first << " ";
       e.second->show();// << "\n";
   }
   */
    root.print_bfs();
    std::cout << "\n";
    root.print_dfs();
    std::cout << "\n";

    root.map_dfs( []( auto&&x ) { check( x ); } );
    
    return 0;
}

//console.log
___BFS___
parent  name    depth   dir/file
None    root    0       Dir
root    program 1       Dir
root    user    1       Dir
program mine    2       Dir
program text    2       Dir
user    Alice   2       Dir
user    Bob     2       Dir
user    Cris    2       Dir
Alice   diary   3       File
Alice   memento 3       File
___BFS___

___DFS___
None    root    0       Dir
root    program 1       Dir
program mine    2       Dir
program text    2       Dir
root    user    1       Dir
user    Alice   2       Dir
Alice   diary   3       File
Alice   memento 3       File
user    Bob     2       Dir
user    Cris    2       Dir
___DFS___

directory : root
directory : program
directory : mine
directory : text
directory : user
directory : Alice
component : diary
component : memento
directory : Bob
directory : Cris