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の意味：一…