お前がすめけになるんだよぉ！！

問誰がすめけをそだてますか？
答誰かが育てるのではありません．あなた方一人一人がすめけなのです．

すぬけ育てコンテストをやったので記事書きました．

目次
ところで
A問題
B問題
C問題 (力入れて書きました)
D問題 (ここからまだ解いてないです)
E問題

By the way, who is the girl beside you? ーーところでーー

C++のソートは，比較関数を自分で定義することが出来ますね．

bool mysort(引数1, 引数2){
    //どうやって書くんでしょうね 
}
vector<int> a(114514);
for(int i = 0; i < 114514; i++) cin >> a[i];
sort(a.begin(), a.end(), mysort);

どうやって書くか知っていますか?
ここは，引数1がソート後の配列で前に来るならtrue,引数1がソート後の配列で後ろに来るならfalseを返すように書きます．
引数はintでもpair型でも多分何でもいいと思う.
pair型で，second要素の降順でソートしたいなら?

たとえば，(2,5) (1,4)を比較したときには，(2,5)が前に来るようにしたいです．簡単化のために，second要素は同じ値が来ないとしておきますか．

次のように書きます.

bool mysort(pair<int,int> x, pair<int,int> y){
    bool ret;
    if(x.second > y.second){
        // 第一引数のほうが出けえなら，ソート後，第一引数が配列の前に来る．
        ret = true;
    } else {
        ret = false;
    }
    return ret;
}

こんな感じで書けます．でもまあ，ほとんどのサイトだと，次のように書かれてるよね

bool mysort(pair<int,int> x, pair<int,int> y){
    return x.second > y.second;
}

ちょっと，自分でソート用の比較式定義出来ないから，雑に調べて使えるようにしてみたってだけ．

pairの第二要素(second)で降順にソートするコート全体はこんな感じ．
今回は分かりやすいかなあって思って行数多い方で書いときました.

#include <bits/stdc++.h>
using namespace std;
bool mysort(pair<int,int> x, pair<int,int> y){
    bool ret;
    if(x.second > y.second){
        // 第一引数のほうが出けえなら，ソート後，第一引数が配列の前に来る．
        ret = true;
    } else {
        ret = false;
    }
    return ret;
}
int main(){
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    for(int i=0; i<n; i++) cin >> a[i].first >> a[i].second;
    sort(a.begin(),a.end(), mysort);
    for(int i=0; i<n; i++) printf("(%d, %d)\n", a[i].first, a[i].second);
}

入力

5
2 5
1 4
3 3
8 9
9 7

実行結果
(8, 9)
(9, 7)
(2, 5)
(1, 4)
(3, 3)

ちなみに，第二要素は降順（今のまま）で，第二要素が同じだったら第一要素は昇順にしたいよ～とかってときはmysortでtrueを返すときの条件を書いちゃえばいいと思う．

if(x.second == y.second){
    if(x.first < y.first) ret = true;
}

みたいな感じにすればいいんじゃないかな.

bool mysort(pair<int,int> x, pair<int,int> y){
    bool ret;
    if(x.second > y.second){
        // 第一引数のほうが出けえなら，ソート後，第一引数が配列の前に来る．
        ret = true;
    } else {
        ret = false;
    }
    if(x.second == y.second){
        if(x.first < y.first) ret = true;
    }
    return ret;
}

あ，main関数の中はさっきと一緒ね．
第二要素は降順，第一要素は昇順，できたね．

入力

5
1 4
3 4
8 4
5 7
6 7

実行結果
(5, 7)
(6, 7)
(1, 4)
(3, 4)
(8, 4)

今日から君もすめけ

なろう．なれるよ．君なら．

COLOCON -Colopl programming contest 2018- A- すぬけそだて――登録――

$$ \begin{align} &文字列sのサイズをnとして\ & a \leq n \leq bであれば，YESを出力 \end{align} $$

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    int n = s.size();
    if((a <= n) & (n<=b)) puts("YES");
    else puts("NO");
}

my code

COLOCON -Colopl programming contest 2018- B- すぬけそだてーーチュートリアルーー

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, x;
    cin >> n >> x;
    string s;
    cin >> s;
    int ans = 0;
    for(int i=0; i<n; i++){
        int sec; cin >> sec;
        if(s[i]=='1'){
            ans += min(x,sec);
        } else {
            ans += sec;
        }
    }
    cout << ans << endl;
}

my code

これなんか短くできないかな

短くならなかったけど行数減らしてみた．

