agwのブックマーク - はてなブックマーク

競技プログラミングをやってきた - はまやんはまやんはまやん

この記事は競プロ Advent Calendar 2021の10日目の記事です。長年、競技プログラミングをやってきた。気が付けば、最初に競技プログラミングを初めてから既に6年が過ぎていた。別にこの記事を何らかの区切りにしようとか、そういった意図はないのだが、振り返るには良い時期なのかもしれない。 2015年競技プログラミングに出会う研究室に入ったタイミングで競技プログラミングの勧誘を受けた。これが競技プログラミングとの出会いである。思い出というのはいつまでも覚えているもので、金沢市内にあるカレー屋でのことだった（もう既に閉店している）。先輩方から「IPCPに出てみないか」と言われたのを鮮明に覚えている。実はこの研修室には競プロの有名人が在籍しており、その人のおかげで研究室には競技プログラミングの流れがあった。本当に奇跡的であり、感謝しきれない。今も色々すごいことをしているすごい人

agw 2021/12/11

リンク

競技プログラミングにおける動的計画法更新最適化まとめ（CHT, MongeDP, AlianDP, インラインDP, きたまさ法, 行列累乗） - はまやんはまやんはまやん

動的計画法更新最適化？参考1 参考2 参考3 セグメント木や累積和 dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j]) dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j]) みたいに区間和や区間最大最小をもたせることで更新を行う。行列累乗 DPの更新式を見てみると、一回の更新操作が行列の形になるときがあるこの場合は行列を繰り返し二乗法の要領でN乗しておくことで、N番目の要素を高速に取り出せる。 Convex Hull Trick 関数の形式になっている区間最小値を素早く見つける手法参考1 参考2 わかりやすい資料 dp[i] = min{j=0...i-1}（

agw 2019/01/07

リンク

二項係数 mod 素数を高速に計算する方法 [累積和, フェルマーの小定理, 繰り返し二乗法, コンビネーション, 10^9+7] - はまやんはまやんはまやん

要望 nCk mod 10^9+7を高速に計算したい n,k≦10^5 追記：llはlong longのことです使ってるテンプレートはこんな感じです。 #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; typedef long long ll; 高校で習うやり方でやると… ll mod = 1000000007; //--------------------------------------------------------------------------------------------------- ll C(int n, int k) { ll res = 1; rep(i, 0, k) res = (res * (n - i)) % mod; rep(

agw 2018/06/07

リンク

競技プログラミングにおける無向グラフ上での特殊な数え上げ問題まとめ [スペクトルグラフ理論, 行列木定理, ケイリーの公式] - はまやんはまやんはまやん

無向グラフ上で特殊な数え上げをする場合に使えるテク集スペクトルグラフ理論無向グラフをあるルールで行列に変換したものを使って色んな問題を解決する参考1 参考2 ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ解説行列木定理（ラプラシアン行列の任意の余因子は無向グラフの全域木の個数と等しい）解説隣接行列の行列式の偶奇とそのグラフの完全マッチングの総数の偶奇が一致する解説ケイリーの公式参考 n頂点のラベル付きの木の総数はn^(n-2)通りあるラベル付きなので、木の形の組合せと木の頂点に数を割り当てる組合せを全て考慮した組み合わせ数ケイリーの定理の問題は「行列木定理+多項式補間」の組合せでも解けるっぽい（かなり不確定）（HEのColorful Spanning Treesはこの組合せなのでケイリーの定理っぽくやっても解ける？）（Stranger Tree

agw 2018/04/15

リンク

Late Edges [CSAcademy #54] - はまやんはまやんはまやん

https://csacademy.com/contest/round-54/task/late-edges/ N頂点の無向グラフがある。辺には利用可能になる時間が書いてある。最初は時間0で頂点0スタート。各時間で必ず隣接点に移動する必要があるときに、最短何秒で頂点(N-1)に到達できるか。 N,M≦5*10^3 解説「mi[i][j] := 頂点iに到達できるパリティがjの時の最短時間」を使って最短距離を更新していく。パリティがjとは最短時間のパリティのことである。時間5に頂点iにいるそれにつながっている利用時間が9である辺を渡れる最短時間は？横の頂点と行ったり来たりすれば5->7->9でピッタリに渡れるそれにつながっている利用時間が10である辺を渡れる最短時間は？横の頂点と行ったり来たりすると5->7->9->11で1秒遅れで渡れるつまり、パリティが一致しているか

agw 2017/10/28

リンク

Yet Another Palindrome Partitioning [CODE FESTIVAL 2017 予選C D] - はまやんはまやんはまやん

http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d 解説 http://code-festival-2017-qualc.contest.atcoder.jp/submissions/1706173 ある文字列が並び替えて回文となるのは「全ての文字が偶数個ある、または、奇数個の文字が1つだけある」場合である。この典型を知っていないと今回の問題を解くのは難しい。 DPで解く。まず、DPを考えてみると「dp[x] := x番目まででまとまりを作った時の分割数の最小」が思いつく。以下、並び替えて回文となる部分列はvalidであると言うことにする。この更新は dp[x] = min{y＜xかつ[y,x)がvalid}(dp[y] + 1) で行える。これを愚直にやろうとする

agw 2017/10/28

リンク

競技プログラミングにおける永続データ構造問題まとめ - はまやんはまやんはまやん

永続データ構造 persistent data structures 解説色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。永続配列があれば永続Union-Findが作れるらしい永続配列は永続木があれば作れるらしい部分永続Union-Findの資料部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる平衡二分木を永続化するときは赤黒木が最良らしい問題完全永続セグメントツリー SPOJ D-query CF429 Destiny (要素add,特殊クエリ) 部分永続セグメントツリー CS

agw 2017/06/16

リンク

競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん

全方位木DP よく分かる解説問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 Road Improvement 解説 yukicoder No.768 Tapris and Noel play the game on Treeone 解説違うけど方針が似ている問題 CF Nearest Leaf

agw 2017/03/22

リンク

はてなブックマーク

タグ

ブックマーク / blog.hamayanhamayan.com (8)

お知らせ

今週のはてなブックマーク数ランキング（2024年10月第1週）

月間はてなブックマーク数ランキング（2024年9月）

今週のはてなブックマーク数ランキング（2024年9月第5週）

公式Twitter

キーボードショートカット一覧

はてなブックマーク

公式Twitter

はてなのサービス