ABC171に挑んだ回
今回で通算10回目。
うち2回は数年前のこと&週1開催だから最近2ヶ月はAtCoderと共にいたことになる。
お前とも長い付き合いになってきたな。
今回はDまで突破。
C - One Quadrillion and One Dalmatians
むしろCの方が細かい計算ミスして時間食った。
テスト書きながらでもやったほうが良いんだろうか…。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void funcC() { ll N; cin >> N; string name; while (N > 0) { N--; name += 'a' + (N % 26); if (N < 26) break; N /= 26; }; reverse(name.begin(), name.end()); DisplayAnswer(name); } |
26(z)、27(aa)、51(ay)、52(az)、53(ba)近辺の値が怪しかった。
1の位、10の位がaになる計算をとち狂いがち。
D - Replacing
絶対愚直に計算したらTLEだろうなぁ。まぁTLEケースも試そうかなぁと思ったけど面倒で、思いついてた方法を書いたら一発通過。
うれしみをかんじます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
void funcD() { ll N; cin >> N; map<ll, ll> map; ll sum = 0; // mapに map[対象の値]=出現回数 になるようにカウント for (ll i = 0; i < N; ++i) { ll n; cin >> n; map[n]++; // 初期時点での合計値も一緒に計算 sum += n; } ll Q; cin >> Q; // Q回ループする while (Q--) { ll b, c; cin >> b >> c; // map[x]の中身は出現回数。 // 合計値から置き換え前の数値の合計を引く sum -= map[b] * b; // map[c]の出現回数に[b]の出現回数を足す map[c] += map[b]; // 変更された出現回数分、cの合計値を足す sum += map[b] * c; // [b]は空になっていらないので消す map.erase(b); DisplayAnswer(sum); } } |
E - Red Scarf
にゃんにゃん。
こうかも!って思ったときに思考ロックしちゃって他の考えに及ばなくなるのはよろしくない。
先にソース見て完全なる間違いを理解した。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void funcE() { ll N; cin >> N; vector<ll> vec(N); ll k = 0; for (ll i = 0; i < N; ++i) { cin >> vec[i]; k ^= vec[i]; } vector<ll> A; for (ll i = 0; i < N; ++i) { A.push_back(k ^ vec[i]); } DisplayAnswerOneLine(A); } |
A xor Bの結果は、1:奇数回出現 0:偶数回出現 の意味になる。
2進数表示(cout << std::bitset<6>(k) << endl;
)しながら考えると、
すべての値をxorしたkは01110
。
2^4が偶数(0)、2^3が奇数(1)、2^2が奇数(1)、2^1が奇数(1)、2^0が偶数(0)回出現する。
猫②③④をxorした値が10100
。
①以外の出現回数で、2^4が奇数(1)、2^3が偶数(0)、2^2が奇数(1)、2^1が偶数(0)、2^0が偶数(0)回出現する。
①+②③④で出現回数をkにしたいので、
偶数(0)と偶数(0)→出現の必要なし(0)
奇数(1)と奇数(1)→出現の必要なし(0)
偶数(0)と奇数(1)→出現の必要あり(1)
という変換を噛ませたい。つまりこれ、xorと同じ。
k xor ②③④すれば良し。
上記を踏まえてコメント追加。考えるべきはここだけだった。
これ突破率高かったのに超えられなかったの悔しいなぁ。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void funcE() { ll N; cin >> N; vector<ll> vec(N); ll k = 0; for (ll i = 0; i < N; ++i) { cin >> vec[i]; k ^= vec[i]; // すべての値の出現回数を足す } vector<ll> A; for (ll i = 0; i < N; ++i) { A.push_back(k ^ vec[i]); // すべての値とのxor } DisplayAnswerOneLine(A); } |
コメントを残す