公式解説動画のとおりに実装。 ちなみに22k mod p (pは素数)はフェルマーの小定理より 22k mod (p-1) mod p で求まる。 vector<vi> dp; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); int N, M; while (cin >> N ></vi>…

とりあえず、頂点を座標の昇順に並べておく。以下のように構成できる。 int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); int n; cin >> n; vll b, r, p, xs; rep(i, n) { ll x; cin >> x; char c; cin >> c; if …

エディトリアルの通り。j<iまで見てxorsumで作れる集合をSとする。a[i]∈Sのとき、x∈Sであればa[i]⊕∈SなのでSの元はそのままで、各元の構成の仕方が2倍になる。a[i]∉Sのとき、x∈Sならばa[i]⊕x∉Sなので、集合にa[i]⊕xを加えるだけ。|S|が2倍になる。 int main() { int N, Q; cin >> N >> Q; vi A(N); rep(i, N)cin >> A[i]; set<int> S; S.insert(0); mint val = 1; vi L(Q), X(Q); vector<vi> qs(N); rep(i, Q) { cin …</vi></int></iまで見てxorsumで作れる集合をsとする。a[i]∈sのとき、x∈sであればa[i]⊕∈sなのでsの元はそのままで、各元の構成の仕方が2倍になる。a[i]∉sのとき、x∈sならばa[i]⊕x∉sなので、集合にa[i]⊕xを加えるだけ。|s|が2倍になる。>

まず最上位ビットについて考えてみよう。最上位ビットが異なる頂点同士を結ぶと、ほかの全てのビットが異なる頂点同士を結ぶよりも高コストなので、できるだけ少なく済ませたい。そこで0b0???のグループと0b1???のグループに分けてそれぞれ木になっていると…

辞書順最小にしたいので先頭からbの値を決めていく。 とりあえず、aの要素を使える限り使っていく。 例えば、入力例2は a={10, 3, 7} b={10, 3, 7} b[i]をa[i]の要素として使えるかどうかを判定するには、あらかじめ十分大きな素数の集合を用意しておく。a[i…

int N, K, M; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); cin >> N >> K >> M; // 各単語の番号 map<string, int> id; rep(i, N) { string s; cin >> s; id[s] = i; } // 各単語の送信コスト vi A(N); rep(i, N)cin >> A</string,>…

Nのパリティを見る。 (1) Nが偶数のとき 最初のターンでMahmoudがN個取ってMahmoudの勝ち。 (2) N >= 3 かつNが奇数のとき 最初のターンでMahmoudは2<=a<N個の偶数しか取れない。よってEhabのターンでN-a個は奇数であり、EhabがN-a個取って勝つ。 (3) Nが1のとき 最初のターンでMahmoudは何もできないので、Ehabの勝ち。 int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); int n; cin >> n; cou…</n個の偶数しか取れない。よってehabのターンでn-a個は奇数であり、ehabがn-a個取って勝つ。>

キングが中心にいる場合、キングから周囲のマスまでの移動は 22222 21112 21012 21112 22222 のようになっている。距離1のマスは45度回転すると のようになる。 すべて整数で表すために√2を掛けると 座標は(2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -…

素朴に考えると dp[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最大profit のようなDPを得る。 例えば、サンプルの入力で6, 8を使うと dp[2][8] = 6*8 のようになる。 この方法には問題が3つあるが、どれも対処できる。 (1) profit fac…

左から要素を見ていく。 a[i] > a[i+1]であるような隣接する2つの要素を見つけた場合、対処は2種類ある。 (1) a[i]の値を小さくする。 これができるのは i = 0の場合、もしくはi>0かつa[i-1]<=a[i+1] の場合のみ (2) a[i+1]の値を大きくする。 具体的にはa[i…

入力に応じて3種類に場合分けする この3種は入出力例で示されているのでそれを使って説明する。 1) |S| < 26のとき 使われていない文字で最小の文字を末尾に追加する。 入力例1のatcoder ではbが使われていないので末尾にbをつけて atcoderbが解となる。 入…

気づき 操作はkの降順だけ考えれば良い。 vに対して整数k1で操作したあとk2で操作したとする。 k1 <= k2を仮定する。 vをk1で割った余りv'は v' < k1 を満たす。 k1 <= k2より v'をk2で割った余りもv'である。よってk2による操作で値が変わらず、 k2の操作が…