ABC253の感想など
ABC253に参加しました。全体的にボロボロです…
感想と、簡単な解説を残しておきます。
A問題
中央値を求める問題
リストに入れてソートしてってやってもいいですね。
私はPythonでぱぱっと解きました→WA
理由はA<=B<=Cと思ってたことです。
逆も追加すれば通ります。
A,B,C=map(int,input().split())
print("Yes" if A<=B<=C or A>=B>=C else "No")#include<bits/stdc++.h>
using namespace std;
int main(){
int A,B,C;
cout<<((A<=B&&B<=C)||(A>=B>=C)?"Yes":"No")<<endl;
}B問題
oのある位置のｘ軸の差とｙ軸の差を足し合わせればよいです。
絶対値を取り忘れないように注意
ちなみにvector<pair<int,int>>を使うと2つしかない制約から簡単です。
参考コード
今回はごり押します。
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
int H,W;
cin>>H>>W;
int x=0,y=0;
REP(i,H){
string s;
cin>>s;
REP(j,W){
if(s[j]=='o'){
if(x==0&&y==0){
x=i;
y=j;
}else{
x-=i;
y-=j;
}
}
}
}
cout<<abs(x)+abs(y)<<endl;
}H,W=map(int,input().split())
x=0
y=0
for i in range(H):
s=input()
for j in range(W):
if s[j]=='o':
if x==0 and y==0:
x=i
y=j
else:
x-=i
y-=j
print(abs(x)+abs(y))C問題
multisetで管理すればすぐ解けてしまう問題。
ただし、multisetはeraceしたときに同じ数字のものはすべて消し去ってしまうので、findと組み合わせてc回のループを回す。
別解として、mapを使用して個数を管理する方法が挙げられる。
c++の場合、map自体が平衡二分探索木なので扱うのも簡単
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
int Q;
cin>>Q;
multiset<int> ms;
while(Q--){
int q;
cin>>q;
if(q==1){
int x;
cin>>x;
ms.insert(x);
}else if(q==2){
int x,c;
cin>>x>>c;
while(c--){
auto itr=ms.find(x);
if (itr==ms.end()) break;
ms.erase(itr);
}
}else{
cout<<*ms.rbegin()-*ms.begin()<<endl;
}
}
}#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
int Q;
cin>>Q;
map<int,int> mp;
while(Q--){
int q;
cin>>q;
if(q==1){
int x;
cin>>x;
mp[x]++;
}else if(q==2){
int x,c;
cin>>x>>c;
mp[x]-=c;
if(mp[x]<=0)mp.erase(x);
}else{
cout<<(*mp.rbegin()).first-(*mp.begin()).first<<endl;
}
}
}Pythonはあまり得意ではないのでatcoderのユーザー解説に丸投げします。
toamさんの参考になるユーザー解説
D問題
苦戦しました…
苦戦したこと→コーナーケース、A*B→lcm(A,B)に気付かない
この問題でやること自体は簡単で、
[1] 1~Nの総和
[2] Aの倍数の総和
[3] Bの倍数の総和
[4] lcm(A,B)の倍数の総和
を求め、[1]-[2]-[3]+[4]をします。いわゆる包除原理です。
[1]~[4]すべてが等差数列の和の公式で出せます。
[1] 1~Nの総和はN(N+1)/2で出します。
[2] 1~Nに含まれるAの倍数はN/A個で初項A、項数A/N、公差Aの等比数列になるので、その和を公式で出して整理すると、N/A*(A*(N/A+1))/2となります。
[3]と[4]も同様です。
私はこの問題でずっとミスをし続けました…上に書いた通り、lcm(A,B)の部分をA*Bと書いていたことです…
それを踏まえて解答例です…
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
ll N, A, B;
cin >> N >> A >> B;
ll sum = N * (N + 1) / 2;
ll NA = N / A, NB = N / B, NAB = N / (A*__gcd(A,B)*B);
ll sumA = NA * (A * (NA + 1)) / 2;
ll sumB = NB * (B * (NB + 1)) / 2;
ll sumAB = NAB * (A/__gcd(A,B)*B * (NAB + 1)) / 2;
prt(sum - sumA - sumB + sumAB);
}(解ききれなかった)E問題
解ききれなかったポイント→K=0
あと５分あれば…
この問題は見てすぐに察しました。DPです。数え上げの問題で、modを取れと言われたら大抵DPです。(グラフでBFSなどの場合も本質的にはDPです)
しかし、制約的に愚直解法が通らないことがわかります。
そこで、累積和を使った高速化をします。
今回私はもらうDPで累積和を用いた高速化をしました。
具体的には、
dp[N][M]がそれぞれ0で初期化され、dp[0][j]は1で初期化された状態で、累積和をとった配列をsumsとすると、
dp[i][j]=sums[M]-sums[min(M,j+K)]+sums[max(j-K+1,0LL)];で遷移することができます。
それを用いて解きましたが、K＝０の時は例外的にすべてがOKになるのでsums[M]を足します。
これに気付いていれば…
提出コード(WA)
提出コード(AC)
まとめ
全体的にミスが目立ちました…落ち着いて解こうと思います…
明日のARCも出ますが、ARCは今のところ全敗なのでそろそろ勝ちたいと思います。