int sec; cin >> sec;int now = (!(s[i]-'0')) * sec + (s[i]-'0') * x;ans += min(now,sec);

nowは，s[i]が0のときに，はt[i]を使う． s[i]が1のときは，t[i]とxのうち，短い方を使う． s[i]-'0'は，s[i]が1のとき1になります．
まぁなんか，nowは+の左側か右側どちらかは絶対0になるようにしたよ．ってだけです…

COLOCON -Colopl programming contest 2018- C- すぬけそだてーーごはんーー

[嬉しい,素数の個数,全探索,bitDP,UnionFindではない]

記事を書き始めて一日後，AC
解説読んでも「あー書ける気しないな」って思って写経する気満々だったのですが，なんとかやる気を振り絞って書いたらＡＣしました．解説は読んでしまったが通しました．しかし解説読んでも書ける気しなかったものを通したので実質自力ＡＣといってもいいでしょう．

UnionFindでは解けない

これは非正解に通じる話なんですけど，UnionFindでは解けませんでした．

まず，そもそもの話として，AやBが10の18乗に近いときに，10の18乗の付近の数x(1'000'000'000'000'000'531)とかっていうクソでか数について2で割り切れるかな3で割り切れるかな，5で...,114514191918103で割り切れるかな…とかっていうのを見ていくのは流石に計算量がやばいです(キメツのﾔﾊﾞｲ)

とりあえず，AとBの差が35以下とのことで，A <= x,y <= Bであるような2つの値x,yが互いに素ではないとき，どちらもkという値で割り切れるとします．
その時のkは2以上35以下です(1は忘れて！).

正確には,2以上B-A以下です．

A=35,B=70のとき，x,y=35,70だとしたら，まぁ35で割り切れますよね．
でも，36以上で割り切れるようなx,yの組は見つけられますか?見つけられないです．なぜなら，A + 35 >= Bという制約があるから，x+36=yの関係を満たすx,yは存在しません．

別の言い方をすると，35個(36個でもいいよ)の連続した整数について，36で割った余りは，全て異なります．

例えば，50,51,...,71,72,73,....,84(35個の連続した整数)を36で割った余りは, 14,15,...,35,0,1,...,12 という風に全て異なります．

この，A以上B以下の数x,yが互いに素ではないとき，x,yを互いに割り切る数kは35以下(B-A以下)という性質を用いることで，AやBがクソでかいときにも扱えるようにします．

で，ここからどうしてUnionFindで解けそうな気がしたかというと，

互いに素でない整数同士をUnionしていって…みたいな感じでUnionFindすることで，答えが「それぞれのグループから整数を，取らない・取る（取るならどの1個を取るか）で各グループにつき存在する整数の個数+1の選択肢があるから，グループごとにその数を掛ければいいんじゃないかって思いました．
例えば，5,6,7,8,9のときは{5}{6,8,9}{7}という3つのグループに分かれるので，(1+1) * (3 + 1) * (1 + 1) = 16通りです．はい，もうこの時点でサンプルと違いますね．
このやり方の問題点は，8と9が一緒のグループにいることです．
8と9は互いに素であるのに，6と8が互いに素ではなく，6と9が互いに素でないため，⑥を媒介として8と９が繋がってしまいました．これでは正しい解答が得られません

次の解法として，2で割り切れる数のグループ・3で割り切れる数のグループ・５で割り切れる数のグループ…(4で割り切れるグループは2で割り切れるグループに入ってる)みたいな感じで分ける方法です

g(i) := iで割り切れる数のグループとして説明を続けます

先ほどのように5,6,7,8,9のときは，g(2) = {6,8}, g(3) = {6,9},こうなります

すると，同じグループでないもの整数は取っていいのかな，って思いますが，6は二つのグループに入ってるから扱いめんどくさそうだし，8を取ったときg(3)で6とっちゃいけないよ，みたいなこともどうやって実現するねん．って感じで無理だな～ってなります．

そんなこんなで，グループ分け戦術は無理そうだ，俺にはできない．となりました．

ある範囲の素数の個数

こっからが正解につながる思考です．多分．知らんけど

とりあえずここまでで「A以上B以下の数について，互いに素でないとき，割り切る数は2から最大でも35以下」ということについて話したつもりです

ここで，二つの数x,yがともに35で割り切れるとき，それは「５で割り切れる」「７で割り切れる」とも言えます．そのため，x,yが35で割り切れるかというのは実は見なくてもいいことが分かります.

