ARC108開始前の準備運動として解いてみました。
D問題が中々に苦しかった…。
A – White Cells
Aにしては少し難しめです。
制約が弱いのでシミュレーションしても解けそうですが、計算で求めていきます。
- h個の行を選ぶと、h*W個のタイルがひっくり返る
- w個の行を選ぶと、w*H個のタイルがひっくり返る
- 両方のひっくり返りで重なる範囲がh*w個あるので、二重加算しないようにする
#include<bits/stdc++.h>
using namespace std;
int main(){
int H,W;
int h,w;
cin>>H>>W;
cin>>h>>w;
cout<<H*W-h*W-H*w+h*w<<endl;
}
包除原理と呼んでいいのか分かりませんが、考え方は近いかと思います。
B – Can you solve this?
制約的に全探索で問題なさそうです。
問題文通り実装しましょう。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M,C;
cin>>N>>M>>C;
long long B[M];
for(int i=0;i<M;i++){
cin>>B[i];
}
int ans=0;
for(int i=0;i<N;i++){
long long sum=C;
for(int j=0;j<M;j++){
long long A;
cin>>A;
sum+=A*B[j];
}
if(sum>0) ans++;
}
cout<<ans<<endl;
}
C – Energy Drink Collector
安い栄養ドリンクから買っていくことが最適です。
次に安い栄養ドリンクがどれかを線形探索していくと間に合わなくなるため、ソートしてから探すなど効率の良いアルゴリズムで探していきます。
今回はmapと呼ばれるデータ構造に突っ込みました。mapは突っ込めば自動的に昇順にソートされるので、こういった問題を解く際に楽になります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
map<int,int> m;
for(int i=0;i<N;i++){
int A,B;
cin>>A>>B;
m[A]+=B;
}
auto it=m.begin();
long long ans=0;
while(M>0){
M--;
ans+=it->first;
it->second--;
if(it->second<=0) it++;
}
cout<<ans<<endl;
}
D – XOR World
Atcoder Problemによると緑上位らしいですが、かなり難しいです。
排他的論理和(XOR)は2進数の各桁に着目した場合、”1″が偶数個である場合は0、奇数個である場合は1になります。
なので、この問題は2進数で表したときのA～Bの各桁の”1″の数が偶数か奇数かを求める問題といえます。
10^12がBの最大値であるため、シミュレーションして各桁の”1″の個数を数えると間に合いません。
A=0から増やしていった時の、各桁のbitを観察します。
0 00000 1 00001 2 00010 3 00011 4 00100 5 00101 6 00110 7 00111 8 01000 ...
と、n桁目のbitは2^n個ごとに反転していることが分かります。なので、下位1桁を除いては途中を見る必要がありません。
具体的には、AとBのn桁目が”0″である場合、その中にある”1″は偶数個ごとに反転しているため、”1″の総数も偶数個になりXORは0になるはず。と分かります。
AやBのn桁目が”1″である場合は、次に反転して”0″になるまでの個数が奇数か偶数かで変わるため、そこだけは計算で求める必要があります。
この辺りのややこしい計算を丁寧にコーディングすればAC…なのですが、難易度が中々高いですね…。(2進数苦手)
#include<bits/stdc++.h>
using namespace std;
int main(){
long long A,B;
cin>>A>>B;
long long ans=0;
for(long long i=1ll;i<10000000000000ll;i*=2ll){
long long bit=0;
//あと何回でbit反転するか
long long a=i-A%i;
long long b=B%i+1;
//最初のbit 0or1
long long aa=A/i%2;
long long bb=B/i%2;
//cout<<a<<","<<aa<<" "<<b<<","<<bb<<endl;
if(aa==1&&a%2==1) bit=1-bit;
if(bb==1&&b%2==1) bit=1-bit;
if(i==1){
//下位1bitは特別
//0110011001100
//1100110011001
long long cc=B-A+1;
//cout<<cc<<endl;
if(cc==1){
bit=aa;
}
else{
if(aa==1) cc++;
if(cc/2%2==1) bit=1;
else bit=0;
}
}
ans+=i*bit;
}
cout<<ans<<endl;
}
コメント