ABC197がありました。C問題がいつもより難しかったみたいですが、私はbitsetの初期化ミスでC問題を通せませんでした。
今回はそういうところの復習です。
目次
1.A問題
3文字の文字列の先頭の文字を末尾に持っていく問題。綺麗に書いてもいいけど、めんどくさいから2文字目、3文字目、1文字目の順番にpush_backした文字列を出力させました。
解説を見ると、2文字目、３文字目、1文字目の順に標準出力すればよかったらしい。
2.B問題
二次元平面の問題は苦手です。紙に書いて考えないとわからないので。
今回は自分の位置から縦と横方向に障害物に当たるまでのマスの数を出力すればよかったので、
- 行方向に自分の位置の一つ前の位置から端まで
- 行方向に自分の位置の一つ後の位置から端まで
- 列方向に自分の位置の一つ前の位置から端まで
- 列方向に自分の位置の一つ後の位置から端まで
の4つを全てfor文で実装すればOKです。自分が立っている位置も数えるので、自分の位置から数える場合は最後に答えから3を引く必要があります。
ほぼコピペで解答ができますが、脳死でコピペすると当たり前ですが違う答えが出るので注意。
3.C問題
今回の主題です。bit全探索で全ての区切り位置を表し、全ての区間内の数にORをし、最後に全ての結果をXORしたときの最小値を出す問題。
やることは単純ですし、bit全探索さえ気がつけば実装できる・・・はずでした。
解説を見ながら書いたコードは以下の通り。
| #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> v(n); | |
| rep(i, n) cin >> v[i]; | |
| int ans = 2e9; | |
| for (int bit = 0; bit < 1 << (n - 1); bit++) { | |
| int xored = 0, ored = 0; | |
| for (int j = 0; j <= n; j++) { | |
| if (j < n) ored |= v[j]; | |
| if (j == n || bit & (1 << j)) { | |
| xored ^= ored; | |
| ored = 0; | |
| } | |
| } | |
| ans = min(ans, xored); | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |
by そして、もともと私が通したかったコードが以下の通り。
| #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 = unsigned long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| int n; | |
| cin >> n; | |
| vector<ll> v(n); | |
| rep(i, n) cin >> v[i]; | |
| ll ans = 2e9; | |
| for (int bit = 0; bit < (1 << (n - 1)); bit++) { | |
| bitset<32> x(0), tmp_ans(0); | |
| for (int i = 0; i <= n; i++) { | |
| bitset<32> tmp(v[i]); | |
| if (i < n) x |= tmp; | |
| //ビットが立っている -> 区切ってXORをする | |
| //末尾 -> 問答無用で区切る | |
| if (bit & (1 << i) || i == n) { | |
| tmp_ans ^= x; | |
| x = 0; | |
| } | |
| } | |
| ll a = tmp_ans.to_ullong(); | |
| if (a < ans) ans = a; | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |
どちらもやってる内容は同じですが、私の通したかったコードはbitsetを用いています。そして、22行目のxのビットを全て0に戻す部分でミスして、区切っているのに区切れていない状態になっていました。(しかもサンプルは全てそれで通る不思議)
3-1.整数のビット演算
整数をビット列として扱う演算子が用意されてるらしい。そのため、解説ではbitsetなんて使わずに整数のままOR演算やXOR演算を行っています。
こっちのほうがシンプル。欠点はcoutで出力するときに10進数で出力されるぐらい。だけど2進数のまま出力することはあまり無いから問題ない気がする。
3-2.bitsetを用いて全てのbitを0に設定する
今回のコードではxに0を代入することで実装しています。しかし、bitsetには関数としてreset()があるため、それを用いても同じことが実現できます。
日本語レファレンスでは"任意の位置のビットを0に設定する"と書いてあって、「任意の位置かあ・・・」と思ったので使いませんでした。
4.まとめ
AtCoderのC++入門全部読もうね！！なんかbit全探索まで解説されているぞ！！
・・・まじでAtCoderのC++入門最初からやります。