7K12 blog

猫でも分かる何か

2023-01-01から1年間の記事一覧

ABC334 に参加した感想

BとCがゲキムズ 実家 累積和を二分探索 https://atcoder.jp/contests/abc334/submissions/48784027

ABC333 に参加した感想

Cを解くのに無限時間かかった。 第一感では3進数かDFSかと思っていて全探索に気づくのに無限時間費やした。サンプルに最大値のヒントがあるの意識すべきだった。 https://atcoder.jp/contests/abc333/submissions/48592287 部分木サイズなのでDFSだとは思っ…

グリッドグラフ変換 LIB::GridGraph

#include <bits/stdc++.h> using namespace std; namespace LIB { using GG=graph<ll>; template<class W, class GG>class GridGraph { using ll=long long; template<class T>using vve=vector<vector<T>>; GG& g; vve<ll> ndtable; public: GridGraph(vve<W>& grid, ll dir, W wall, GG& g):g(g) { vector<pair<ll,ll>> d…</pair<ll,ll></w></ll></vector<t></class></class></ll></bits/stdc++.h>

ABC330 に参加した感想

E問題マルチセットで解けると思ったがTLEになった。 Cで「めぐる式二分探索」が出題される時代なのか…と思いつつ他の解法が思いつかなかったので二分探索で提出。ところで高校数学の典型問題に「2変数関数の最小値は両方を平方完成してと式変形すると且つが…

ABC318D - General Weighted Max Matching (dif1017)

順番は無関係なのでで固定して赤黒木のような感じでDFSする。白線では遷移自体はせず赤線で遷移する。完全グラフの完全マッチングは「残った頂点のうち最も小さい番号の頂点に対して相手を選ぶ」を繰り返すことで数え上げることが出来る。残った頂点のうち最…

複合コンテナ CompoundContainer

#include <bits/stdc++.h> using namespace std; namespace LIB { template<class T>class DequeSet { public: deque<T> d; unordered_set<T> s; DequeSet() {} DequeSet(initializer_list<T> il) { for(auto&e: il) push_back(e); } auto back() { return d.back(); } auto begin() { return </t></t></t></class></bits/stdc++.h>…

ABC325 に参加した感想

B問題を誤読して冷えた実家 union-find で連結させる https://atcoder.jp/contests/abc325/submissions/46806218

データ構造の分割 LIB::MultiSplit

#include <bits/stdc++.h> using namespace std; namespace LIB { template<class MT>class MultiSplit { using ll=long long; using sl=set<ll>; template<class T>using ve=vector<T>; MT& ds; sl spl; template<class T>void push(ve<T>& t, T x) { t.push_back(x); } public: MultiSplit(MT& ds):ds(ds) { spl.</t></class></t></class></ll></class></bits/stdc++.h>…

作問

hello world 想定dif 0-400 https://mojacoder.app/users/tkr987/problems/hello_world Fizz Buzz 想定dif 0-400 https://mojacoder.app/users/tkr987/problems/fizzbuzz 回転寿司 想定dif 1000-1200 https://mojacoder.app/users/tkr987/problems/sushi 二…

難問

自分が難問奇問と感じた問題メモですG - General Weighted Max Matching https://atcoder.jp/contests/adt_medium_20231107_2/tasks/abc318_d

めぐる式二分探索 auto meguru_search

https://atcoder.jp/contests/abc063/submissions/47856291

ゲーム記録

BMS 段位認定八段 https://youtu.be/9LPipna92gA?si=w0TjCaTQ-VJCgpzE 熱した鉄球を水につけるとどうなるか ☆8982 CLEAR https://youtu.be/e3TCtPcBXP8?si=BD6O5oB7DKWVNiwd LOL アーリちゃん初ペンタキル https://youtu.be/RHTmuKFrRV4?si=3HQWvM_LNJYwM6UO…

全方位木DP LIB::RerootingDP

わかりやすそうな記事 https://algo-logic.info/tree-dp/猫でも分かる全方位木DP記事を募集しています

強連結成分分解 LIB::StronglyConnectedComponents

互いに行き来できる頂点集合に分解する https://manabitimes.jp/math/1250 メンバ関数 StronglyConnectedComponents(G& g); コンストラクタ vector<set<ll>> Run(bool ignore_dag); ignore_dag=false にすると閉路を持たない各頂点はサイズ1の各集合に割り当てる (</set<ll>…

visual studio でフォントが反映されないバグ

Windows Font Cache Service というプロセスを一度停止させると治る http://www.ria-lab.com/archives/3051何年バグ放置しとるんやMS

形式的冪級数 LIB::FormalPowerSeries

LIB::FormalPowerSeries modの畳み込みでn次式fとm次式gの乗除算を高速に計算する https://zenn.dev/koboshi/books/600753d917cdbc/viewer/3a148e https://web.archive.org/web/20220813112322/https://opt-cp.com/fps-implementation/ https://judge.yosupo…

