2021-01-01から1年間の記事一覧
これのとき、2文探査の上限をll r=N*1e12/K + 10; としたらWAで、ll r=N*1000000000000/K + 10; としたらACだった。1e12 != 1000000000000 ? あとで調べるatcoder.jp
いろいろ試行錯誤あったので自分用メモ 後でもう少し詳しく書く(はず) やったことは以下 wsl2の有効化 詳しい説明がたくさんあるのでそちらを参照。 途中で山ほど見た。 後でリンク貼る。 docker及びnvidia-dockerのインストール dockerはともかくnvidia何…
setって順序つき集合になってたんですね。 なので、x以上の要素の値を取り出したかったら auto iter = set.lower_bound(x); int ans = *iter;って感じでできそうです。x"より大きい"なら upper_bound これを知ってたらACできたやつ atcoder.jp
クラスカル法(英: Kruskal's algorithm)は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。(Wikipedia) クラスカル法 - Wikipedia 使った例 Submission #24808238 - 競プロ典型 90 問 dsuを用いて軽い辺から…
を使った例 atcoder.jp・ダブリングで登るときのやり方 ・lcaを返す時に自分の親を返すこと ・根の親は根で大丈夫そう
セグメント木は前に備忘録書いてなんとなくわかった気になっていたが、 遅延セグ木は使い方よくわからんかった。宣言しておくもの S:データの型。intとかなら不要。普通のセグ木と同じ。 S op(S a, S b):ノード間からどういう値を抽出するか。普通のセグ木…
どこに+1,-1なのか忘れがち。左上を原点として +1, -1 -1, +1まず1方向に累積和とったときに、もう1方向の累積和がいい感じになる感じ。atcoder.jp
有向グラフを、「互いに行き来可能な頂点」のグループに分ける方法。 コード atcoder.jp追記(2022/07/11) 構造体にした atcoder.jp 問題文 atcoder.jp
典型力。ダブったペアのぶん種類数が減る。 ダブったペアの数え上げにfenwicktreeを使う。atcoder.jpfenwicktreeにどう情報を入れるか、数え上げをどう実現するかがミソでしょうか。
ソートでgreater使うとき、よくわからんくなる。 greaterな方が(大きいほうが)先に来るようにsortされる。
いろいろ勉強になったので、自分用備忘録。 内容は ・priority_queueのgreatorとか使った宣言 ・それを使ったダイクストラ敵なの ・ラムダ式使ったpriority_queueのemplace ・文字列操作いろいろ atcoder.jp ほかにダイクストラ使ったやつ https://atcoder.j…
ABC_183を解いたとき調べたもののメモ AtCoder Beginner Contest 183 - AtCoder 順列の列挙 調べればいくらでも出るが、next_permutationを使う 競プロの基本事項確認~順列生成の方法~ - Qiita vector<int> v = {1,2,3}; //全部を列挙するときは、はじめ昇順ソー</int>…
数値とかのソートされた配列aに対して lower_bound(a.begin(), a.end(), k) は aの中で ai≧k となる最小のポインタを求める。 upper_bound(a.begin(), a.end(), k) は aの中で ai>k となる最小のポインタを求める。 これらを使ってaの中の値がkの要素の数は …
ビットをシフトさせる操作で、2^nを計算できる。が、これってintの範囲しか使えないんですかね?ABC189のDやってた時にはまったんですが、これではなく掛け算でn乗求める方法にしたらACした。https://atcoder.jp/contests/abc189/tasks/abc189_d