数学っぽく言うと？，二つの数x,yが35を公約数にもつとき，35の約数(5や7のこと)もx,yの公約数である．(出典:nibopedia <-架空のサイトです)

つまり何が言いたいかというと，「割り切る数」としてみなければいけない数字は「2以上35以下の素数」だけである．ということが言いたいです．

2以上35以下の素数の数は,12個ぐらいです．多分．実際どうですかね?

2, 3, 5, 7, 11, || 13, 17, 19, 23, 29, ||31, で11個ですね．5個おきに線を二つ入れときました.

ちなみに12個ぐらいかなあといったのは，35以下で2で割り切れる数が35/2 = 17個，35以下で3で割り切れる数が35/3 = 12ぐらい個

35以下で6で割り切れる数が35/6 = 6ぐらい個

2で割り切れる数は素数じゃないから，2～35までの35個から17を引いて素数候補は残り18個

更に，3で割り切れる数も素数じゃないから，素数候補の残り18から12を引いて素数候補は残り6個

ここであらあら，2で割り切れる数と3で割り切れる数を素数候補から除いてしまったが，良く考えたら6とか12みたいに，2でも3でも割り切れる数がそれぞれ2回ずつ引かれているじゃん．ということに気づきます．そこで，素数候補の残りの数に6で割り切れる数の6個を足して6+6=12個．こんなノリで，大体12個かなあ，というのを0.2sで頭の中で計算しました．

はい．まぁ，11個の素数がx,yをともに割り切る数の候補であることが分かりました．

bitDP

割り切る素数の数が11個，AからＢまでの数字が最大36個,なんだか全探索できそうな匂いがプンプンするな…

ここで僕は力尽きて解説を読みました.

bitDPを考えます．良く分からないのでとりあえずDPの表を書いてみます．

dp [i] [j] の中身は，i,jであるような状態のときの，整数の選び方が何通りか(わけわかんないよね)

とりあえず dp [i] [j] のiは，A+iまでの数字を見たとき．でいい気がします．(実は違くて，A+i-1までの数字を見たときですが，これは表を書くことで気づきましたが，今はまだ気づいていないていで話を進めます．)そうすることでiは0から35までを多分動きます.

jは，AからA+iまでの数字を取る・取らないの選択をしてきたときに，どのような素数で割り切れるかを管理する整数です．2進数的に？扱います．

まず，割り切る素数の配列を prime = {2,3,5,...,31} って感じに持っておきます．

(僕は，2から31までの素数ではなく，2からB-A以下のみの素数だけを持ったので，そっちで話をします．)

j = 2 のとき，2進数としてみると(10)です．dp [i] [2]は，A+i までの数について，取る・取らないを選択したときに，その中には3(prime配列の1番目(0-indexed)の要素)で割り切る数字のみがある．という状態を表します．例えば，A= 5, B = 9のとき，prime [] = {2,3}です．
このときに，状態jが2，となるっていうのは，選んだ選択肢が3で割り切れるもの(と，primeにない数字でしか割り切れないやつ，例えば5,7)だけであり，3で割り切れる数字が2つ以上入っていない状態を示します．
ちょっと分かりずらいですよね，
例えば，選び方，{9} {5,9} {7,9} {5,7,9}，この4通りの選び方はj=2のような状態でありますが，{6},{5,6},{6,9}などの選び方はj=2のような状態ではありません．

{6}を選んだとき，選んだ整数は，2と3で割り切れるため，このような状態はj=3(2進数で11)で管理されます．

{5,6}を選んだ時も同じで，選んだ整数は２と３で割り切れるため，このような状態はj=3で管理されます．(ちなみに，5でも割り切れる5が入っていますが，primeに5は入っていないので興味の範囲外です．社会から見た俺ですね．)

{6,9}は，そもそも選べない組み合わせです． 6と9はどちらも３で割り切れるため，同時に選べません．すぬけ君が悲しんでしまいます．（ﾆｬｰ)

ちょっとずつ感覚がつかめてきたかな？

状態ｊが2進数でx1,x0みたいになってる(上のj=2の例は，x1=1,x0=0だよ)とき，すぬけが食う飯は(xi == 1のとき) prime[xi]で割り切れる整数を含んでいる．みたいな感じ．

いろんな言い方をしすぎて逆にこんがらがっちゃうかな?

はい，そんな感じで，表を書いてみるよ．A=5,B=9ね．

f:id:niboshi_bisyoujo:20210811153515j:plain

表書いてみた．とりあえず，dp [0] [00]が1になって欲しいから，dp[0] [00] を1 にしたよ．
右の余白は表がでかすぎただけだから気にしないで