ABC320 に参加した感想

最近は数学:プログラミング=9:1くらいの割合で精進しているため実装に無限時間かかったけど意外と暖まった。自分が30分かけて実装したBを全人類5分で提出していて回文ライブラリを用意するべきだと思った。 C - Slot Strategy 2 (Easy) 実装が重い!順…

ABC315に参加した感想

D の解法見当もつかなかった 最近一生冷えてるな C - Flavors 愚直にやると なので異なるケーキの最上位だけ集めた配列を作ってソートすると https://atcoder.jp/contests/abc315/submissions/44730930 D - Magical Cookies なんもわからん

HL分解 LIB::HeavyLightDecomposition

LIB::HeavyLightDecomposition heavy edge と light edge に分解してセグメント木などのデータ構造と併用することでパスクエリを高速に処理する 構築 部分木クエリ パスクエリ https://qiita.com/Pro_ktmr/items/4e1e051ea0561772afa3 https://hcpc-hokudai.…

メカニクス虚無でも完全ソロでゴールドになる方法

lol

前回の記事:メカニクス虚無でも完全ソロでシルバーになる方法 https://9871225.hatenablog.com/entry/2023/04/19/105117 はじめに 120ゲーム勝率62%(直近は10連勝)で人生初ゴールドなれたので、この記事では才能ない人がゴールドになる方法を書いていきま…

ローリングハッシュ LIB::RollingHash

LIB::RollingHash 長さNとMの文字列に対して文字列検索をすると計算量 https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 https://zenn.dev/hellorusk/articles/c2de32c2295093f8721c メンバ関数 RollingHash(string& sin, u64 base) ハッシュ値を計算…

文房具に興味がなかったので1万円の鉛筆を買った

最近、クルトガダイブという1万円の鉛筆を買いました。 この鉛筆、本来の定価は5000円なんですが、限定生産品みたいな扱いになっていてプレミア価格で最安値でも1万円です。鉛筆1本1万円!?高すぎ!!!!!って思うかもしれませんが、文房具に興味ない人に…

ABC310 に参加した感想

DやE問題が難しくてCまでの3完速解き回だった。解法を思いつくのに無限時間かかって敗北…。 C - Reversible https://atcoder.jp/contests/abc310/submissions/43617976 この問題の肝はダブルカウントしないよう処理できるかどうか。考えなければならない単語…

ABC305に参加した感想

C問題もう少し早く解法に気づきたかった。アルゴリズムは数学的性質を使うことが多いので、もう少し数学的に処理する意識を持つべきだったように思う。 C - Snuke the Cookie Picker https://atcoder.jp/contests/abc305/submissions/42145904 まず、問題文…

典型数学(微分)

接線の公式 y軸に平行な接線 x=a は表せないが二次関数や三次関数のような普通の陽関数はy軸に平行な接線にならない 法線の公式 f'(t)=0 のときはy軸に平行になる 法線は単純な陽関数でもy軸に平行になりやすく場合分けが面倒なので で暗記するテクニックが…

変数名

accumulation, acc: 累積 edge, ed: 辺 factor, fac: 因数 rotate, rot: 回転 node, nd: 頂点

二次元の回転 auto vvrot

二次元の90度回転 (vv rotate 90) テンプレート auto vvrot90=[&](auto& vv, auto vf) vv: 2次元配列など(入力) vf: 入力の先頭要素 (vv[0][0]) using ll=long long; template<class T>using vec=vector<T>; auto vvrot90=[&](auto& vv, auto vf){ ll W=ll(vv.front().</t></class>…

ARC154-B New Place (400) diff1027

解説AC https://atcoder.jp/contests/arc154/submissions/41983611 本質 逆順テク SSS(単純部分列)の判定はtwo-pointers的な累積テクでO(N) 一箇所に集めて分配 詳細 「Sの先頭の文字を任意の箇所に挿入できる⇒Sの後半の文字列がTの部分列」が一致できる条…

ABC300に参加した感想

数カ月ぶりに参加した割に健闘したと言って良いと思う。最近、数学の勉強を頑張ってるのでDみたいなのが解けたのは良かった。 C - Cross https://atcoder.jp/contests/abc300/submissions/41033925 実家 D - AABCC https://atcoder.jp/contests/abc300/submi…

メカニクス虚無でも完全ソロでブロンズの魔境を抜ける方法

lol

自分はメカニクスがなので色々と悩んだ結果、対面のソロキルを諦めたら逆に94ゲーム勝率64%(直近20ゲーム勝率74%)でシルバーに昇格できました!友達がいなくて完全ソロでも魔境を抜けることが可能! ルーン レベル6になったらミニオン吸収装置を使ってレ…