ABC171振り返り

投稿者: | 2020年6月22日
0件のコメント

ABC171参加してました。今回は43分で4完できたのでめっちゃ喜んでいました。パフォーマンスも上がりました。やったね！ただ、今までのマイナスが大きすぎてハイスコアすら更新できない辛さ。年内には緑に上がりたいです。


1.A問題

やるだけです。char型の比較では、文字と文字を比較できることを忘れなければif文だけで実装できました。私はASCIIコード表出さなきゃ！って慌ててました。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
char c;
cin >> c;
if (c >= 'A' && c <= 'Z')
cout << 'A' << endl;
else
cout << "a" << endl;
return 0;
}
view raw ABC171a.cpp hosted with ❤ by GitHub

2.B問題

これもやるだけです。価格を昇順にソートして、先頭からN個加算すれば終わりです。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
int n, k;
cin >> n >> k;
int a[n];
rep(i, n) cin >> a[i];
sort(a, a + n);
int ans = 0;
rep(i, k) ans += a[i];
cout << ans << endl;
return 0;
}
view raw ABC171b.cpp hosted with ❤ by GitHub

3.C問題

問題文見て計算用紙に書き出してから、なんだこれ・・・？となってD問題を通した後に解きました。実装してみたらただそれだけって感じでした。

要するに26進数表記のi桁目の文字がそのまま出力すべき文字列のi番目と一致します。なので、与えられた整数nを26で割った余りを出して、それを文字に変換して、その後、nを26で割ってみたいなことを繰り返すと良さげでした。

余りを出す前にn-1することを忘れないようにしましょう。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
ll n;
cin >> n;
n--;
string ans;
while (n >= 0) {
ll a = n % 26;
n = n / 26;
n--;
ans.push_back('a' + a);
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
return 0;
}
view raw ABC171c.cpp hosted with ❤ by GitHub

私の実装だと、後ろの文字から決まっていくので、reverseを掛けてちゃんとした順番にしています。

また、今回数値→文字は26進数で0がa,1がbに対応するようになっているので、そうなるように実装しています。今回のコンテストはchar周りの出題多めですね。

4.D問題

C問題より先に解けた問題。解けたときは「いける・・・いけるぞ！！」となりました。

ぶっちゃけこれもやるだけといえばやるだけです。

数列内の各数字のカウントだけやって、その数字のカウント分配列の合計値からbを引いてあげて、cを足してあげます。その後、配列内のbと一致する数字のカウントを0にして、cと一致する数字のカウントにbを足します。これを繰り返すと通りました。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
int n;
cin >> n;
unordered_map<ll, ll> mp;
ll maxi = 0;
rep(i, n) {
ll num;
cin >> num;
mp[num]++;
maxi += num;
}
// cout << endl;
// for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
// cout << itr->first << " " << itr->second << endl;
// }
int q;
cin >> q;
rep(i, q) {
ll b, c;
cin >> b >> c;
maxi -= mp[b] * b;
maxi += mp[b] * c;
cout << maxi << endl;
mp[c] += mp[b];
mp[b] = 0;
}
return 0;
}
view raw ABC171d.cpp hosted with ❤ by GitHub

この日の朝にハッシュテーブルなるものを扱った問題を解いていたので、「ハッシュテーブルつかったるか！！」と思ってハッシュテーブルで実装しています。後で考えたら配列でもよかったです。ハッシュテーブルを使ってもやってることは同じです。最初書いた時、配列の最大値を更新するのを忘れていて、入力例1で躓いていました。

5.E問題

暗号学を研究している端くれとして、XOR系の問題は通したいと思いましたが、全く思いつかず断念しました。しかし解説を読めばすぐに理解できました。

数学の問題かなと思います。重要なのは、与えられる配列の要素の全ての排他的論理和を取ったものと、出力すべき各要素の全ての排他的論理和を取ったものは等しいという点。ここでNが偶数であることが必要です。もしNが奇数なら排他的論理和を取った後の結果は0になります。

このすべての要素の排他的論理和をSとすると、任意のaに対するbは、Sとaの排他的論理和を取ったものになります。

この問題で最も重要な排他的論理和を性質は、同じ数字の排他的論理和は0であるという点だと思います。この性質を生かして考察すれば解けたかも・・・？

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
int n;
cin >> n;
ll a[n];
ll sum = 0;
rep(i, n) {
cin >> a[i];
sum ^= a[i];
}
rep(i, n) {
ll ans = sum;
ans ^= a[i];
cout << ans << " ";
}
cout << endl;
return 0;
}
view raw ABC171e.cpp hosted with ❤ by GitHub

排他的論理和を調べていると、C言語ならa^bで排他的論理和を計算できるそうですが、C++でそれを書くとダメでした。

代わりに^=を使うとうまくいきました。std::bitsetを使わないとダメらしいです。

参考:cpprefjp – C++日本語レファレンス std::bitset

6.おわりに

F問題は無理そうだなと思って諦めました。

とりあえず、4完できたことはとても嬉しいです。しかし、E問題は暗号学の研究をしている学生の端くれとしては悔しいなと思います。

いま、やっとAtCoder ProblemsのBoot camp for BeginnersのMediumが半分を超えました。ABCのC問題を中心に解いていますが、1問にかかるスピードがEasyと比べ物にならないぐらい遅い。しかし、いろいろなことを学べるので、頑張ってMediumを終わらせます。

コメントを残す

This site uses Akismet to reduce spam. Learn how your comment data is processed.