あと，dp[0] [00]にして気づいたんだけど，dp [i] [j] は，a+iまでを取るかとらないときに…じゃなくて，i個の数字を見たとき…にしたほうが都合がいいね

だから，5,6,7,8,9の5個の数字を見なきゃいけないから，iは0から5の6個があるよ．
さて,dp[0] [00] からの遷移を考えよう．

dp [0] [XX]からの遷移では，5 を取るか取らないかで考えるよ．

取らない場合

すぬけ君が食べる飯に影響はないので，jは変わらないね．だから，dp[1] [00]にはdp[0] [00]が足せるね．

取る場合

5を取るってことは，食べる飯が増えるから，，それ以降のカードが取れるか取れないかに影響するね．(10や15が取れなくなる！！(今回の例ではB=9だから気にしなくていい))
でも5はprime = {2,3} に入っていないから，どうでもいいね．

ということで，5を取ったとしてもjは00のまま．ということで dp[1] [00] には dp [0] [00] をもう一度足せるね．

ということで，取らない場合(1)と取る場合(1)を足し合わせてdp [1] [00] = 2通り．

(表で，X 矢印は，5を取らないときの遷移， o 矢印は5を取るときの遷移を意味するよ，あと，次の表は，iの横に，取るか取らないか見る対象の数字を書いておくよ．)

f:id:niboshi_bisyoujo:20210811153517j:plain

さて，dp[0] [01], dp[0] [10] , dp[0] [11] からの遷移も考えようと思ったが，このときの値はいずれも0なので，考慮しなくていいね．ってことで0を入れるよ．

f:id:niboshi_bisyoujo:20210811153519j:plain

次，dp[1]からの遷移を考えよう．

dp[1] [00] からの遷移

ここでは，6を取るか，取らないかを考えるよ．
- 6を取らない場合
  
  5を取らないときと一緒で，jに変化はない．よって，dp[2] [00] に2を加えます．
  
  2というのはdp[1] [00] の値です．
  
  ここでいったん補足しますが，表では分かりやすさのためjの値を二進数で書いていますが，実際のプログラムではj = 0, 1 , 2, 3って書いていますよ．(書いてないかも)
- 6を取る場合
  
  6を取ると，すぬけが食べるものは2，3で割り切るものが含まれることになります．
  
  そのため，これ以上2や3で割り切れるものを食べてはいけないので，j=3 (2進数で11)へ遷移しなければいけません．
  
  j = 1, 2(01と10)への遷移はありません．なぜなら，6を食べたときにj=1 (01)への遷移をしてしまったら，3で割り切る数を食べたという情報が抜け落ちてしまうからです．
  
  ということで，dp[2] [11] へ dp[1] [00] の値である2を足します．
dp[1] [01], dp[1] [10], dp[1,11]からの遷移

dp[0] [01], ... ,dp[0] [11]と一緒で，値が0だから無視～～

ちなみに，プログラムでは意図的にcontinueとかしなくてもちゃんと動くよ．

dp[1]からの遷移を反映した表が次です．

f:id:niboshi_bisyoujo:20210811153529j:plain

よしよし，だいぶ表が育ってきたぞ．

次はdp[2]からの遷移を考えよう．

dp[2] [00] からの遷移
- 7を取らないとき
  
  食べたものの集合に変化はないので当然jも変化しない．
  
  dp[3] [00] += dp[2] [00]
- 7を取るとき
  
  食べたものの集合に変化あり．
  でも，7はprimeに入っていないのでjに変化無し．
  
  dp[3] [00] += dp[2] [00]
  
  primeに入っていないということは，7で割り切る数がA,Bには1つ未満しかないということを意味していると思うよ．
  
  dp[2] [00] からの遷移で一回表を更新しようと思ったけど，やっぱやめた．
dp[2] [01] ，dp [2] [10]からの遷移

値が0なので無視～～
dp[2] [11] からの遷移
- 7を取らないとき
  
  食べたものの集合に変化はないので当然jも変化しない．
  
  dp[3] [11] += dp[2] [11]
- 7を取るとき
  
  食べたものの集合に変化あり．
  でも，7はprimeに入っていないのでjに変化無し．
  
  dp[3] [11] += dp[2] [11]

よし，dp[2]からの遷移を書いたところで表を更新．

f:id:niboshi_bisyoujo:20210811153531j:plain

