ABC200です。レーティング-15でした。やはりA~Cの早解きが緑への近道かあと思っています。そんなわけでA~D問題の復習です。E問題はいろいろな解法があるようですが、私はその議論に参加できるほど強くないので、強くなって出直してきます。
目次
1.A問題
100で割って1足すと西暦が世紀になります。注意すべきは西暦が100の倍数の時は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; | |
| cout << n / 100 + (n % 100 != 0 ? 1 : 0) << endl; | |
| return 0; | |
| } |
by 2.B問題
書かれているとおりにやるだけ問題。数値の後ろに数字を付け足す(文字列としてみたら結合)ところがネック。いちいち数値⇔文字列をやるのはめんどくさいので、結合する場合は元の数値を1000倍して200を足せば同じことができます。
| #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, k; | |
| cin >> n >> k; | |
| rep(i, k) { | |
| if (n % 200 == 0) | |
| n /= 200; | |
| else | |
| n = n * 1000 + 200; | |
| } | |
| cout << n << endl; | |
| return 0; | |
| } |
3.C問題
C – Ringo's Favorite Numbers 2
危うく死にかけた問題。通せたのでレーティングの減少が15で済んだ。通せてなかったら・・・考えたくないね。
やることはバケットソートをして、数列の先頭から、その数字に対応するバケツ内の個数-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); //入力される数列 | |
| vector<int> num(200); //バケットソートのためのバケツ | |
| rep(i, n) { | |
| cin >> a[i]; | |
| num[a[i] % 200]++; // 200で割った余りで分類して個数を数える | |
| } | |
| ll ans = 0; | |
| for (int i : a) { | |
| i = i % 200; //数列の先頭から取り出し余りっを出す | |
| num[i]--; //自分は選べないので個数から1を引く | |
| ans += num[i]; //残りの個数を答えに足す | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |
4.D問題
鳩の巣原理によって探索する区間を絞ることができるらしい。
鳩の巣原理(問題名は誕生日のパラドックスから?)はN羽の鳩をM個の巣に分ける時、N>Mであれば少なくとも1個の巣には2羽以上の鳩がいるという原理です。
今回の問題の場合、取りうる数列は通りですが、その数列の和を200で割った余りは200通りに分類できます。そのため、であるならば、鳩の巣原理を適用すると、個の数列を200通りの余りに分類するため、少なくとも和の余りが同じになる数列が2つ存在することになります。
よって、数列の長さは最大200ですが、その中から適当に8つ取り出して和の余りが一致する数列を探せばいい(全探索)となります。
| // cf) https://atcoder.jp/contests/abc200/editorial/1246 | |
| #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>; | |
| // vectorのsizeと中身を出力 | |
| void output(vector<int> &a) { | |
| cout << a.size(); | |
| for (auto i : a) { | |
| cout << " " << i; | |
| } | |
| cout << endl; | |
| } | |
| int main() { | |
| //入力 | |
| int n; | |
| cin >> n; | |
| vector<int> v(n); | |
| rep(i, n) cin >> v[i]; | |
| //鳩の巣原理より最大8個の数列だけ見れば良い | |
| int count = min(8, n); | |
| // 200通りの余りに分類 | |
| vector<vector<int>> amari(200, vector<int>(0)); | |
| // bit全探索 | |
| for (int i = 1; i < (1 << count); i++) { | |
| int sum = 0; //合計の余り | |
| vector<int> t; //選んだ番号 | |
| for (int j = 0; j < count; j++) { | |
| if (i & (1 << j)) { | |
| // bitが立っていたら入れる | |
| t.push_back(j + 1); | |
| //合計の余りの計算 | |
| sum += v[j]; | |
| sum %= 200; | |
| } | |
| } | |
| //同じ余りになったらどっちも出力 | |
| if (amari[sum].size() != 0) { | |
| cout << "Yes" << endl; | |
| output(amari[sum]); | |
| output(t); | |
| return 0; //[注意!]忘れない | |
| } else { | |
| //新出なら分類に加える | |
| amari[sum] = t; | |
| } | |
| } | |
| cout << "No" << endl; | |
| return 0; | |
| } |
解説を読んだ時、なんて頭のいい解法なんだ！！と思いました。全探索っぽいけど最大の数列を全探索したら確実にTLEだから、DPか？と思ってググってましたが、こうやって探索範囲を絞れるとは驚きです。
研究室で暗号学的ハッシュ関数をやってた時期もあったので、誕生日のパラドックスは知ってたのですが、競技プログラミングでこういう形で出てくるとは。
twitter見ていると、強い人には典型だったらしいので覚えておこう。
5.おわりに
レート-15でしたが、楽しいコンテストでした。Cはもっと早く通すべきでした。
このコンテストの前に過去問をやっていて、ABCの茶色の問題は全て解き終わりました。ただ、緑になるためにはA~C問題の早解きが重要なのでどう練習すればいいんだろう？と思っています。もう一度C問題を解き直して分類するのは手間だし・・・。
とりあえずいい加減解法集はつくらないとなあ。そういえば強い人が典型問題コンテストやってるし、それをやるのもありか。
どうでもいいですが、VScodeのエディタからターミナルへフォーカスするショートカットキー、Shift+0は辞めたほうがいいです。めっちゃ誤爆します。