最近全く記事を書いていませんでしたが、コンテスト自体は予定がない限り参加しています。今回のABC206では15分以内に3完して緑パフォ取れたのでレートが伸びましたが、レート-100を未だに返せていなくて辛いです。
今回はD問題でアホなミスをして通せなかったので反省も兼ねて記事を書いています。
目次
1.A問題
消費税8%を含んだ価格(ただし小数点以下は切り捨て)が定価の206円と比較してどうかという問題。床関数を使ってもいいですが、普通にint型の演算で実装したほうが楽です。
小数点を含んだ問題は心臓に悪いから嫌い。
| #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; | |
| n *= 1.08; | |
| if (n < 206) | |
| cout << "Yay!" << endl; | |
| else if (n == 206) | |
| cout << "so-so" << endl; | |
| else | |
| cout << ":(" << endl; | |
| return 0; | |
| } |
by 2.B問題
問題:B – Savings
i日目にi円貯金した時、貯金額がN円を初めて超えるのは何日目かという問題。1から順に足し合わせてNを超えたら出力すればACできます。
| #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 money = 0; | |
| rep2(i, 1, 1e10) { | |
| money += i; | |
| if (money >= n) { | |
| cout << i << endl; | |
| break; | |
| } | |
| } | |
| return 0; | |
| } |
3.C問題
数列があった時、ある番目より後ろにある要素の中で、その番目の数字と違う数字が何個あるか、それの和を求める問題。
真面目にやると死ぬ制約条件になっているので、hash_tableを使って高速化します。
数列内の各要素をそれぞれ数え上げます。この時hash_tableを使うと楽。その後、数列内の前から数字を取り出し余事象を計算します。その余事象の和が答えになります。数列を進む時、余事象の計算に用いる全体の大きさが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() { | |
| int n; | |
| cin >> n; | |
| vector<int> a(n); | |
| unordered_map<int, int> mp; | |
| rep(i, n) { | |
| cin >> a[i]; | |
| mp[a[i]]++; | |
| } | |
| ll ans = 0; | |
| for (int num : a) { | |
| ans += n - mp[num]; | |
| mp[num]--; | |
| n--; | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |
4.D問題
数列をある操作をして回文にする時、最小操作回数を求めよという問題。ある操作とは、ある数字を選んで数列内の同じ数字をすべて別の数字に変えるというもの。
私は最後までしょうもないミスでREが取れず死んでいました。
数列内で回文になっていない箇所の数字を無向グラフとして持っておきます。その無向グラフに対してBFSやDFSを行ったときの連結要素の数の和が答えになります。
私のやらかしは、無向グラフのサイズをnにしていたことです。nは数列のサイズであり、グラフのサイズは数列に含まれる中で最大の数より大きくなければいけません。そのため、セグフォしてREになったようです。
教訓: グラフのサイズは制約条件の最大に固定しておく
| #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>; | |
| using Graph = vector<vector<int>>; | |
| constexpr int MAX = 200005; | |
| vector<bool> arrive; | |
| ll dfs(const Graph &G, int v) { | |
| ll count = 0; | |
| arrive[v] = true; | |
| for (auto next_v : G[v]) { | |
| if (arrive[next_v]) continue; | |
| count++; | |
| count += dfs(G, next_v); | |
| } | |
| return count; | |
| } | |
| int main() { | |
| int n; | |
| cin >> n; | |
| vector<int> a(n); | |
| rep(i, n) cin >> a[i]; | |
| vector<int> b; | |
| b = a; | |
| reverse(b.begin(), b.end()); | |
| Graph G(MAX); | |
| arrive.assign(MAX, false); | |
| rep(i, n) { | |
| if (a[i] != b[i]) { | |
| G[a[i]].push_back(b[i]); | |
| G[b[i]].push_back(a[i]); | |
| } | |
| } | |
| ll count = 0; | |
| rep2(i, 1, MAX - 4) { | |
| if (arrive[i]) continue; | |
| count += dfs(G, i); | |
| } | |
| cout << count << endl; | |
| return 0; | |
| } |
5.おわりに
最近着実にレートをプラスにしていますが、未だにhighestを更新できません。一時期レートを40や50下げていたことがあったのでその影響が大きいです。今回D問題を通せていればhighest更新が狙えたのですが、しょうもないミスでだめでした。来週がんばります。