GCJ2020 B - Pascal Walk

B - Pascal Walk

問題へのリンク

和がになるようにパスカルの三角形上を動く問題。

解説

以降、とする。

パスカルの三角形の行の和は二冪であることから、を2進数表現すればうまく表せそうである。ここで、r行に到達したいだけでも、その手前の行を訪れなければ到達できないということに注意したい。

この解決策として、少なくとも30行目までは到達すると仮定してしまうことである。このとき、必ず1列目を通ると仮定すると、は必ず確保することができるので、それ以外のところでadditionalな和を揃えたくなる。すでに1行目のが使われていることから、行目を選ぶ場合、追加で足されるのはである。 つまり、選ぶ行の集合をとすると、

これは非常にbit表現に似ているが、惜しい。シグマの中身がされてしまっており、うまく表現できなさそうである。ここで、30行が終わったあと、集合のサイズ分だけさらに下に行を増やすことで解決することができる。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define bit(k) (1LL<<(k))

void solve(){
    int N;
    cin >> N;
    if(N < 30){
        rep1(i,N+1){
            cout << i << " " << 1 << endl;
        }
        return;
    }
    N -= 30;
    int isleft = 1;
    int cnt = 0;
    for(int r = 1; r <= 30;r++){
        if(N & bit(r-1)){
            cnt++;
            if(isleft){
                for(int col = 1; col <= r;col++){
                    cout << r << " " << col << endl;
                }
            }
            else{
                for(int col = r; col >= 1;col--){
                    cout << r << " " << col << endl;
                }
            }
            isleft ^= 1;
        }
        else{
            cout << r << " " << (isleft ? 1: r) << endl;
        }
    }
    for(int k = 1; k <= cnt;k++){
        cout << 30 + k << " " << (isleft ? 1: 30 + k) << endl;
    }
}
int main() {
    int t;
    cin >> t;
    rep1(i, t+1){
        cout << "Case #" << i << ":" << endl;
        solve();
    }
}

• 参考 William Lin YouTube Channel