abc023_d
結構悩んで解いた問題。
解説を読んでも
if(t[i] < i) flg = false;
の部分がずっとハテナだったけどt[i]はデッドラインだからデッドラインが今割るべき時間iより小さかったらNG
#include<bits/stdc++.h>
using namespace std;
int n, h[100009], s[100009];
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> h[i] >> s[i];
long long int ng = 0, ok = 100000000000009;
while(abs(ok - ng) > 1){
long long int mid = (ok + ng)/2;
bool flg = true;
for(int i=0;i<n;i++){
for(int i=0;i<n;i++){
//cout << t[i] << endl;
if(t[i] < i) flg = false;
}
}
if(flg) ok = mid;
else ng = mid;
//cout << mid << " " << flg << endl;
}
cout << ok << endl;
}
*1:mid-h[i])/s[i]);
else flg = false;
}
if(flg){
sort(t.begin(), t.end(
arc084_a
少し紙に書いて考えたら、なるほどーって閃いた問題
中部を基準として決め打ちすると
・基準より小さいものを上部から選ぶ
・基準より大きいものを下部から選ぶ
というそれぞれの二分探索を行えば作れる祭壇のパターン数が分かる
あとは全中段のパターン数を足せばOK
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100009], b[100009], c[100009];
int solve1(int p){
int ok = -1;
int ng = n;
while(abs(ok-ng)>1){
int mid = (ok+ng)/2;
if(a[mid] < p) ok = mid;
else ng = mid;
}
return ok;
}
int solve2(int p){
int ng = -1;
int ok = n;
while(abs(ok-ng)>1){
int mid = (ok+ng)/2;
if(p < c[mid]) ok = mid;
else ng = mid;
}
return ok;
}
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<n;i++) cin >> b[i];
for(int i=0;i<n;i++) cin >> c[i];
sort(a, a+n);
sort(b, b+n);
sort(c, c+n);
long long int cnt = 0;
for(int i=0;i<n;i++){
long long int j = solve1(b[i]);
long long int k = solve2(b[i]);
cnt += (j+1) * (n-k);
//cout << i << " " << j << " " << k << endl;
}
cout << cnt << endl;
}
joi2009ho_b
宅配先に近い店舗を二分探索で見つける。
今回は探したいものが環状線になっているのでd-1と0をまたぐ必要がある
→番兵としてdの箇所にも店舗を置いておく(本店の座標は0=d)
あとはd[i] < kを満たすような最大のd[i]を見つけて、kを跨いだ隣の店舗d[i+1]との差分の小さい方が一番近い店舗となる。
#include<bits/stdc++.h>
using namespace std;
int d, n, m;
int a[100009];
int solve(int k){
int ok = 0;
int ng = n+1;
while(abs(ok-ng)>1){
int mid = (ok+ng)/2;
if(a[mid] <= k) ok = mid;
else ng = mid;
}
return min(abs(a[ok]-k), abs(a[ok+1]-k));
}
int main(){
cin >> d >> n >> m;
for(int i=1;i<n;i++) cin >> a[i]; a[0] = 0; a[n] = d;
sort(a, a+n);
int sum = 0;
for(int i=0;i<m;i++){
int k;
cin >> k;
sum += solve(k);
//cout << "solve:" << solve(k) << endl;
}
cout << sum << endl;
}
ALDS1_4_B
T[i]がSの中に含まれているかを二分探索する。
二分探索は関数化すると実装しやすい。
問題とは関係ないけど、macを購入してから初めてのAC
自分の持ってるwindows機より軽くて持ち運びやすいmacbook airで競プロできるのは勉強時間増えるのでGOOD
#include<bits/stdc++.h>
using namespace std;
int n, s[100001], q;
bool solve(int a){
int ok = 0;
int ng = n;
while(abs(ok-ng)>1){
int mid = (ok+ng)/2;
if(s[mid] <= a) ok = mid;
else ng = mid;
//cout << mid << endl;
}
return s[ok] == a;
}
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> s[i];
sort(s, s+n);
cin >> q;
int cnt = 0;
for(int i=0;i<q;i++){
int a;
cin >> a;
if(solve(a)) cnt++;
}
cout << cnt << endl;
}
ALDS1_13_A
有名な8クイーン問題
・同じ行、同じ列にクイーンを置かないこと
・左斜め上、左斜め下、右斜め上、右斜め下にクイーンを置かないこと
上記2点を満たせばよい。
・同じ行、同じ列にクイーンを置かないこと
⇒順列そのままで全列挙可能なので判定は不要
・左斜め上、左斜め下、右斜め上、右斜め下にクイーンを置かないこと
⇒4ベクトル方向に探索
条件1は順列のみで実現出来るのであとは8個のクイーンが全て条件2を満たせばOK
#include<bits/stdc++.h>
using namespace std;
int k, r[9], c[9];
int board[9][9];
int dx = {1, -1, 1, -1};
int dy = {1, 1, -1, -1};
void print(){
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(board[i][j] == 1) cout << "Q";
else cout << ".";
}
cout << endl;
}
return;
}
bool judge(int y, int x){
bool flg = true;
for(int i=0;i<4;i++){
int ny = y, nx = x;
while(true){
ny += dy[i], nx += dx[i];
if(ny < 0 || ny > 8 || nx < 0 || nx > 8) break;
if(board[ny][nx] == 1){
flg = false;
break;
}
}
}
return flg;
}
int main(){
cin >> k;
for(int i=0;i<k;i++) cin >> r[i] >> c[i];
for(int i=0;i<8;i++) v.push_back(i);
do{
bool flg = true;
memset(board, 0, sizeof(board));
for(int i=0;i<8;i++){
int y = i, x = v[i];
board[y][x] = 1;
for(int j=0;j<k;j++){
if(r[j] == y && c[j] != x) flg = false;
}
flg &= judge(y, x);
if(!flg) break;
}
if(flg){
print();
break;
}
}while(next_permutation(v.begin(), v.end()));
}
abc150_c
問題文通り
vector <int> v;
for(int i=0;i<n;i++) v.push_back(i+1);
do{
}while(next_mermutation(begin(v), end(v)));
上記テンプレを覚えればとりあえずOK
#include<bits/stdc++.h>
using namespace std;
int n;
int p[9], q[9];
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> p[i];
for(int i=0;i<n;i++) cin >> q[i];
for(int i=0;i<n;i++) v.push_back(i+1);
int pp = 0, qq = 0;
for(int i=0;i<n;i++){
pp *= 10; pp += p[i];
qq *= 10; qq += q[i];
}
int a = 0, b = 0, i = 0;
do{
int vv = 0;
for(int j=0;j<n;j++){
vv *= 10;
vv += v[j];
}
if(pp == vv) a = i;
if(qq == vv) b = i;
//cout << vv << endl;
i++;
}while(next_permutation(begin(v), end(v)));
// cout << a << " " << b << " " << pp << " " << qq << endl;
cout << abs(a-b) << endl;
}
abc145_c
問題文通りに実装するだけ
こういう系って再帰で実装できなかったかなぁー？とこねくり回したけどうまく書けず
ググったら便利な関数出てきてほぼ写経
#include<bits/stdc++.h>
using namespace std;
int n;
int x[10], y[10];
int main(){
cin >> n;
for(int i=0;i<n;i++){
cin >> x[i] >> y[i];
v.push_back(i);
}
double ret = 0;
double cnt = 0;
do{
for(int i=1;i<n;i++) ret += hypot(x[v[i]]-x[v[i-1]], y[v[i]]-y[v[i-1]]);
cnt++;
} while(next_permutation(begin(v), end(v)));
printf("%lf\n", ret/cnt);
}
