解答 根付き木において、頂点 a, b 間を辿る最短パスはの最も近い共通祖先の頂点である。よって LCA を用いて、頂点 a までの深さ + 頂点 b までの深さ - 2*共通祖先の頂点 + 1 が答えとなる。 まだ自力でLCAを書くことが出来ないので蟻本そのままのコードを…

解説 いもす法。 まず一次元で状態が変わる点をイベントとしてみて、カウンタ +1, -1 の増減を設定する。O(N) 累積和を取り、実際の状態の遷移状況を求める。O(N) よって全体で O(N) #include <bits/stdc++.h> using namespace std; #define MAX (1000000) int imos[MAX+10]</bits/stdc++.h>…

解説 状態を２進数値化して考えて、指定の位置にビットが立っているかどうかで N 個の ON / OFF を調べる手技。 X と (1 論理積が 0 でないなら、i 番目にビットが立っている。 #include <bits/stdc++.h> using namespace std; int main() { int N, X; cin >> N >> X; int s</bits/stdc++.h>…

解説 足りない分は b - (a を b で割った余り) である。 数が余らない時は 0 を出力するのに気をつける。 #include <bits/stdc++.h> using namespace std; int main() { int a, b; cin >> a >> b; cout << ((a%b) ? b-a%b : 0) << endl; return 0; }</bits/stdc++.h>