次，dp[3]からの遷移．（飽きてきたけど，このあたりからちょっと複雑そうに見えるかもしれないし…頑張るか)

dp[3] [00] からの遷移
- 8を取らない
  
  状態jに変化は無し.dp[4] [00] += dp[3] [00]
- 8を取る
  
  8は2で割り切れる． 2はprime[0]なので，2進で01への遷移になる．
  
  dp[4] [01] += dp[3] [00]
dp[3] [01] ，dp[3] [10]からの遷移

いままで同様無視
dp[3] [11] からの遷移
- 8を取らない
  
  状態に変化なし． dp[4] [11] += dp[3] [11]
- 8を取る
  
  正気か？お前
  
  状態j = 3 (11)は，すでに2で割り切れる数と3で割り切れる数を食っていることを意味している．
  だから，２で割り切れる数である8を食うことは出来ない．
  よってdp[3] [11] で8を取る選択肢は取ることが出来ない．
  
  はい，反映

f:id:niboshi_bisyoujo:20210811153846j:plain

ここまで来たらもう最後まで書いても変わらん.
dp[4] からの遷移

dp[4] [00] からの遷移
- 9を取らない
  
  状態に変化なしなので略
- 9を取る
  
  状態に変化あり．3で割り切れるようになる．
  
  3はprime[1]なのでjの1bit目？(0indexed?)を建てて，2進で10への遷移．
  
  dp[5] [10] += dp[4] [00]
dp[4] [01] からの遷移
- 9を取らない
  
  状態変化なし略
- 9を取る
  
  状態に変化あり．3で割り切れるようになる．
  
  3はprime[1]なのでjの1bit目？(0indexed?)を建てて，2進で10への遷移．…
  ではなくて，今現在dp[4] [01]では，2で割り切れる数を食っているので，2と3で割り切れる数を食ったことを示すj=3 (11)への遷移
  
  dp[5] [11] += dp[4] [01]
dp[4] [10] からの遷移

0やし無視
dp[4] [11] からの遷移
- 9を取らない
  
  状態変化なし略
- 9を取る
  
  取れない．
  なんで？って，dp [4] [11] は，もう3で割り切れる数を食っているから．
  
  ってことで遷移無し

f:id:niboshi_bisyoujo:20210811153533j:plain

 表完成！！

 出力する答えは，dp[5]の合計値です．これは，5個の数字，つまりB==9までの数字を見たときに，すぬけ君が悲しまないようにカードを食ったときの状態の数ということですね．

後はコードを書くやで

先にコード見せておくね．遷移先としてbitをいじいじした提出AC, 遷移先を求めるときにbitをいじいじしてない(したけど)提出AC

  ll dp[40][1<<11];
  int main()
  {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    ll n = b - a + 1; // a ~ bの数字はb-a+1個
    //2~n-1の素数を管理すれば良い．
    vector<int> prime(0);
    for(int i = 2; i < n; i++){
        bool p = true;
        for(int j = 2; j * j <= i; j++){
            if(i%j == 0) p = false;
        }
        if(p) prime.push_back(i);
    }
    int psz = prime.size();
    // dp[i][j] := a+i-1まで見たときに，bitがjであるような組み合わせが何通りあるか．
    dp[0][0] = 1;
    rep(i,n){
        // dp[i][j]からdp[i][nbit]の遷移を作成する
        ll num = a + i;
        rep(j,1<<psz){
            // 先ず，numを取らないことでdp[i+1][j]への遷移が可能
            dp[i+1][j] += dp[i][j];
            bool flag = true;
            bitset<12> tmp(j);
            ll sum = 0;
            rep(k,psz){
                // num がprime[k]で割れるとき，tmpのkビットが立っていたら使えない．
                if(num % prime[k] == 0 && tmp.test(k)){
                    flag = false;
                    break;
                }
                //if(num % prime[k]) tmp.set(k);
                //if(num % prime[k])
                if(0 == num % prime[k]) sum += (1<<k);
            }
            if(flag){
                // num取るという選択肢が生れる
                dp[i+1][j|sum] += dp[i][j];
            }
        }
    }
    ll ans = 0;
    rep(i,(1<<psz)){
        ans += dp[n][i];
    }
    cout << ans << endl;
  }

これが全体図．読まなくても読んでもいいよ，読みたかったら読んでね．

とりあえず，dp[ i ] [ j ] のときを遷移元として遷移先を決めていく．ということをしていけばいいとわかったので

  for(int i = 0; i < B - A + 1; i++){ // i < 5 (=9-5+1)
    for(int j = 0; j < (1 << primeの素数の数)){
        // dp [i] [j] からの遷移を書く
    }
  }

