Quiz https://codeforces.com/contest/1547/problem/E AC https://codeforces.com/contest/1547/submission/122256788 解法 左からの累積MIN, 右からの累積MINを取ればいい 別解？ 下記画像左上のように、不要なエアコンがあれば除去してしまえば、現在位置…

Quiz https://codeforces.com/contest/1542/problem/B S={1}とする。Sの要素には「aをかける or bを足す」を無限回できて要素を増殖できる。nを作れるか判定せよ。制約は109 AC https://codeforces.com/contest/1542/submission/121451438 解説 書き下しても…

Quiz https://codeforces.com/problemset/problem/770/C AC https://codeforces.com/contest/770/submission/100808711 解説 パット見でトポロジカルソートっぽい。サイクルを見つけたら-1にすればいいと思うのだがそれは罠で、不要な講義でサイクルができて…

Quiz https://codeforces.com/contest/817/problem/B AC https://codeforces.com/contest/817/submission/100792550 解説 editorialと違うので書いておく どの3つを選べば最小になるかはソートすれば分かる。その数値を[a,b,c]とする 入力の配列Aから[a,b,c]…

Quiz https://codeforces.com/problemset/problem/825/D AC https://codeforces.com/contest/825/submission/100739266 問題理解 読解に苦労したが、sの上にtを滑らせていき、完全一致する回数を最大化するように?を埋めよという問題 英語 largest number of…

Quiz https://codeforces.com/contest/845/problem/C AC https://codeforces.com/contest/845/submission/100730243 解説 editorialと違う解法だったので書いておく 番組の終了と同時に新たな番組を見ることはできないので、右端を+1しておき、範囲(l, r)と…

Quiz https://codeforces.com/problemset/problem/847/A AC https://codeforces.com/contest/847/submission/100729004 解説 editorialがないので書いておこうと思ったが、実装問題です。特殊なデータ構造は不要 左右の情報が与えられるので、各数字の右と左…

Quiz https://codeforces.com/problemset/problem/875/B AC 問題理解 すごく問題文が理解しづらかった。サンプルで説明します // input 4 1 3 4 2 // output 1 2 3 2 1 問題理解つづき 最初の状態はOOOO これで右までスキャンもカウントするので、この場合の…

Quiz https://codeforces.com/problemset/problem/883/E AC https://codeforces.com/contest/883/submission/100592159 問題意図 ＊で隠された文字列sがある a～zの文字のうち、宣言したら確実に＊のいずれかが開く文字の個数を求めよ 解説 editorialがない…

Quiz https://codeforces.com/problemset/problem/887/C AC https://codeforces.com/contest/887/submission/100585022 解説 簡潔に書けた 回転は色々あるが、たとえば面0を回転軸として面3,1,4,5を右にずらす・左にずらすの2パターンがある この時、面0,2に…

Quiz https://codeforces.com/problemset/problem/958/F1 AC https://codeforces.com/contest/958/submission/100475630 解説 範囲の全探索。colorごとの累積和を持てば各色の集計も高速にできる その他 汎用的に構造体で書けると以前から思っていたので、ち…

Quiz https://codeforces.com/contest/959/problem/C AC https://codeforces.com/contest/959/submission/100473060 解説 N>=6なら間違う木を作れる。editorialの構築もいいですが、私は下記の図のように等分に分けた すると間違ったアルゴリズムでは解をN/2…

Quiz https://codeforces.com/contest/991/problem/D AC https://codeforces.com/contest/991/submission/100399548 解説 editorialは以外にもDPではなかった。私はDPで解いた 左から埋めていくとして、何か置くと次の位置も埋めてしまう。ただ、埋まり方は4…

Quiz https://codeforces.com/problemset/problem/744/A AC https://codeforces.com/contest/744/submission/100309023 解説 辺でunion findしていく governmentのいる連結成分ごとに、全点間で辺をはる governmentのいない街をすべて集めて、全点間で辺をは…

Quiz https://codeforces.com/problemset/problem/707/C AC https://codeforces.com/contest/707/submission/100306975 解説 完全な数学問題 Nを底面としてNを偶奇で場合分けすると求まる 学び (a-b), (a+b)の偶奇は一致する int main(){ cin.tie(0); ios::s…

Quiz https://codeforces.com/contest/687/problem/A AC https://codeforces.com/contest/687/submission/100305056 解説 2部グラフに塗り分けられないなら-1 塗り分けられるなら色ごとに分配すればいい その他 2部グラフに塗ることは今後もありそうなので、…

Quiz https://codeforces.com/problemset/problem/638/B AC https://codeforces.com/contest/638/submission/100302483 解説 editorialがないので書いておきたいが、実装が多くて疲れたので流れだけ。 適当な順番でくっつけていはいけない 文字列それぞれを…

Quiz https://codeforces.com/problemset/problem/630/K AC https://codeforces.com/contest/630/submission/100290959 解説 余事象を包除原理で求める（下記画像参照） int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; ll al…

Quiz https://codeforces.com/problemset/problem/620/C AC https://codeforces.com/contest/620/submission/100282991 感想 解法は貪欲でOK。サンプルケースは全て通るので提出！WA 全てのPearlはそれぞれ1度、範囲に含まれている必要がある A = [1,1,1,1,2…

Quiz https://codeforces.com/contest/609/problem/C AC https://codeforces.com/contest/609/submission/100228846 解説 sum%N!=0の時のみ説明します 嘘解法 a = sum/Nとして、最終形ではすべての要素がaまたはa+1になる a+1より大きい値が来たらその差の分…

Quiz https://codeforces.com/problemset/problem/599/B AC https://codeforces.com/contest/599/submission/100225973 感想 問題理解に手間取りましたが、理解できれば簡単です 問題把握 長さMの配列Aがある（値域１～N） 変換関数Fがある AをFに通した長さ…

Quiz https://codeforces.com/problemset/problem/584/B AC https://codeforces.com/contest/584/submission/100220226 解説 余事象を考える 全ての出方は33N 3つ組にて、和=6を満たしていない値の割り振りは(1,2,3), (2,2,2) (1,2,3) : 6パターン (3!) (1,2…

Quiz https://codeforces.com/contest/1005/problem/D AC https://codeforces.com/contest/1005/submission/100175976 解説 各文字をmod3しておく 文字列を後ろから見て、今まで見た数値の部分集合で3の倍数が作れるなら+1して、見た集合を空にする int main…

Quiz https://codeforces.com/contest/1031/problem/B AC https://codeforces.com/contest/1031/submission/100148060 解法 editorialではbitごとに決まると書いてあるが、値域が狭いので全探索したらACした 先頭2つを全探索し、条件を満たし続ける限りi=2以…

Quiz https://codeforces.com/contest/1043/problem/C AC https://codeforces.com/contest/1043/submission/100145616 解説 aaaaabbbbbの形にできる aの塊ごとに見て、その後端で1度flipすると、そのaの塊が先頭に来る 次のaの塊の直前にあるbで1度flipする…

Quiz https://codeforces.com/contest/569/problem/A AC https://codeforces.com/contest/569/submission/100124130 問題理解 音楽をダウンロード（DL）しようとしている。S秒分の曲をDLしたら、Playを開始する DLが完了するまで、何度も曲を聞く 聞いている…

Quiz https://codeforces.com/problemset/problem/1080/C AC https://codeforces.com/contest/1080/submission/100064787 感想 解法はeditorialの通り。https://codeforces.com/blog/entry/63436 二次元累積和に似た考え方をすることで指定領域内のblack, wh…

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…