草体にぼ日記

だらだらと

2021年 1月 17日 bitDPれんしゅうちゅう

まえがき

こんにちは

2021年 1月 17日,解いた問題

BITDPを多めにときました(あはは)

ARC007 C-節約生活

  • [bitDP,集合を管理するDP] 問題の概要
    'oxoxooo'みたいなのを繰り返し使い,oとxが重なった部分はoにすることで,'ooooooo'にしたい.(ちょっとめんどくさい言い換え)
    つまり
    'oxoxooo'
    'ooxoxoo' (これは'oxoxooo'を1回だけ回転したもの(右シフト的なノリ?))(正しくは右回転シフトかな??)
この2つを重ねることで
    'oooooooo'になる

別に,回転する回数は1回だけじゃなくてもよくて,2回
    'oxoxooo'
    'ooooxox' (3回だけ回転したもの)

こんな感じ

bitDPで出来るだけ可読性高くなるように頑張って書いたよ.

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[(1<<10)];
int rotate(int x){            // この関数のやること 0001 を 右に1個ずつつらして 1000にする
    int y = x;
    x = x >> 1;              //0001を ?000にする(ちなみに?は0が入っているよ)
    x = (x>>1) + (1<<(n-1)) * (x%2);//?を1にするために 2進数で表した下一桁が1なら(y%2==1)ならxの一番左(?の部分)を1にするっていう処理 x += (1<<(n-1)) * (y%2)でもok
    return x;
}
int main()
{
    string s;
    cin >>  s;
    n = s.size();
    for(int i = 1; i < (1<<n); i++) dp[i] = 10; // 最大でも10台つければずっと見れるよね(1台で必ず1分は見れるから)
    int tmp = 0;
    for(int i = 0; i < n; i++){
        tmp |= (1<<i) * (s[i] == 'o');  // 'oxxo' は1+0+0+8(2進数なら1001)として扱う
    }

    for(int i = 0; i < n; i++){
        // n回回転させたら元に戻るので,n回やる.
        for(int mask = 0; mask < (1<<n); mask++){
            dp[mask|tmp] = min(dp[mask|tmp], dp[mask]+1);
        }
        tmp = rotate(tmp);  // 1001 を 1100に回転する
    }
    cout << dp[(1<<n)-1] << endl; //dp[1111]を出力する(1の数はn個)
}

コメント無しのコード

dpの中の添字,dp[1100] のときの1100(2進数表記)は,1分目,2分目がテレビを見れる. 3分目,4分目は見れないことを意味しているよ.

ちなみにdp[1100]は,1分目,2分目にテレビを見るために必要なテレビの最小台数を意味しているよ.

初期値は,dp[0000]で,1分目から4分目まで全くテレビを見ないときのテレビの最小台数なので,0台やで.

ちなみに,mask | tmp の意味だけど,2進数表記でmask=0010とtmp=0001があったときに

mask|tmp をすることで,どっちかに1があるなら1になるってことをする(OR演算というやつ)

つまりmask|tmp =(0011)になるたぷにきあ

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます