ブルーブリッジカップロボットタワー——python

タイトルは以下の通りです.
X星のロボットショー応援団には、AとBの2種類の衣装があります.
彼らが今回披露したのはロボットタワーです.
類似:
A
B B
A B A
A A B B
B B B A B
A B A B B A
チーム内のタワーのルールは次のとおりです.
AはAAかBBの肩にしか立たない.
BはABかBAの肩にしか立たない.
あなたの任務は応援団を助けて、AとBの人数を与えたとき、何種類の模様の塔を構成することができるかを計算することです.
入力記述入力1行2個の整数M,NM,N(0)
出力記述は、生成可能な花種数を表す整数を出力する必要がある.
入出力サンプル入力
1 2出力
3
テーマ解析
この問題はどうすればいいですか.私たちは実際に最初の行を調べるだけで直接上に押すことができることに気づいた.こんなに議論する必要はありません.しかし、最初の行はいくつあるのでしょうか.ロボットの総数cnt=M+N、それでは何層をすることができますか?このように考えて、num層があると仮定すると、これがnumステップ長が1の等差数列であり、タワー内のロボット総数cnt=num*(num+1)/2=M+Nであるため、num=sqrt((M+N)*2)となる.そこで決めました.次は最初の行を探して、上に拡張できるかどうか、A、Bの数が十分に使われているかどうかを確認します.ここでは、最初の行のすべてのオプションを巡回し、Aを1、Bを2で表すと同時に再帰的な方法を使用します.次にチェックコードを設定し、行がすべてのA,Bを計算し始めるようにします.個数が最上位に達してもm,nと同じであれば、実行可能であることを示します.
code

import math

def check():#           
    a = 0
    b = 0
    tmp = row
    while tmp >0:
        for i in range(1, tmp+1):
            if cnt[i] == 1:
                a +=1
            else:
                b += 1
        for i in range(2, tmp+1):
            if cnt[i-1]==cnt[i]:
                cnt[i-1] = 1
            else:
                cnt[i-1] = 2
        tmp -=1
    if a == m and b == n:
        return True
    else:
        return False

def dfs(k):#        
    global res
    if k > row:
        if check():
            res +=1
        return
    cnt[k] = 1
    dfs(k+1)
    cnt[k] = 2
    dfs(k+1)

if __name__ == "__main__":
    m = int(input())
    n = int(input())
    res = 0
    cnt = [0 for _ in range(100010)]
    row = int(math.sqrt(2*(m+n)))
    dfs(1)
    print(res)

第2の解法
もちろん、これ以外にも調べました.これはあまり速くないので、ネット上でもう一つ収集しました.実は原理も悪くありません.コード量を増やして時間の複雑さを少し下げ、同時に多くのデータを収容することができます.コードは次のとおりです.

def dfs(x, s, aa,bb):
    global ans
    if aa<0 or bb<0:
        return
    if aa==0 or bb==0:
        ans +=1
        return
    cs = bs = 0
    p = 'A'
    cs +=1
    for i in range(len(s)):
        if s[i] == 'A':
            if p[i] =='A':
                p += 'A'
                cs += 1
            else:
                p+= 'B'
                bs +=1
        else:
            if p[i] =='A':
                p += 'B'
                bs += 1
            else:
                p+= 'A'
                cs +=1
    dfs(x+1, p, aa-cs, bb-bs)
    cs = bs = 0
    q = 'B'
    bs +=1
    for i in range(len(s)):
        if s[i] == 'A':
            if q[i] =='A':
                q += 'A'
                cs += 1
            else:
                q+= 'B'
                bs +=1
        else:
            if q[i] =='A':
                q += 'B'
                bs += 1
            else:
                q+= 'A'
                cs +=1
    dfs(x+1, q, aa-cs, bb-bs)


if __name__ == "__main__":
    a = int(input())
    b = int(input())
    ans = 0
    c = []
    c += 'A'
    dfs(1,c,a-1,b)
    c[0] = 'B'
    dfs(1,c,a, b-1)
    print(ans)

第3の解法
3つ目の解法は最も簡単なはずですが、残念ながらソースコードはC言語で、pythonで書こうとしたとき、pythonのビット演算に大きな欠点があることに気づきました.大きな数字を計算すると、より長い整数に変換できず、負数になります.この新聞は長い間探していませんでしたが、歯を食いしばるしかありませんでした.便利さを楽しむときにも迷惑がかかることも分かった.この方法はバイナリのビット演算を利用しており,原理は以下の通りである.

'''
   A    0，  B    1，                         。

AB   ，   01  ，      x，      AB-01       y      ：
y =  x ^ (x    )       
    ：

A B A B B A        x = 010110，             x^(x>>1)     y=011101，y          ，      y=11101   BBBAB，     y       ：
y = x ^ (x>>1)

y &= (1 << (i - 1))  - 1 //                    1
               。
'''
#     ，    
#    
import math


n = 1
m = 2
num = int(math.sqrt((m+n)*2))
ans = 0

def nbit(x):
    ans = 0

    while x:
        x = x&(x-1)
        ans +=1
    return ans

def check(i, num):
    a = 0
    b = 0

    for j in range(num, 1, -1):
        count = nbit(i)
        a +=count
        b+=i-count
        i = i^(i>>1)
        s = 1 << (i-1)-1
        i = i & s
        if a>m or b > n:
            return False
    return a == m and b == n

for i in range(1<<num):
    if check(i, num):
        ans +=1
print(ans)

しかしC++のコードはうまく動作するので試してみることができます.

#include
#include
#include

using namespace std;


int n, m;
int nbit(int num) {
     
    int ans = 0;
    while(num){
     
        num = (num-1) & num;
        ans++;
    }
    return ans;
}
bool check(int now, int floor) {
     
    int num_a = 0, num_b = 0;

    for (int i = floor; i >= 1; i--) {
     //i   ，       
        int count1 = nbit(now);//now     1
        num_b += count1;
        num_a += i - count1;//now     0
        //         now
        now ^= now >> 1;
        now &= (1 << (i - 1)) - 1; //     

        if (num_a > m || num_b >> n) return false;//         
    }
    return num_a == m && num_b == n;
}

int main() {
     
//    freopen("/Users/zhengwei/CLionProjects/lq_final/2016_c_b/4/in6.txt", "r", stdin);
    cin >> m >> n;
    //  double int         ， (floor + 1) * (floor) / 2 == n + m    
    int floor = sqrt((n + m) * 2);//    ==  

    int ans = 0;
    //2 floor       ，        i
    for (int i = 0; i < (1 << floor); i++) {
     
        if (check(i, floor))
            ans++;
    }
    cout << ans << endl;
}

まとめ
これを見ることができる人はきっとすごいでしょう.この問題は6題目です.全部で7題のブルーブリッジカップはもう圧巻です.確かにこの問題は完全にはできません.簡単なdfsアルゴリズムしか考えられません.一部のデータしか通じませんが、これらのデータは私たちが多くの選手を超えるのに十分だと思います.テーマは諦めないでください.しかし、ずっと時間を費やさないでください.学会「問題を解く」は単に問題を解くことを学ぶだけではありません.皆さん頑張ってください.