Quiz https://atcoder.jp/contests/arc112/tasks/arc112_b AC https://atcoder.jp/contests/arc112/submissions/20213324 解説 数直線で考える 到達できる箇所は2つの範囲になる（重なることもある） 左に行くのと右に行くコストが非対称なので、bを場合分け…
Quiz https://codeforces.com/contest/1487/problem/C AC paste TODO 解説 グラフにして矢印でwin/loseを表すと、大抵はwin/loseを割り当てられることが分かる 一般化 一般にNが偶数の時はtieがN/2個あり、Nが奇数の時は全てwin/loseを割り当てられる
Quiz https://codeforces.com/contest/1487/problem/D AC https://codeforces.com/contest/1487/submission/107464174 解説 式変形をして性質を見つけて(b+1==c), aの探索範囲を狭めて全探索する TLE? TLギリギリな気がするが、最大ケースを作成して2秒に間…
Quiz https://atcoder.jp/contests/arc112/tasks/arc112_a AC https://atcoder.jp/contests/arc112/submissions/20196184 解説 L<=A<=Rなどの制約が扱いづらいので、全体からLを引いて0<=a<=R-L (A-L=aとおく)として扱いやすくする 満たすべき条件「A = B + …
min_left, max_rightの使用例です cf ACL doc https://atcoder.github.io/ac-library/document_ja/lazysegtree.html Quora Programming Challenge 2021のSkyscraperという問題で使用してACを確認した Skyscraper 問題 https://jonathanirvin.gs/files/divisi…
公式サイト https://www.quora.com/q/quoraprogrammingchallenge 2021/02/10時点、editorialなし... 全体の印象 部分点がある 最初の1問はやるだけ実装問題 次に、いくつかの競プロ的問題 最後にML(Machine Learning)問題がセットごとに2つあり、統計を使う …
Quiz https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_b AC https://atcoder.jp/contests/nikkei2019-final/submissions/20052741 解説 公式editorialがアッサリしすぎなので書く 制約を見ると、A
Quiz https://atcoder.jp/contests/arc005/tasks/arc005_3 AC https://atcoder.jp/contests/arc005/submissions/19891504 解説 問題としては01BFSやるだけ 構造体にまとめてみた struct ZeroOneBFS{ ll H,W; VS S; VV d; // distance const int dx[4] = {-1,…
Quiz E-Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e AC https://atcoder.jp/contests/abc190/submissions/19830501 感想 似たのが来たら貼るぞ！ 距離行列やdpテーブルで未記入の-1やinfが混乱しがち 訪れたらフラグを上げるのか下…
Quiz https://codeforces.com/contest/1476/problem/D AC https://codeforces.com/contest/1476/submission/105969483 解説 頂点倍化してUnion Find 下図を見れば分かるはず
キッカケとなった問題 D.Nezzar and Board https://codeforces.com/contest/1478/problem/D AC https://codeforces.com/contest/1478/submission/105774949 解説 2点間の距離を全部求めてgcd取ると飛び幅が求まる しかしO(N2)かかる。なんとなく隣接だけ距離…
Quiz https://codeforces.com/contest/1475/problem/G AC https://codeforces.com/contest/1475/submission/105517286 解説 aの値が重複していない場合を考えると、小さい値から下図のようにDPしていくと「残せる最大頂点数」が求まる aの値が同じものはそれ…
Quiz https://codeforces.com/contest/1475/problem/F AC https://codeforces.com/contest/1475/submission/105417957 他者の解法 こどふぉ #697 div3A 2でひたすら割るB 2021*2020以上は大丈夫、以下は2020の数で全探索C 各人から出る辺の数をカウントD 尺…
Quiz https://codeforces.com/contest/1472/problem/E AC https://codeforces.com/contest/1472/submission/105254745 解説 座圧したりセグ木使ったり色々解法はあるようですが、mapを使った解法を紹介します (width, height)は横長で揃えておく (width, hei…
個別に選ぶ場合 https://clist.by/ に直近のイベントがリスト化されている カレンダーアイコンを押すとGoogle, Yahoo, Outlookお好きなカレンダーに予定を追加できる 「こどふぉDiv2は予定に入れたいけどDiv1は入れたくない・・・」等の人はこちらの方法を取…
Quiz https://atcoder.jp/contests/pakencamp-2020-day1/tasks/pakencamp_2020_day1_d 解説 1N<=K<=2Nのカットのみ複雑なので図示します
Quiz http://poj.org/problem?id=2104 POJ一般 auto使えない using使えない include bits使えない 苦労したこと 問題文の読み間違い。Aは負値もある cinではなくscanfを使わないとTLE（問題文に書いてある） scanfで読み込み先がintかlong longかで指定を変…
最大安定集合（最大独立集合）とは グラフにて、辺でつながった２頂点の両方は選べないとしたときに選べる頂点の最大数 具体例「嫌いを辺で表した時に、何人スタッフを選べるか」 2部グラフなら最大マッチングで解ける Quiz C - 広告 https://atcoder.jp/con…
グラフの彩色数問題とは、辺で結ばれた頂点は違う色で塗る時、最低何色必要かという問題 ei1333さんのライブラリを（引数を変更して）使いました記念 https://ei1333.github.io/luzhiled/snippets/graph/chromatic-number.html 計算量O(2N N) AC https://atc…
Quiz https://atcoder.jp/contests/agc051/tasks/agc051_a AC https://atcoder.jp/contests/agc051/submissions/19089349 解説 野生の解説が見当たらなかったので書いておく 公式editorialは読んだものとします d=2の時の解は3通り 追記：(1,1)x6の意味：一…
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にすればいいと思うのだがそれは罠で、不要な講義でサイクルができて…
