自己紹介
- 中学3年生
- AtCoderレーティング：952
- AtCoder始める前まではScratchをやってた
- 2021年6月にAtCoderを始め、2023年6月に入茶、2023年10月に入緑
- C++er
- 数学1Aは分かります
AtCoderや競技プログラミングとは？
- Algorithm部門のRating 800以上期待できる能力
コーディングの安定感、速さに信頼がおけます。計算量への意識も高く、ボトルネックとなる箇所において、実行時間がとても遅いプログラムを書いてしまう、などといったことも少なくなります。 (https://info.atcoder.jp/utilize/jobs/rating-business-impact より引用)
論理演算
- $a$ or $b$
| $a\b$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
- $a$ and $b$
| $a\b$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
- $a$ xor $b$
| $a\b$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
ビット演算
ビット演算は、論理演算を$2$進数の各位の数に対して行います。
例えば
$
a = 0101_{(2)}
b = 0110_{(2)}
$
とすると、$a$ and $b$ は
| $a$ | $0$ | $1$ | $0$ | $1$ |
|---|---|---|---|---|
| $b$ | $0$ | $1$ | $1$ | $0$ |
| $a$ and $b$ | $0$ | $1$ | $0$ | $0$ |
となり、$a$ and $b$は、$0100_{(2)}$となります
C++での書き方
$a$ and $b$
a & b
$a$ or $b$
a | b
a xor b
a ^ b
- 左シフト演算
0110110_{(2)}
これを$2$ビット左シフトすると、ビット列が$2$回左にずれ
1011000_{(2)}
はみ出たビットは切り捨てられ、右は$0$が埋められます。
C++で書く時、intは$32$ビットでlong longは$64$ビットの整数であることに注意する必要があります。
実は$k$ビットの左シフトは$10$進数の時に値を$2^k$倍した値と等しくなっています。
(ビットがはみ出さない場合)
C++で$n$を$k$ビット左シフト
n << k
k番目のbitが立っているか調べる
さっき書いたand演算と左シフト演算を使って実装できる。
#include <iostream>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
if (n & (1 << k)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
例えば$n=10_{(10)}=1010_{(2)},k=4$の時
| $n$ | 1 | 0 | 1 | 0 |
|---|---|---|---|---|
| $1$ << $k$ | 1 | 0 | 0 | 0 |
| $n$ & ($1$ << $k$) | 1 | 0 | 0 | 0 |
となります。C++では0以外の数値はすべてtrueになるので、$1000_{(2)}$は、trueと判定され、Yesが出力されます。
ここでは省略していますが、int型は32ビットの整数なので、$n$は$1010_{(2)}$の前に$0$が$28$個続いています。
入力と出力は$10$進数です。
bit全探索
問題文
駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。
切符には
4 つの 0 以上 9 以下の整数 $A$,$B$,$C$,$D$ が整理番号としてこの順に書かれています。$A$ $op1$ $B$ $op2$ $C$ $op3$ $D$ $=$ $7$ となるように、$op1$,$op2$,$op3$ に $+$ か $-$ を入れて式を作って下さい。
なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。
(https://atcoder.jp/contests/abc079/tasks/abc079_c より引用)
$op1$,$op2$,$op3$を全部調べれば良さそうです。$op1$,$op2$,$op3$の全ての組み合わせは
| $op1$ | $op2$ | $op3$ |
|---|---|---|
| - | - | - |
| - | - | + |
| - | + | - |
| - | + | + |
| + | - | - |
| + | - | + |
| + | + | - |
| + | + | + |
この+と-は1と0に置き換えられて
| $op1$ | $op2$ | $op3$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
このように書けます。そして、この0と1の組み合わせを1桁のbitと捉えると、
3桁のbit列$000_{(2)}$から$111_{(2)}$を順番に足していきながら調べればいいことがわかります。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
for (int i = 0; i < (1 << 3); i++) {
//↑000から1000まで調べるよ(ただし < なので1000は入らず、1000-1の111まで)
int n = s[0] - '0';
//↑文字を整数に変換するテクニック 文字 - '0' です。
vector<char>ans(3);
//↑組み合わせ(+か-)を配列に保存しておく(出力するときに便利)
//↓各(iの)組み合わせの時にそのbitが立っているか(それが+か-か)を調べるよ
for (int j = 0; j < 3; j++) {
if (i & (1 << j)) {
//bitが立っている(+)
n += s[j + 1] - '0';
ans[j] = '+';
}
else {
//bitが立っていない(-)
n -= s[j + 1] - '0';
ans[j] = '-';
}
}
if (n == 7) {//もし結果が7だったら出力して終了
cout << s[0] << ans[0] << s[1] << ans[1] << s[2] << ans[2] << s[3] << "=7" << endl;
return 0;
}
}
}
ACコード
https://atcoder.jp/contests/abc079/submissions/48663937
終わりに
最後まで読んでいただきありがとうございます。
実は前日の夜までほぼ手を付けていなかったというのはナイショで、、、
というわけで今まで競プロやっていなかった人も、競プロがどういう感じなのかな～っていうことがわかっていただけたらと思います。
では私は引き続き競プロがんばります
明日は rinrin 24 さんの FC2ホームページにGitHubからファイルをアップロードする です。