3完。ADBの順にやった。難しかった。
No.682 Average
iの範囲が決まってるし数字も小さいので、ループで数えるだけ。計算量のオーダーを落とす方法が存在するので怖い見た目になってる(そのことは考えずに解いた)。
No.683 Two Operations No.3
色々いじってみるも全然解ける気配がない。逆からやるのも考えたが見えない。糸口もつかめないので他の問題へ。
Dから帰ってきて、もう時間があんまりない。とりあえず逆からDFSを投げてTLEしないことを祈ってみよう。実装して提出するとMLE!?DFSの深さがってことか。そういえば123 0みたいなケースは考えてたのに忘れてた。片方が0になったら終わるように修正して投げるとAC。これでTLEしないことをまだ証明できない。
No.684 Prefix Parenthesis
Bのあとの(終了までの)数分考えただけ。でかい山を作りたいのだと思ったが、一定以上の谷もあっちゃいけないしどうするんだろ。
No.685 Logical Operations
XORなのでこれをやった。まずAND<=ORなのはわかる。それどころかXOR<=ORも言える。等号がポイントか。両方1なビット位置があればいい。XORは最上位ビットが打ち消し合うとANDより小さくなるので、yの最上位ビットの位置のxは0だ。
つまりそういうのを数えればいい。いけそう。ああそうか、Nが半端な値だから面倒なんだ。Nが2冪なら、yの最上位ビットの位置で場合分けしていける。そうでないときも半端なぶんを下位から2冪個ずつ数えていけばいい。具体的には、両方1な位置が存在しない場合の数を全体から引く。それだけ。でも実装が全然できなかった。何から手をつけていいのか全くイメージが湧いてこない。コーナーケースのことを思うと頭がどん詰まりになる。脳がのっぺりする。何も感じない。起伏がなければコードは書けない。最終的にはACできてよかった。