NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）D - FizzBuzz Sum Hard
問題の要約
1以上N以下の整数であって、Aの倍数でもBの倍数でもないものの総和を求めよ。
制約
1<=N,A,B<=10^9
入力
N A B
考え方
1,1からNの総和を求める。これはN*(N+1)/2で求めることができる。
2,上の数からAの倍数の総和を引く。Aの倍数の総和はN/A*(N/A+1)/2*Aで求めることができる。
3,上の数からBの倍数の総和を引く。Bの倍数の総和はN/B*(N/B+1)/2*Bで求めることができる。
4,上の数からAの倍数かつBの倍数の倍数(AとBの最小公倍数の倍数)の総和を足す。AとBの最小公倍数lcm_numの総和はN/lcm_num*(N/lcm_num+1)/2*lcm_numで求めることができる。
5,答えを出力する。
(注)倍数の総和は簡単な例で導出可能である。
例えば、3の倍数は3,6,9,12,...となるが、これは3をくくりだせば、3*(1,2,3,4,...)となるので、1からNまでの総和がわかっていれば、ある程度簡単に導出できる。
あとはNまで何個の倍数があればよいか分かればよい。
例えば、3の倍数で10までだと3,6,9の3つだけだが、これはfloor(10/3)で求めることができる。
実際のプログラム
#include<iostream>
#include<numeric>
using namespace std;
int main(){
long long N,A,B;
cin >> N >> A >> B;
if(A > B){
swap(A,B);
}
long long sum = N*(N+1)/2;
sum -= N/A*(N/A+1)/2*A;
sum -= N/B*(N/B+1)/2*B;
long long lcm_num = lcm(A,B);
sum += N/lcm_num*(N/lcm_num+1)/2*lcm_num;
cout << sum << endl;
return 0;
}
NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）C - Max - Min Query
問題の要約
整数の多重集合Sがある。はじめSは空。
Q個のクエリが与えられるので順に処理せよ。クエリは次の3種類のいずれか。
・1 x:Sにxを1個追加する。
・2 x c:Sからxをmin(c,(Sに含まれるxの個数))個削除する。
・3:(Sの最大値)-(Sの最小値)を出力。このクエリを処理するとき、Sが空でないことが保証される。
制約
1<=Q<=2*10^5
0<=x<=10^9
1<=c<=Q
入力
Q
query1
...
queryQ
考え方
1,問題文に多重集合と書いてあるので、multisetでもよいが、今回はmapで考えてみる。
2,クエリの処理を考える。(map<long long,long long> mpで管理する)
1の場合、++mp[x]でよい。
2の場合、min(c,(Sに含まれるxの個数))をmin_numとすると、mp[x]-=min_numでよい。
3の場合、mp.rbegin()->first-mp.begin()->firstではだめ。
なぜならmp.rbegin()->second,mp.begin()->secondともに0である可能性がある。
よって、0のものは無視する。
実際のプログラム
#include<iostream>
#include<map>
using namespace std;
int main(){
int Q;
cin >> Q;
map<long long, long long> mp;
for(int i = 0; i < Q; ++i){
int q;
long long x,c;
cin >> q;
if(q == 1){
cin >> x;
++mp[x];
}else if(q == 2){
cin >> x >> c;
long long min_num = min(c,mp[x]);
mp[x] -= min_num;
}else if(q == 3){
auto it_r = mp.rbegin();
while(it_r->second == 0){
++it_r;
}
auto it = mp.begin();
while(it->second == 0){
++it;
}
cout << it_r->first - it->first << endl;
}
}
return 0;
}
NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）B - Distance Between Tokens
問題の要約
H行W列のマス目があり、そのうち二つの異なるマスに駒が置かれている。
マス目の状態はH個の長さWの文字列S1,...,SHで表される。Si,j=oならばi行目j列目のマスに駒が置かれていることを、Si,j=-ならばそのマスには駒が置かれていないことを表す。
一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要があるか?
制約
2<=H,W<=100
入力
H W
S1
...
SH
考え方
1,駒があるマスの行番号をy1,y2、列番号をx1,x2とする。
2,x1<=x2およびy1<=y2になるように値を交換する。
3,x2-x1+y2-y1が答え。
実際のプログラム
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
int H,W;
cin >> H >> W;
vector<string> S(H);
for(int i = 0; i < H; ++i){
cin >> S[i];
}
int x1,x2,y1,y2;
int check = 0;
for(int i = 0; i < H; ++i){
for(int j = 0; j < W; ++j){
if(S[i][j] == '-'){
continue;
}
if(check == 0){
x1 = j;
y1 = i;
check = 1;
}else if(check == 1){
x2 = j;
y2 = i;
check = 2;
}
}
}
if(x1 > x2){
swap(x1,x2);
}
if(y1 > y2){
swap(y1,y2);
}
cout << x2-x1+y2-y1 << endl;
return 0;
}
NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）A - Median?
問題の要約
整数a,b,cが与えられる。bがこれらの整数の中央値であるかどうか判定しろ。
制約
1<=a,b,c<=100
入力
a b c
考え方
1,bがaとcの間であればよいが、これだけではa<=c,c<aの2通りあるので、c<aの場合aとcの値を交換する。
2,a<=cなので、a<=bかつb<=cならばbは中央値。
実際のプログラム
#include<iostream>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
if(a > c){
swap(a,c);
}
if(a <= b && b <= c){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
AtCoder Beginner Contest 252 C - Slot Strategy
問題の要約
N個のリールからなるスロットがある。
i番目のリールの配列は文字列Siによって表される。ここでSiは0,1,...,9がちょうど1回ずつ現れる長さ10の文字列。
それぞれのリールには対応するボタンがついており、各非負整数tについて、スロットが回り始めてからちょうどt秒後にボタンを1つ選んで押す(または何もしない)ことができる。
スロットが回り始めたからt秒後にi番目のリールに対応するボタンを押すと、i番目のリールはSiの(t mod 10)+1文字目を表示して止まる。
全てのリールを止めた上で、表示されている文字が全て同じであるようにしたい。
目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めよ。
制約
1<=N<=100
Siは0,1,...,9がちょうど1回ずつ現れる長さ10の文字列
入力
N
S1
S2
...
SN
考え方
1,0から9までの文字全てについて最小の秒数を求めればよい。
ある文字cについて最小の秒数を求めたいとする。
秒数t=0から始めて、N個のリールを順にt%10の位置にある文字がcであるかどうかを調べていく(0始まりなことに注意)。
cであった場合、そのリールを削除する。
全てのリールがなくなるまで繰り返す。
実際のプログラム
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int f(vector<string> S, const char c){
int t = 0;
while(!S.empty()){
for(int i = 0; i < static_cast<int>(S.size()); ++i){
if(S[i][t%10] == c){
S.erase(S.begin()+i);
break;
}
}
++t;
}
return t-1;
}
int main(){
int N;
cin >> N;
vector<string> S(N);
for(int i = 0; i < N; ++i){
cin >> S[i];
}
int min_t = 100000;
for(int i = 0; i <= 9; ++i){
min_t = min(min_t, f(S,static_cast<char>('0'+i)));
}
cout << min_t << endl;
return 0;
}
AtCoder Beginner Contest 252 B - Takahashi's Failure
問題の要約
T君の家にN個の食品があり、i番目の食品のおいしさはAi。
また、T君には嫌いな食品がK個あり、具体的にはi=1,2,...,Kについて、Bi番目の食品が嫌い。
T君はN個の食品のうち、おいしさが最大の食品から1つを選んで食べようと考えている。
T君が嫌いな食品を食べる可能性があるならばYesを、食べる可能性が無いならばNoを出力せよ。
制約
1<=K<=N<=100
1<=Ai<=100
1<=Bi<=N
Biはすべて相異なる
入力
N K
A1 A2 ... AN
B1 B2 ... BK
考え方
1,おいしさが最大の食品を全て調べたときに嫌いな食品があるときにYes、そうでなければNoということになる。
2,おいしさの値をvector<int>Aで管理する。
3,おいしさの値を比較して、おいしさが最大の値を持っておく。
4,嫌いな食品を食べる可能性があるかどうかを、bool checkで管理する。初期値はfalse。
5,Bi番目の食品のおいしさが最大のおいしさならcheckをtrueにする。
このとき、Biが1始まりなことに注意する。Biをデクリメントすることで、0始まりの値にすることができる。
実際のプログラム
#include<iostream>
#include<vector>
using namespace std;
int main(){
int N,K;
cin >> N >> K;
vector<int> A(N);
int max_num = 0;
for(int i = 0; i < N; ++i){
int Ai;
cin >> Ai;
A[i] = Ai;
max_num = max(max_num, A[i]);
}
bool check = false;
for(int i = 0; i < K; ++i){
int Bi;
cin >> Bi;
Bi--;
if(A[Bi] == max_num){
check = true;
}
}
if(check){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
