出入り口に使う面の組、行の組（列の組）ごとに操作回数を考える。具体的には頭の中でサイコロを回転させつつ展開図に操作回数や行または列の対応を書き込んでいく。すると上のような図を得る。あとは最小値を計算するだけ。 // faceA, faceB, rowA, rowB, c…

int N, K, D; cin >> N >> K >> D; vi A(N); // とりあえずソートしておく rep(a, N)cin >> A[a]; sort(all(A)); vi in(N+1), out(N+1); // 小さい方から0個をすべて使って箱詰めできている in[0] = 1; out[0] = 1; ll cur = 0; rep(a, N) { cur += in[a]; /…

構成のベースは以下の２通り。 適切な最大の高さxは二分探索で求める。この通りに構成したときに、余りが出る場合があるが、x以下のすべての高さが存在するので、余りをrとするとceil(r/x)個だけ同じ高さの横に挿入すればいい。 // Hが大きすぎても無意味な…

int N, K, L; cin >> N >> K >> L; int M = N*K; vi A(M); rep(a, M)cin >> A[a]; sort(A.rbegin(), A.rend()); // 必ずできる一番小さい樽の大きさで制限 ll lim = (ll)A.back() + L; ll re = 0; // 使ってない板の数、作った樽の数 int cnt = 0, taru = 0;…

起こす人uから起こされる人vへ辺(u, v)を張るようなグラフを考える。このグラフは閉路があってややこしい。とりあえず強連結成分分解してみよう。各強連結成分において誰か一人でも起きれば、その強連結成分内において全員が必ず起きる。よって強連結成分S内…

N=32とする。1<=v<w<=31としてを満たすすべての辺(v, w)の辺を貼ると1から2<=x<=31までの経路の和は2x-2通りである。これは経路数をf(x)と表すと f(x) = f(1) + f(2) +...+ f(x-2) + f(x-1) = (f(1)+f(2)+...+f(x-2)) + f(x-1) = f(x-1) + f(x-1) = 2f(x-1)であるため。よってKを2進数として各桁をみてk(>=0)ビット目が立っていたら頂点k+2から頂点Nに辺を張ればよい。 int K, N = 32; cin >> K; vector<pii> E; for (int w =…</pii></w<=31としてを満たすすべての辺(v,>

/** 2以外の素数はすべて奇数 x*x<=Kであるような最大のxを考える。 a+bが奇数であるような偶数aをx個と奇数bもx個使って 素数がx*x個作れる。 K' = K-x*x としてK'に対しても同様に繰り返していけばいい。 以前に使った偶数、奇数に対しては素数を作らない…

http://codeforces.com/blog/entry/59484?#comment-431237 これを見てそのとおりに書いた。 using P = array<int, 7>; static bitset<2001> vis[10][10][10][10][10]; int N; cin >> N; vi A(N), B(N); rep(a, N)cin >> A[a] >> B[a]; queue<P> Q; Q.push({ 0,0,0,0,1,0</p></int,>…

ll p, q, b; cin >> p >> q >> b; ll g = gcd(p, q); // とりあえず約分 q /= g; // 分母をb^kの形にできればOK // そのためには分母qをgcd(b, q)で割り続けて // bと互いに素な素因数をもつかどうか判定する string re = "Finite"; while (q > 1) { ll h = …

/** 実験すると各引数が二項係数と同じ個数だけxorに使われることがわかる。例えば f(1, 2, 4, 8) = (1)⊕(2⊕2⊕2)⊕(4⊕4⊕4)⊕(8) であり、各引数はC(3, 0), C(3, 1), C(3, 2), C(3, 3) 回だけ使われている。 xorは同じ整数同士で打ち消し合うので二項係数の偶奇…

/** Flowrisa から Beetopiaへのパスの辺を 取り除いたグラフを考えよう。このグラフは少なくとも2つの部分木からなり、 1つはFlowrisaを含み、もうひとつはBeetopiaを含む。 もとのグラフにおいてFlowrisaを含む部分木からBeetopiaを含む部分木 への経路だ…

const string ALPHA = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; string NAME[3] = { "Kuro", "Shiro", "Katie" }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); ll N; // 0<=N<=10^9 cin >>…

公式解説みて書いた void dfs(int u, int p, int d, vector<vi> &H, vi &dist, vi &score) { dist[u] = d + score[u]; each(v, H[u])if (v != p) { dfs(v, u, dist[u], H, dist, score); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fix</vi>…

(x[j], y[j])を辺とするようなグラフを考える。このグラフの各連結成分内では要素は各辺を介したスワップによって自由に配置できる。よって頂点iを含む連結成分にp[i]が含まれるかを調べればいい。連結成分の識別にはUnion Find木を使うと便利。 int N, M; v…

priority queueに(s[i,i], i), 1<=i<=Nを挿入していく。あとは先頭の要素をとってきて右端を1個伸ばしたものをpriority queueに挿入していく。ダイクストラ法で辺によって隣接する頂点を追加するのに似ている。s[l, r] <= s[l, r+1]なのでs[l, r]が取り出さ…

隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。 この問題では、白と黒の２色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方につい…

よい盤面である条件は、1<=i<=Nについてi行目とi列目が等しいことと同値。例えばN=4については、以下が等しければよい。 更にこの図から、任意の自然数の組(A, B)について(A+x, B+x) (xは自然数) も(A,B)と比較対象が同じであることがわかる。たとえば、(A, …

公式解説動画のとおりに実装。 ちなみに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の操作が…

問題 N行M列, カード 初期状態: すべて表 すべてのカードについて、そのカードと周囲8枚のカードを裏返す 最終状態の裏のカードを数えよ 1解説 カードが十分多いとき ほぼすべてのカードが自分と周りの計9枚によって裏返される よって裏 あとは残りのカード…