質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1745閲覧

東京海上日動プログラミングコンテスト2020のE問題O(rand)の包除原理を用いた解法のWAの原因を教えていただきたいです。

退会済みユーザー

退会済みユーザー

総合スコア0

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

3クリップ

投稿2020/06/23 01:51

編集2020/06/23 01:55

実現したいこと

東京海上日動プログラミングコンテスト2020のE問題O(rand)で包除原理を用いて解いたのですが、サンプルケースは全てACになるもののテストケースのほとんどでWAになってしまいました。
解説や他の方の解答などを読んでも方針は間違っていないと思いオーバフローなどもないように思われるので、原因の究明をお願いしたいです。
また、デバッグしていただきやすいようにコメントアウトでやりたいことを書いてあります。よろしくお願いします。

ソースコード

c++

1#include <bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4 5//マクロ 6//forループ関係 7//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか 8#define REP(i,n) for(ll i=0;i<(ll)(n);i++) 9#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++) 10//xにはvectorなどのコンテナ 11#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい 12#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく 13//定数 14#define INF 1000000000000 //10^12:極めて大きい値,∞ 15#define MOD 1000000007 //10^9+7:合同式の法 16#define MAXR 100 //10^5:配列の最大のrange(素数列挙などで使用) 17//略記 18#define PB push_back //vectorヘの挿入 19#define MP make_pair //pairのコンストラクタ 20#define F first //pairの一つ目の要素 21#define S second //pairの二つ目の要素 22 23 24signed main(){ 25 //入力の高速化用のコード 26 ios::sync_with_stdio(false); 27 cin.tie(nullptr); 28 ll n,k,s,t;cin >> n >> k >> s >> t; 29 vector<ll> b(n);REP(i,n)cin >> b[i]; 30 vector<ll> a; 31 //i bit目を見て、s_i=1.t_i=1の時は全ての数のi bit目が1→当てはまらないのは除く 32 //i bit目を見て、s_i=0.t_i=0の時は全ての数のi bit目が0→当てはまらないのは除く 33 //i bit目を見て、s_i=1,t_i=0の時は0を出力 34 //i bit目を見て、s_i=0,t_i=1の時は候補に入れる 35 REP(i,n){ 36 bool f=true; 37 REP(j,18){ 38 bool s_,t_,b_;s_=(s>>j)&1;t_=(t>>j)&1;b_=(b[i]>>j)&1; 39 if(s_ and t_){ 40 if(!(b_)){ 41 f=false;break; 42 } 43 }else if(!(s_) and !(t_)){ 44 if(b_){ 45 f=false;break; 46 } 47 }else if(s_ and !(t_)){ 48 cout<<0<<endl;return 0; 49 } 50 } 51 if(f)a.PB(b[i]); 52 } 53 n=SIZE(a); 54 k=min(n,k); 55 //以下ではそれぞれのbitは0と1が少なくとも一つなければならない 56 //余事象は、全ての数で1だけまたは0だけのbitが少なくとも一つある場合 57 //少なくとも一つ→包除原理 58 //それぞれのbitで"0だけになる集合"と"1だけになる集合"を用意すると、3^L(L=18)になる→O(N×3^L) 59 //0だけor1だけなので分割してく 60 //チェックするのは結局N個くらいで済む→O(N×2^L×L) 61 62 //以下、集合はbitで表現 63 64 //まずは、それぞれのbitで集合を分割(そのbitが1か0かで二つに分割→pairで保存) 65 vector<pair<ll,ll>> bits; 66 REP(i,18){ 67 ll f1=0;ll f2=0; 68 REP(j,n){ 69 if((a[j]>>i)&1){ 70 f1+=(1<<j); 71 }else{ 72 f2+=(1<<j); 73 } 74 } 75 if(f1 and f2)bits.PB(MP(f1,f2)); 76 } 77 ll bits_len=SIZE(bits); 78 79 //集合分割したのでさらに分割を行う(部分集合全列挙したいのでbit全探索) 80 //余事象が何通りあるかをans_subに格納 81 ll ans_sub=0; 82 83 //ここで答えでの組み合わせの前計算しておく 84 //prior_calc[i][j]:iC1+iC2+…+iCjの答え(i:1~n,j:1~k) 85 //0-indexed 86 vector<vector<ll>> pcalc(n+1,vector<ll>(k+1,0)); 87 pcalc[0][0]=1; 88 FOR(i,1,n){ 89 pcalc[i][0]=1; 90 FOR(j,1,k){ 91 pcalc[i][j]=pcalc[i-1][j-1]+pcalc[i-1][j]; 92 } 93 } 94 REP(i,n+1){ 95 pcalc[i][0]=0; 96 REP(j,k){ 97 pcalc[i][j+1]+=pcalc[i][j]; 98 } 99 } 100 101 //bit全探索でありうる積集合のパターンを全て考える 102 //2^L 103 //all_setsにはそこまでで分けられた集合を集合ごとに保存(bitでどの要素が含まれるか表す) 104 deque<ll> all_sets; 105 FOR(i,1,(1<<bits_len)-1){ 106 //まず全ての要素が同じ集合に含まれているものとする 107 all_sets.PB((1<<n)-1); 108 //L 109 //包除原理において、積集合で考える集合の個数の偶奇が知りたいので 110 ll odd_even=0; 111 REP(j,bits_len){ 112 //そのbitを積集合を考えるbitとして考慮に入れる時 113 if((i>>j)&1){ 114 odd_even+=1; 115 ll s=SIZE(all_sets); 116 //n 117 //今分けられている集合それぞれをさらに(そのbitが0か1かで)分割する 118 REP(_,s){ 119 //積集合をとりたい集合を書き出す 120 ll ins=*(all_sets.begin()); 121 all_sets.pop_front(); 122 //insはf1とf2へと分割される 123 ll f1=ins&(bits[j].F);ll f2=ins&(bits[j].S); 124 //f1,f2が0の時は空集合なので0通りより無視 125 if(f1){all_sets.PB(f1);} 126 if(f2){all_sets.PB(f2);} 127 } 128 } 129 } 130 //積集合のパターンを決めた下で完全に集合を分割できた 131 //それぞれの集合に対して1以上K以下の数を選ぶ(pcalcを使う) 132 ll s=SIZE(all_sets); 133 //n 134 REP(_,s){ 135 ll now=*(all_sets.begin()); 136 all_sets.pop_front(); 137 //立ってるbit数を数える(注目する集合の要素数を数える) 138 ll s_sub=__builtin_popcount(now); 139 //前計算で求めたpcalcから求める 140 //ここで、包除原理より+-が決まる 141 if(odd_even%2){ 142 ans_sub+=pcalc[s_sub][min(k,s_sub)]; 143 }else{ 144 ans_sub-=pcalc[s_sub][min(k,s_sub)]; 145 } 146 } 147 } 148 //ans_subは余事象のパターン数で、全体のパターン数からその余事象のパターン数を引く 149 cout<< pcalc[n][k]-ans_sub <<endl; 150}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

