Quiz https://codeforces.com/problemset/problem/1209/D AC https://codeforces.com/contest/1209/submission/91176952 解説 連結成分ごとに見たとき、「連結成分内のノード数-1」が幸せになる客の数、逆に言えばそれ以外の客は sad になる その他 「入次数…

is_subset /* b is subset of a a = 11001010 b = 01001000 => true */ bool is_subset(ll a, ll b){ ll c = (~b | a); if(c==~0LL){ // 11111111 return true; }else{ return false; } } A. Marcin and Training Camp Quiz https://codeforces.com/contest/…

Quiz https://codeforces.com/contest/1215/problem/D AC https://codeforces.com/contest/1215/submission/91168942 解説 editorialと違う解法 左の数字の和＝＝右の数字の和の時は自明とし、以降は数字の和に差があるものとする 左の？が多いとする（違う…

Quiz https://codeforces.com/contest/1219/problem/C AC https://codeforces.com/contest/1219/submission/91093006 解説 ...はeditorialの通りなので書きません 解法は簡単に思いつきますが、コーナーケースがあります。与えられる文字列sの長さをNとして…

Quiz https://codeforces.com/contest/1256/problem/C AC https://codeforces.com/contest/1256/submission/91006703 解法 最大ジャンプを繰り返した場合、その長さの川まで渡れるかは求められる。それが足りないならNO 足りている場合、platformの間隔を詰…

Quiz https://codeforces.com/contest/1260/problem/C AC https://codeforces.com/contest/1260/submission/91003892 解説 r==gの時はOBEY それ以外のとき、空白を除去するためにgcdで割る r>gとする rとrの間に、gを最大に詰め込んだ場合に何個入るかを考え…

Quiz https://codeforces.com/contest/1295/problem/B AC https://codeforces.com/contest/1295/submission/90787038 解説 editrorialとは別の解法 波船が上下しながらxという上にあるバーに迫っていくイメージだが、逆にxのバーが下に下がってくると考える …

Quiz https://codeforces.com/problemset/problem/1310/A AC https://codeforces.com/contest/1310/submission/90780105 解説 editorialではmultisetを使っていたが、私はpriority_queueを使った サンプル1を見れば分かるように、Aの小さい方から見ていって…

Quiz https://codeforces.com/contest/1009/problem/C AC https://codeforces.com/contest/1009/submission/90329549 解説 xは位置に関係なく均一に足されるのでまとめて考えられる dが正の時は i をはじっこに、 dが負の時は i を真ん中に置けばいい その他…

Quiz https://codeforces.com/contest/1036/problem/B AC https://codeforces.com/contest/1036/submission/89997834 解説 できるだけ斜め移動しようとしたとき、X回目にいれる座標には制限がある。逆にその座標なら全て斜めで行ける 目的地までの大抵の移動…

Quiz https://codeforces.com/problemset/problem/1045/I AC https://codeforces.com/contest/1045/submission/89811807 解説 たとえばaabとbは同一視できる 各文字の偶奇のみに意味があり、各文字列は26文字をフラグとした整数値として表せる 回文を作れる…

Quiz https://codeforces.com/problemset/problem/1056/B AC https://codeforces.com/contest/1056/submission/89797233 解説 mが小さく、m x mの範囲なら全探索できる。その中で条件を満たす座標を見つけた時、それに対応する座標がm x mより向こうの範囲に…

Quiz https://codeforces.com/contest/1056/problem/D 解説 色を塗るのは葉だけ 辺の与え方が見慣れない形式 解法は、各頂点以下の葉の個数を調べ、それをソートする sample 2

Quiz https://codeforces.com/problemset/problem/1227/D1 AC https://codeforces.com/contest/1227/submission/89546017 解説 降順ソートして上位k個を取るのは分かる その中の最小値をxとして、xを何個取ればいいかも分かる xより大きい値は全部取る あと…

具体的にはこの問題 A - Integer Product https://atcoder.jp/contests/agc047/tasks/agc047_a 本番では文字列で読み込んで1e9倍することで誤差を完全に消してACしたが、EPSで誤差を解消できればもっと速く解けた 具体的にはここ using ld = long double; #d…

Superなロリハ（ローリングハッシュ）です ロリハを2本持ってチェックを2回することで衝突リスクを減らして(?)います verified AGC47 B - First Second https://atcoder.jp/contests/agc047/submissions/15818636 multi rolling hash jupiroさんもやってたｗ…

Quiz https://codeforces.com/problemset/problem/1238/C AC https://codeforces.com/contest/1238/submission/89380918 問題意図 readforcesに思ったので図だけ書いておく 現在の足場でレバーを引くと、それと、高さ1下の足場の状態が変化する。出っ張って…

Quiz https://codeforces.com/problemset/problem/1243/B2 AC https://codeforces.com/contest/1243/submission/89376490 解説 文字種ごとに文字数が偶数じゃない場合は等分できないのでNo。それ以外を考える sの先頭から合わせていけばいい s[i]に合わせた…

Quiz https://codeforces.com/problemset/problem/1252/C AC https://codeforces.com/contest/1252/submission/89372135 解説 偶奇なのでmod 2で考える はじめにY方向移動（縦）、次にX方向移動（横）をするとして、even pathにするには通るパスが全て0であ…

Quiz https://codeforces.com/problemset/problem/1305/C AC https://codeforces.com/contest/1305/submission/89296034 解説 mが小さいことに注目。n=200000の時は |Ai - Aj| mod m == 0 となる組み合わせがある 答えが0にならない時はnが小さい時しかあり…

Quiz https://codeforces.com/problemset/problem/1349/A AC https://codeforces.com/contest/1349/submission/89173123 感想 学びの多い問題だった lcm, gcdの関係は、lcm(a,b) x gcd(a,b) = a x b しか知らなかったが、肩のmax, minという類似があることを…

Quiz https://codeforces.com/problemset/problem/1371/D AC https://codeforces.com/contest/1371/submission/89158955 解説 斜めに置いていくとfを小さくできる それを作るために、まず縦長に1を配置してから各行でrotateしてずらした // 正方行列の転置 v…

Quiz https://codeforces.com/contest/1373/problem/D AC https://codeforces.com/contest/1373/submission/89155189 解説 editorialと違う解法 範囲の長さは偶数だけ考えればいい ひっくり返した時、奇数番目と偶数番目がひっくり返るので、差し引きどれだ…

Quiz https://codeforces.com/contest/1208/problem/B AC https://codeforces.com/contest/1208/submission/88938397 解説 editorialの方が賢いですが、別解法で解いたので書いておきます 削る長さが大きいほど条件を満たしやすくなり、条件を満たす・満たさ…

Quiz https://codeforces.com/problemset/problem/1250/H AC https://codeforces.com/contest/1250/submission/88920287 解説 例えば各値が105の時はとても大きい値になるので解はstringになる 観察すると、0は特別 1番出現回数が少ないものがボトルネックと…

Quiz https://codeforces.com/contest/1250/problem/L AC https://codeforces.com/contest/1250/submission/88911821 解説 editorialがないので書いておく 「3つのグループのうちの最大サイズはvに収まるか？」という判定関数を書いて二分探索 // for codefo…

Quiz https://codeforces.com/problemset/problem/1287/B AC https://codeforces.com/contest/1287/submission/88847282 解説 2枚決めると最後の1枚が決まるので、それを持っているかが分かればよい その他 3つ組の時は常に「2つ決めたら最後の1つも決まらな…

Quiz https://codeforces.com/problemset/problem/1296/D AC https://codeforces.com/contest/1296/submission/88831779 解説 各モンスターをAの手番で倒すためには魔法を何回使うことが必要か求めておく その回数の配列を昇順ソートして、K以内に収まる限り…

Quiz https://codeforces.com/contest/1299/problem/A AC https://codeforces.com/contest/1299/submission/88829498 解説 f(a,b) = a&(~b) 最終的な値は、先頭のa0と、それ以外（順不同）で決まる。ではどれを先頭に持ってくればいいか？ 先頭の値のbit=1, …

Quiz https://codeforces.com/contest/1066/problem/B AC https://codeforces.com/contest/1066/submission/88626668 解説 editorialがないので書いておく 各ライトが照らせる範囲を[left, right]として持っておき、左のライトから点けるべきか判定していく …