2020-12-01から1ヶ月間の記事一覧
Quiz (2016/01) https://atcoder.jp/contests/abc032/tasks/abc032_d AC https://atcoder.jp/contests/abc032/submissions/19071044 感想 「やるだけ」と放置していたが、復習に丁度いいのではと思って解いたらその通りで、よい復習になった 解法 入力データ…
#ifdef LOCAL #define _GLIBCXX_DEBUG #define __clock__ #else #pragma GCC optimize("Ofast") #endif 私のコードは上記を定義している。基本的に便利だが、困ることもある 以前、_GLIBCXX_DEBUGが有効だとpriority_queueが遅いことにハマったことがある 今…
意図 定義を見に行ってもよく分からないので、具体例をここに集めてふわっと理解したい links The Phone Number https://codeforces.com/contest/1017/problem/C この問題のeditorialで出てきます ABC134-E editorialに書いてある from https://img.atcoder.…
Quiz https://codeforces.com/contest/1025/problem/C AC https://codeforces.com/contest/1025/submission/102099631 解説 画像のように、どこで切っても文字列は循環している 文字列を2倍の長さにして探索すればいい 視点 「操作をしても変わらない性質」…
Quiz https://yukicoder.me/problems/no/1310 AC https://yukicoder.me/submissions/596585 解説 +1, -1が隣り合う箇所（変化点）に注目する N個のマスに切れ目をいくつか入れ、グループごとに+1, -1を割り当てる。変化点の数は切れ目の数 円環なので切れ目…
Quiz https://codeforces.com/contest/1462/problem/E1 AC https://codeforces.com/contest/1462/submission/101418838 解説 editorialと違う解法だったので書いておく 3つ組なので真ん中をずらしながら全探索する 左側の統計と右の統計をBITでそれぞれ持て…
Quiz https://codeforces.com/contest/1462/problem/C AC https://codeforces.com/contest/1462/submission/101404148 解説 Find the smallest positive integer というのを読み飛ばしていたので1～9を使うかどうかを「BIT全探索」した結果、期せずして正し…
大抵nCrを求める時はmodをとったものを返すが、以下の問題は違った (ABC 300点) C - Duodecim Ferra https://atcoder.jp/contests/abc185/tasks/abc185_c パスカルの三角形を上に登っていく再帰でnCrを求めればoverflowに怖がらずに済む AC https://atcoder.…
（自分で検索する時用の記事です） 下記の700点問題が典型っぽい L - をあ ぷろぶれむ https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_l この問題名で検索して出るアルメリアさんのBlogを読めばいい ポイント：二分探索・単調性・セグメ…
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/855/B AC https://codeforces.com/contest/855/submission/100722877 解説 3つ組の真ん中を固定した時、左右でどれを選べばいいかは範囲min, 範囲maxが取れれば分かる 左からのmin, max配列 右からのmin, ma…
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…