C++

1 if(f1 and f2)bits.PB(MP(f1,f2));

どちらかが0 かつSのビットが0でTのビットが1 の場合、条件を満たす組み合わせがないということなので、push_backしないだけじゃなくて0を出力して終了するような分岐にすべきです。

あとは型の問題で
シフト演算は 1LL<<i というように左辺をlong long 型にしないとlong long 型にはなりません(オーバーフローします)。
__builtin_popcountも64ビット版は __builtin_popcountllという名前のようです。

これでACできるかどうかはわかりませんが......


もうAC取れたということで蛇足かもしれませんが

どちらかが0 かつどちらかが0 かつSのビットが0でTのビットが1 の場合

今のコードで短絡評価してるのはSのビットが1でTのビットが0の場合なので、ここは評価されていません。
これが問題になるのは下のようなケースです

Text

12 1 0 3 22 4

明らかにTが3になる組み合わせは存在しませんが、今のコードだと1が出力されます。

投稿2020/06/23 16:37

編集2020/06/24 10:05
yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2020/06/24 05:57 編集

> どちらかが0かつSのビットが0でTのビットが1の場合、条件を満たす組み合わせがないということなので、push_backしないだけじゃなくて0を出力して終了するような分岐にすべきです。 この記述についてなのですが、Sのビットが0でTのビットが1の場合は数行前で0を出力して終了しているので、ここでは考慮していないです。自分の書き方がわかりにくかったと思います。ご指摘ありがとうございます。 `1LL<<i`と`__builtin_popcountll`の二つのご指摘の点を直したところ無事ACできました。テストケースでSとTが大きい時にWAだったのでオーバフローだと思ったのですが、勉強不足で上記二つの点にたどり着くことができませんでした。 ご丁寧に回答していただきACできたので、ベストアンサーとさせていただきます。非常に助かりました。ありがとうございました。
退会済みユーザー

退会済みユーザー

2020/06/24 12:59 編集

蛇足についてですが、"どちらかが0かつSのビットが0でTのビットが1の場合"を"Sのビットが1でTのビットが0の場合"と読み間違っていました。 ご指摘の通り上記の場合では自分のコードでは間違った挙動を示すので書き直しました。ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問