pipenvはあまり関係なさそう。 だいたい以下の記事で解決した。 astherier.com 自分用メモ タイトルにあるようなキーワードで検索したが、記事が少し古めのものが多く（2023/10現在に対し2020,2021あたり、WSL2やWSLgが出る前後？）、今なら不要な設定もして…

atcoder.jp 難しかったけど解説ACしたら何かわかったような気がしたのでメモ。 解法の考え方 N頂点ラベル付き木は、各要素が1~Nで長さN-2の配列に１対１対応させることができる。（Prüfer コード。これを使うと、N頂点ラベル付き木の個数が $N^{N-2}$ 個であ…

良く忘れるのでメモ（使わないとどっちが最小か忘れる）使った問題（解説AC） Submission #41137764 - Denso Create Programming Contest 2022(AtCoder Beginner Contest 239) 学んだこと 頂点のカット（頂点を消す、到達不可にする）は最小カットで考えにく…

どうも苦手意識があるので、典型的な解法やテクニックをまとめることにする。 問題を解いたら適宜追加する。未来の自分、よろしく。 動的計画法 dp[盤面] = その盤面からスタートした時に勝つ/負ける として、勝ち負けが自明な状態（決着がついたときとか）…

部分木に対するクエリとかを効率的に行いたいときに便利。 ABC294Gで学んだ。 atcoder.jp やり方 根からdfsしたときに、辺（あるいは頂点）を通った順に記録しておく。 ついでに問題に必要な情報も同じ順番で記録しておく。 こうすると任意の部分木について…

ABC_287_FでTLEしまくった学びをメモ F - Components このdpを> で書いていたらTLEして、 > で、dp[i][j] のjのループ回す範囲を上限（部分木の頂点数）超えないように適切に管理して書いたらACした。jがスパース（？）になりうるからmapのほうがお得やろ、…

ls * | xargs grep 'hoge'

set s に対して s.upper_bound(x) のほうが upper_bound(s.begin(),s.end(),x) より速い upper_bound(s.begin(),s.end(),x) でやるよりはseg_treeで管理したほうが速い D - Draw Your Cards

windows11のアプデでPCがまともに起動しなくなったので色々やり直した。 毎回やり方わからなくなるので、自分用にメモ。 ・ホストマシンが起動したら自動でsshサーバ立ち上げてくれて、 ・ローカルマシンはssh/config設定した内容＆鍵認証で入るだけ、 を目…

最近Unityを触り始めました。 visual studio で予測変換（Intelisence?）が出ないな～、でもEditor Attachingの設定項目ないな～、と思っていたら使うエディタの設定が少し違ったようです。docs.microsoft.com Unityのエディタ画面から Edit>Preferences>Ext…

これのとき、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

忘れがち pairの要素でソートするときなどに使うかも。second の降順、firstの降順でソート sort(K.begin(),K.end(),[](P const& a, P const& b){ if(a.second != b.second) return a.second>b.second; return a.first > b.first; });

AtCoder Library 最近ようやく確認しました。 modintとか自分で実装しようとすると時間かかるやつがすぐ使えて（自分より）バグがなく使えるのほんとありがたい。 けど、素人には公式の使い方資料わかりづらい。ということで、忘備録。（あとで公式資料リン…

vector v={1,2,3,4}; とかってしたときの最後の要素にが欲しいとき、 v.back(); で要素が得られる。sortのときとかは v.end()ってするけど、 あれはポインタなんですよね。便利便利。 久しぶりに日記書いて書き方忘れてる。

よく忘れるのでメモn行m列のベクターv、0で初期化 vector<vector<int>> v(n, vector<int>(m);</int></vector<int>

set 要素を格納して、後からある要素が含まれているか確認したいようなときに使うコンテナ set - cpprefjp C++日本語リファレンスABC176E の爆弾の位置をvectorで扱おうと思ったらTLEしたりREしたりした。 （REはおそらくメモリが足りなかった） set<int> a; %宣</int>…

c++ の文字列 string ・忘れずに using namespace std; ・宣言 string s; %普通に宣言 string s(N,'a'); %N文字、すべてaで初期化・部分抜き出し s.substr(0,3); %０文字目から３文字抜き出す