電球M[i]に使うスイッチをビットで管理する スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯 そういえば今回は書かなかったけどビットカウントをするときは for(int …

電球M[i]に使うスイッチをビットで管理する スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯 そういえば今回は書かなかったけどビットカウントをするときは for( i=b…

bit全探索 毎クエリ計算しているとTLEになるのでクエリの外で前計算してテーブルに持たせておいて,各クエリの処理はテーブルを参照する クエリ処理は気をつけよう…(反省) #include<bits/stdc++.h> using namespace std; int n; int q; int a[29]; map < int, bool > mp; int</bits/stdc++.h>…

これと同じ感じ気が付けば過去問精選100問の工夫して通り数を減らす全列挙まで終了 tanukistune.hatenablog.com #include<bits/stdc++.h> using namespace std; int m, n; vector < pair<int, int> > vm; vector < pair<int, int> > vn; map < pair<int, int >, bool > np; int main(){ cin >> m; for(int i</int,></int,></int,></bits/stdc++.h>…

パッと見た瞬間,A[0]~A[n-1]の間のどこかに入り口があってB[0]~B[n-1]の間のどこかに出口がありそうってなる 最悪のケースで最左端から最右端の可能性もあるしなぁってなりながらもとりあえず2分探索書いてみたけどサンプル合わず サンプルよく見てみると入…

愚直にやるとO(N^4)でキツい 正方形の性質としてある1辺の長さと残りの3辺の長さが同じである つまり任意の2点の距離が分かれば残りの2点は推測できるため,2点を調べるためのO(N^2)で済む ここまでは分かってたのに 面積=a*a+b*b で済むところを sqrt(a*a+b*…