見出し画像

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のある位置のx軸の差とy軸の差を足し合わせればよいです。
絶対値を取り忘れないように注意
ちなみに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
あと5分あれば…

この問題は見てすぐに察しました。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=0の時は例外的にすべてがOKになるのでsums[M]を足します。
これに気付いていれば…
提出コード(WA)
提出コード(AC)

まとめ

全体的にミスが目立ちました…落ち着いて解こうと思います…

明日のARCも出ますが、ARCは今のところ全敗なのでそろそろ勝ちたいと思います。

この記事が気に入ったらサポートをしてみませんか?