2021-02-01から1ヶ月間の記事一覧
Quiz C - Sqrt Inequality https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c 誤差に厳しい。C++のlong doubleだと通らない。EPS足せばEPSの値によっては通る pythonのdecimalで殴ってみる AC https://atcoder.jp/contests/panasonic2020/su…
algo-logicさんのライブラリをお借りした https://algo-logic.info/bridge-lowlink/ 橋（と関節点）をO(N+M)で求められる(AC)ことを確認した 無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います verify (AtCoder)…
背景 ABC-Dでlong longのオーバーフローチェックが必要でした(C++erの場合) 積のオーバーフローチェックは a > INF / b がおすすめ— tatyam (@tatyam_prime) February 20, 2021 同値 上記発言の背景には同値関係があり、snukeさんも解説放送で説明していた h…
Quiz https://codeforces.com/contest/1486/problem/D AC https://codeforces.com/contest/1486/submission/107889074 解説 editorialの通りですが、なんとなくKは小さい方が大きいmedianが見つかる気がして、長さKのみ調べればいい気がしますが、間違いです…
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,…
