s8pc_6_b
パッと見た瞬間,A[0]~A[n-1]の間のどこかに入り口があってB[0]~B[n-1]の間のどこかに出口がありそうってなる
最悪のケースで最左端から最右端の可能性もあるしなぁってなりながらもとりあえず2分探索書いてみたけどサンプル合わず
サンプルよく見てみると入り口と出口に必ずA[i]とB[i]が含まれてる事を発見
N個の中から入り口と出口を探してAC
#include<bits/stdc++.h>
using namespace std;
int n;
long long int a[33], b[33];
int main(){
long long int sum = 0;
cin >> n;
for(int i=0;i<n;i++){
int aa, bb;
cin >> aa >> bb;
if(aa < bb) a[i] = aa, b[i] = bb;
else a[i] = bb, b[i] = aa;
sum += abs(aa-bb);
}
long long int ax = 40000000000;
long long int bx = 40000000000;
for(int i=0;i<n;i++){
long long int asum = 0;
for(int j=0;j<n;j++){
asum += llabs(a[i] - a[j]);
}
long long int bsum = 0;
for(int j=0;j<n;j++){
bsum += llabs(b[i]-b[j]);
}
ax = min(ax, asum);
bx = min(bx, bsum);
}
cout << sum + ax + bx << endl;
}
joi2007ho_c
愚直にやるとO(N^4)でキツい
正方形の性質としてある1辺の長さと残りの3辺の長さが同じである
つまり任意の2点の距離が分かれば残りの2点は推測できるため,2点を調べるためのO(N^2)で済む
ここまでは分かってたのに
面積=a*a+b*b で済むところを sqrt(a*a+b*b)^2 ってやってたせいで小数点誤差してWA出しまくってた.
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n;
bool c[5009][5009];
int main(){
cin >> n;
for(int i=0;i<n;i++){
int x, y;
cin >> x >> y;
c[x][y] = true;
vec.push_back( make_pair(x, y) );
}
int ans = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int a = vec[i].S - vec[j].S, b = vec[i].F - vec[j].F;
int px = vec[i].F - a, py = vec[i].S + b;
int qx = vec[j].F - a, qy = vec[j].S + b;
if(px < 0 || py < 0 || qx < 0 || qy < 0) continue;
if(px > 5000 || py > 5000 || qx > 5000 || qy > 5000) continue;
if(c[px][py] && c[qx][qy]) ans = max(ans, a*a+b*b);
}
}
cout << ans << endl;
}
sumitb2019_d
愚直にやるとO(N^3)
3桁が肝っぽいなーと思いつつも分からないので解説へ
000~999がN文字で作れるかを見るとO(10^3*N)でOK
(10^3は定数だから無視…？まぁいいや)
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
cin >> n;
cin >> s;
int cnt = 0;
for(int i=0;i<1000;i++){
int pos = 0;
char c[3] = {'0', '0', '0'};
c[0] += i/100;
c[1] += (i%100)/10;
c[2] += i%10;
for(int j=0;j<n;j++){
if(s[j] == c[pos]) pos++;
if(pos == 3){
cnt++;
break;
}
}
}
cout << cnt << endl;
}
abc095c
この問題…過去の社内コンテストで同じの出たぞ…！！
一応全探索で解いた
ピザCの枚数が決まればピザAとピザBの枚数も決まるからピザCの枚数をループで回しながら答えを探す
#include<bits/stdc++.h>
using namespace std;
int a, b, c, x, y;
int main(){
cin >> a >> b >> c >> x >> y;
int ans = 1<<30;
int n = max(x, y) * 2;
for(int i=0;i<=n;i++){
int na = max(x-i, 0);
int nb = max(y-i, 0);
ans = min(ans, a * na + b * nb + 2 * c * i);
}
cout << ans << endl;
}
条件式でやるときは
･ハーフピザが高い→X枚ピザA,Y枚ピザB
･ハーフピザが安い→min(X, Y)までハーフピザ,残りをピザAもしくはピザBとハーフピザの安い方を買う
#include<bits/stdc++.h>
using namespace std;
int a, b, c, x, y;
int main(){
cin >> a >> b >> c >> x >> y;
int ans = 0;
if(a + b < 2 * c) ans = a * x + b * y;
else if(x < y) ans = min(2 * c * y, 2 * c * x + b * (y-x));
else ans = min(2 * c * x, 2 * c * y + a * (x-y));
cout << ans << endl;
}
pakencamp_2019_day3_c
全列挙最終問題
一人が2曲歌っても点数の高い方しか加点されないことに注意
異なる2曲の選び方を0<=i<mとi+1<=j<mのiとjで表現するとi<jかつi!=jになる
#include<bits/stdc++.h>
using namespace std;
int n, m;
long long int a[109][109];
int main(){
cin >> n >> m;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> a[i][j];
long long ans = 0;
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
long long int sum = 0;
for(int k=0;k<n;k++){
sum += max(a[k][i], a[k][j]);
}
ans = max(ans, sum);
}
}
cout << ans << endl;
}
abc122b
全探索問題
サンプル2
HATAGAYA
の出力結果が5なのに驚いた
パッと見そんなにあるように思えない…
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
cin >> s;
int ans = 0;
for(int i=0;i<s.size();i++){
int cnt = 0;
for(int j=i;j<s.size();j++){
if(s[j] != 'A' && s[j] != 'C' && s[j] != 'G' && s[j] != 'T') break;
cnt++;
}
ans = max(ans, cnt);
}
cout << ans << endl;
}
abc106b
全探索問題2問目
奇数って条件を忘れないように
(サンプル合わなくて焦った)
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
int ans = 0;
for(int i=1;i<=n;i+=2){
int cnt = 0;
for(int j=1;j<=i;j++){
if(i%j == 0) cnt++;
}
if(cnt == 8) ans++;
}
cout << ans << endl;
}
