はじめてのD問題AC！ - みずまずぷろぐらみんぐ日記

こんにちはー、みずまずです。

気合を入れて臨んだ昨日のABC171ですが、とても悔しい結果に終わってしまいました。
A問題,B問題は過去最高ペースで通過したのに、Cで詰まり終了(ﾁｰﾝ)

今日再度挑戦してみたのですがしたりしたのですが、方針まではコンテスト中に気づいていたのであっさりAC。

ぴえん。

ただコンテスト終了後にTwitter見てた感じだと、C飛ばしてD,Eを先に見に行った人結構いたみたいですね。

"単純にコードを書いたとしてもTLEになってしまう"
それがD辺りの問題の難しさなのかなと2度目のコンテスト(ABC170)参加時に感じ、アルゴリズムのアの字もわかっていない自分が手を出すには早いと思っていたのですが…………

CできなくてもDできた人がいるとわかると、やっぱりちょっと挑戦したくなるのもので……

今何となくやってみたらできました←

嬉しいです。

この記事で言いたかった事それだけです。

(とはいえ何も考えなかったわけではないです。
出てくる数字(特にループの回数を左右するやつ)の大きさを考えたり、むやみな多重ループは封印したり、四則演算の回数を少なくするにはどうしたらいいかななど、今の自分が持てる知識はちゃんと使いました。)

一般的にはC問題よりD問題の方が難易度が高いとは思いますが、今後はCに手を出して厳しいと思ったら"早い段階で"一度D問題も見てみるのもありかな、と思えました。

昨日はへこんだけど今日はちょっとるんるんなので、D問題の自分の回答を載せさせてください。
(おかしいところがあったらご指摘、ご指導、お願いします！)

D Replacing

制約から 1 ≤ N, Q, Ai, Bi, Ci ≤ 10^5 なので

・もしN=10^5でAiが全て同じ数だったら10^5個の要素の書き換えが発生するかも

・Q=10^5だったら操作は10^5回やらなきゃなので、その度にいちいち配列A(最大で10^5個の要素を持つ)の全要素を全部足し合わせて和Siを求めるのは時間超過しそう

・あと、存在しないkeyで配列[key]をしてアクセスしちゃうとValueの型の初期値が追加されるから、CはともかくBがAに存在しているか調べておかないとな
(配列.at(key)でのアクセスはエラーが出るので大丈夫(大丈夫かはわからんが追加はされない))

この辺りを意識して解きました。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, q;
  cin >> n;
  map<int, int> a;//key=Ai,value=何回出てきたか
  int64_t s = 0;
  for (int i = 0; i < n; i++) {
    int ai;
    cin >> ai;
    if (a.count(ai)) a.at(ai)++;
    else a[ai] = 1;
    s += ai;
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int b, c;
    cin >> b >> c;
    if (a.count(b)) {
      if (a.count(c)) {
        s += (c - b) * a[b];
        a[c] += a[b];
        a.erase(b);
      }else {//Aにcはない
        a[c] = a[b];
        a.erase(b);
        s += (c - b) * a[c];
      }
    }
    cout << s << endl;
  }
}

まず出現回数ごとに整数をまとめたいので、添え字を整数、値を出現回数とする配列を作ることも考えたのですが、要素数の大きな配列を使うのがこわいのでmapを使いました。

求めるものも和Siだけなので、最初の状態の和だけAiを入力する時に一緒に足し合わせておいて、Q回ある出力時にはBi→Ciの書き換えで生じる変化分だけ、簡単な足し引きでSの値を書き換えてあげるようにしました。

こんな感じですかね……。

なんか普段よりさらに需要がなさそうな記事になってしまった、な…。
APG4b育ちな書き方なので、APG4bでC++勉強中の方とかは回答例として読みやすいかも？そうであってくれ。

コンテストページ↓
atcoder.jp