この2重ループの中の処理を書いていけばいいね．

prime

とりあえず，primeが必要だから作ろうか．primeは，2からB-A以下の素数を入れたものだったね

     vector<int> prime(0);
    for(int i = 2; i < n; i++){
        bool p = true;
        for(int j = 2; j * j <= i; j++){
            if(i%j == 0) p = false;
        }
        if(p) prime.push_back(i);
    }
    int psz = prime.size();

まぁ，nはB-A+1を入れてあります．(A~Bの数の個数がn)

ここは単純に，iが素数かを判定して，素数ならprimeに突っ込む．という風にしてあります．
あとついでに，pszにprimeの要素の個数を持っておきます．

2重ループの中身

とりあえず，i のときに考える数字は，A + iです(これをnumとする)

で，dp [i] [j] の遷移表を作っていた時，numは取らないという選択肢を毎回取れたことから，numがどんな数字かを考えず，「numを取らない(食べない)」という選択ができます

    for(int i = 0; i < B - A + 1; i++){ // i < 5 (=9-5+1)
        int num = a + i;
        for(int j = 0; j < (1 << primeの素数の数)){
            // dp [i] [j] からの遷移を書く
            // num を取らない
            dp[i+1][j] += dp[i][j];
            // num を取ることを考える
        }
    }

次に，numを取ることを考えますが，ここでは取れない場合を考慮しなくてはいけませんね. numを取れない条件というのは，numがkで割り切れるとき，既に状態jが，kで割り切れる数を取っていることを表しているときです．

例えば，9を取ろうとしているときの状態 j = 2と3(二進数で10,11)が該当します．

つまり，jの1bit目(0-indexed)が立っているときに，9は取れません.
jのkビット目が立っているか判定するコードを書きたくなくて，bitsetを使いました．jのkビット目が立っているときは，tmp.test(k)がtrueになります（多分） bool flagは，numを取れるときがtrueです．

numがprime[k]で割り切れて，bit.test(k)がtrueのとき，prime[k]で割り切れる数をもうすでに食っているので，numは取れません．よってflagをfalseにします．（bit.test(k)は，numをまだとっていないときの状態jを見て，prime[k]で割り切れる数が含まれていることを意味する) このコードを書きます．

             bool flag = true;
                bitset<12> tmp(j);
                ll sum = 0;
                for(int k = 0;k < psz;k++){
                    // num がprime[k]で割れるとき，tmpのkビットが立っていたら使えない．
                    if(num % prime[k] == 0 && tmp.test(k)){
                        flag = false;
                        break;
                    }
                    if(0 == num % prime[k]) sum += (1<<k);
                }
                if(flag){
                    // num取るという選択肢が生れる
                    dp[i+1][j|sum] += dp[i][j];
                }

sum は，遷移先を求めるためのものです．

たとえば，状態j = 0 (00)で，ｎum=9 を取ったときの遷移は，j=2 (10)ですが，このときはsumに2の1乗(二進数で10)を足します． > > 最後に，jとsumのORを取ることで(00 or sum) = (00 or 10) = (10)への遷移が完成します．
> > 他の例ですと，j = 1 (01)からnum=9のとき，これはj=3への遷移ですが，これも sum = 2の1乗としておけば (j or sum) で(01 or 10) = (11)への遷移が出来ます．
> > num=６の例が分かりやすかったかな
> > j = 0 (00)で6を食うとき... > > 1. k = 0 のとき > > 6 % 2 == 0 で， sum += 2の0乗 > > 2. k = 1 のとき > > 6 % 3 == 0 で， sum += 2の１乗 > > 今，sum += 3. > > j or sum = 11．

これが出来りゃもう勝ちよ．<br>

DP表が完成したから

    ll ans = 0;
    for(int j = 0; j < (1<<psz); j++){
        ans += dp[n][j]; 
    }
    cout << ans << endl;

終わり！！長かった～～

COLOCON -Colopl programming contest 2018- D- すぬけそだてーートレーニングーー

COLOCON -Colopl programming contest 2018- E- すぬけそだてーーわっかーー

すぬけそだてーーそれからーー

あれから3年と8ヵ月（つまり，約869120秒）の月日が流れた．
つまり，今から3年と8か月前(つまり，約869120秒前)，すぬけそだてコンテストが開かれた．

草体にぼ日記

だらだらと

すぬけ育てーーごはんーーやるぞ