2021-01-01から1年間の記事一覧
Quiz https://codeforces.com/contest/1485/problem/C AC https://codeforces.com/contest/1485/submission/107728292 解説 editorialかkoboshiさんの解説を読みましょう https://koboshi.growi.cloud/Contests/701 学び 条件A=B=kと置いて式変形していくこ…
Quiz https://codeforces.com/contest/1490/problem/G AC https://codeforces.com/contest/1490/submission/107711008 解説（というか感想） 何周かして、最後の1周のどこでxに到達できるかという2段階で考える 何周すればいいかは数学でO(1)で求まるが、（…
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の意味：一…
