string rev(string s){ reverse(ALL(s)); return s; } string prefix_palindrome(const string& s){ VI pref(s.size()*2 + 10); string a = rev(s); a = s + "#" + a; ll c = 0; for (int i = 1; i < (int)a.size(); i++){ while (c != 0 && a[c] != a[i]) c…

Quiz https://codeforces.com/contest/1352/problem/E AC https://codeforces.com/contest/1352/submission/88534343 解説 editorialとは別解法 すべての範囲 l ～ r について和を求めて、作れるかをフラグで持っておく。和を求める高速化には累積和を使う …

Quiz https://codeforces.com/problemset/problem/1370/C AC https://codeforces.com/contest/1370/submission/88162228 解説 想定解(editorial)と違うので書いておく 相手に負け確定の状態で渡すことができるなら勝ち、そうでないなら負け これをメモ化再帰…

Quiz https://codeforces.com/problemset/problem/1362/C AC https://codeforces.com/contest/1362/submission/88153884 解説 例としてN=11を見てみましょう。2進数で書いていって、0,1の切り替わる箇所の和が答えです 切り替わる間隔が2倍ずつ増えていくこ…

Quiz https://codeforces.com/contest/1351/problem/C AC https://codeforces.com/contest/1351/submission/88145828 解説 訪れたpathを再度通るなら1秒で通れる。訪れた「マス」じゃないよ！ {x1, y1, x2, y2}の情報でパスは表現できる。具体的にはpairや構…

数列Aがあり、添字i, jについての条件式があり、左右にiごと、jごとに移行するといい感じになるやつ ソートしたり 数列A, Bが数列Cに合体したり 問題集 D Pair of Topics (1400) https://codeforces.com/contest/1324/problem/D AC https://codeforces.com/c…

I used multiset＜int＞ and used upper_bound N=200000 times, and TLE (time limit error) https://codeforces.com/contest/1324/submission/87940679 I searched in Twitter, and it seems count is also slow

Quiz https://codeforces.com/problemset/problem/1250/A AC https://codeforces.com/contest/1250/submission/87667768 問題解説 1番目に1番の投稿、2番目に2番の投稿、... と最初なっている 各投稿に「いいね」が付くと、その投稿は1つ上の表示になる M個…

Quiz https://codeforces.com/contest/1108/problem/D AC https://codeforces.com/contest/1108/submission/87500494 解法 (公式editorialがないので書いておく) dp[i][j] i文字まで見て、そこで使った文字がjであるときの最小の交換回数 dpテーブルサイズは…

Quiz "D. Diverse Garland" https://codeforces.com/contest/1108/problem/D AC https://codeforces.com/contest/1108/submission/87499830 問題の内容は重要ではないのですが、コーディング中のデバッグ表示に以下のコードを使いました void debug_vector(V…

// 正しい括弧列か？ bool is_right_parenthesis(string s){ ll L = s.size(); ll a=0; for(char c : s){ if(c=='(') a++; } ll b=L-a; if(a!=b) return false; ll cur=0; for(char c : s){ if(c=='('){ cur++; }else{ cur--; } if(cur<0) return false; } r…

Quiz https://codeforces.com/contest/1107/problem/C AC https://codeforces.com/contest/1107/submission/87383623 解説 設定が分かりづらかった K=3でs="aaaaaaaaaa"の時は、どれか7つのaをスキップしなければいけない(スキップしてもボタンの疲労は回復…

Quiz https://codeforces.com/problemset/problem/1090/A AC https://codeforces.com/contest/1090/submission/87366503 解法 各会社のMax給料の人が重要 最終的にはすべての会社をMergeするのだから、各会社のMax給料が一致するところまで、各会社の給料を…

Quiz https://codeforces.com/problemset/problem/1070/D AC https://codeforces.com/contest/1070/submission/87337427 解説 今日のゴミはまだ出さない 昨日のゴミは出さないと行けないので袋を使って捨てる。その時に袋の容量に余りがあれば今日の分のゴミ…

// できること // 一点追加 // 範囲和 // ei1333's BIT struct BIT { VI data; BIT(ll sz) { data.assign(++sz, 0); } // sum of [0,k] ll sum(ll k) { ll ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return (ret); } // [i, j] ll range_sum(l…

Quiz https://codeforces.com/contest/1335/problem/D AC https://codeforces.com/contest/1335/submission/87041995 My answer

Quiz https://codeforces.com/problemset/problem/1343/C AC https://codeforces.com/contest/1343/submission/87007538 解法 配列を正負で分割してそれぞれでMaxをとる code // 正負で分割 // 例 1 2 3 -1 -2 => {1,2,3},{-1,-2} VV f(VI& A){ ll N = A.siz…

Quiz https://codeforces.com/contest/1205/problem/A 問題の意味 Nが与えられる 1 ... 2Nまでを円状に配置し、隣接N個の和をすべて求めた時、どの和のペアを見ても差が1以下となる配置を構築せよ ないなら -1 AC https://codeforces.com/contest/1205/submi…

Quiz https://codeforces.com/problemset/problem/1191/B AC https://codeforces.com/contest/1191/submission/86908550 解説 実装やるだけなのですが、与えられた3枚のカードを数字に置き換えることで差が考えやすくなるという気づきがあった int main(){ /…

Quiz https://codeforces.com/contest/1084/problem/B 感想 問題文の理解が1番難しい N個の樽があり、酒を抜いていくが、酒の高さの最小値ができるだけ高くなるようにして実現できる高さを答えればいい 算数で解ける 「最小値の最大化」なので、二分探索でも…

Quiz https://codeforces.com/contest/1362/problem/B AC https://codeforces.com/contest/1362/submission/86646585 解法1 kをbit全探索 210未満を調べればいい。それ以上をXORすると父に絶対にバレる 解法2 (editorialの別解として書かれている) サンプル…

Quiz https://codeforces.com/problemset/problem/1311/B AC https://codeforces.com/contest/1311/submission/86604199 解説 各値はどこに移動したいのか求めるために、(value, index)の組でvectorに入れてsortする iからjに移動したいと分かったとして、そ…

Quiz https://yukicoder.me/problems/no/844 AC https://yukicoder.me/submissions/508731 dpテーブル VI dp(N+5, -A); // 最後に引いた線がiのときの最大スコア dp[0] = 0; 解説 右端ごとにまとめて、右端が小さいものから処理してDP マスに番号があります…

rank付きUFとは違う。rankは木の高さなので サイズはグループの根に保存されるとする size : 木の頂点数 統合ルール sizeの大きい方に統合する sizeが同じ場合は数値の小さい方に統合 // サイズ付きUF struct UnionFind{ VI parent; VI size; // グループの…

Quiz https://yukicoder.me/problems/no/1102 AC https://yukicoder.me/submissions/508089 editorialを補足します 寄与について 組み合わせ nCr について Kが大きいので競プロでおなじみの方式ではなく、漸化式を使う メモ化再帰する 漸化式にはnを減らすも…

Quiz https://yukicoder.me/problems/no/1071 AC https://yukicoder.me/submissions/507889 解法 三分探索（想定解ではない） 全部ベホイミが最適：左のグラフ 全部ベホマラーが最適：中央のグラフ 丁度いいベホマラー回数がある：右のグラフ 下に凸のグラフ…

https://yukicoder.me/problems/no/1101 こちらの問題の解説を図示してみました。黒い波打つ線が鼻水の余裕量で、0を下回るとアウトです 波線を下で支えるサポートラインを考えると、何回鼻をすすることができるかが求められます

部分永続Union Findとも言うらしい 各uniteしたときに時刻が1進むとして、各時刻での連結情報が取れる、記憶力の良いUF // cf : https://misteer.hatenablog.com/entry/persistentUF // 永続UF struct PersistentUnionFind{ VI parent; // 親ID VI time; // …

自分検索用に上記タイトルにした code // 山登りの最大負荷 // A[i] = -1 or 0 or 1 // 最大上昇を返す ll max_fatigue(VI& A){ ll ma=0; ll cur=0; ll N = A.size(); rep(i,N){ cur += A[i]; chmax(ma, cur); if(cur<0) cur=0; } return ma; } what is this…