アルゴ式で間違えた問題(ビット)
ビットシフトの用いて 2のN乗を計算する問題
2の累乗に釣られて 2<<N-1 としてしまったので N=0のときにエラーがでた。ビット演算そのものが2の累乗だった。1を左シフトしてN回左に移動させるイメージ
ビット演算を用いて任意の桁を変える
ビット列を電球のONとOFFの状態とみなし、電球を切り替える問題 algo-method.com
状態をSとし、x桁を1にしたければ
S = S | 1<<x;
とすればいいのはわかった。ではx桁を0にしたければ何をすればいいか。1への変換と同様に(文法ミスしてるが)x桁を0にしてANDをとればいいかと思ってしまった
S = S & 0<<x;
しかし、これだとx桁は0になるが、他の桁も全部0になってしまう。x桁だけ0にし、残る桁は1にしてANDを取るといい。よってNOT演算を使った下のように考えればよかった。
S = S & ~(1<<x);
XOR で電球の状態管理
bit のフラグ管理を理解してなかった。フラグが立っているか立っていないかや、bitの操作などの慣れが甘い。今回も、 XOR の操作に釣られて
if (A ^ 1<<i) { // }
などと書いてしまった。本来はこう書くべきだった。
if (A & 1<<i) { // }
A & 1 << 1
は下の図のようにあるビットに着目してそれが1か0かを確かめるものと考える。
フラグ状態の復元
問題の条件としてフラグの個数は30個縛りであることを見落としていたため、入力された値をそのまま精査してたら1つの問題に2秒かかり時間切れになるなどとんでもない事態になった。また、配列を30個作る必要なくて、まず空の配列を作り、条件にマッチしたら配列に追加するという方法(push_back)を取ればよかった。(C++慣れてなくてこんな発想すらできなかった。標準ライブラリもメソッドも何も提供されてないイメージだから当たり前があるのに驚きだよ。) また、配列の範囲外アクセスによりランタイムエラーが多発した。
フラグをまとめて消す
真理値表を書けば一発でわかるのだろうけど、0001 という真理値表を回路に変換する方法がわからなかった。次もその次の問題も真理値表で考えれば解けそうな問題だから論理回路を復習したい。『ビジュアル 論理回路』という本が良さそうなレビュー。
フラグが全て立っているかどうか
真理値表を作って11のところが1だったので、AND回路かと思った。でも、問題文を言い換えるとMと一致するかどうかという条件に書き換えれるので、必ずしも真理値表を使えばいいという話ではないことが学び。出題例を見ても真理値表の問題のときの書き方ではなかったから、メタ読みで気づけばよかった。
初項が与えられている等差数列
0,1番目に初期値が与えられているならそれをforループ外で代入しておけばよかった。forをi=2から始めれば良かった。
for(int i=0; i<N; i++) { if(i ==0){A[0] = X} else if(i==1) {A[1] = Y} else{} }
ではなくこんな感じ
A[0] = X A[1] = Y for(int i=2; i<N; i++) { A[i] = }
タイルの敷き詰め
「最後行動で場合分け」というのがポイント。階段の登り方の場合わけも、最後の行動で場合わけ。