「離散数学への招待（上）」を読んでいれば簡単 部分点１、２ わからない 部分点３ (a,b)⇄(c,d) when a

部分点１ 問題文を読む 部分点２ 各頂点から、直左右の自分以上の値を持つものにコスト１の辺を張ったグラフがあって、a~bの最短距離をQ回求めよという問題。 辺は遅延セグ木(max,max)とかで殴るととりあえず分かる。他に天才解法がありそう。 辺が2*N個なの…

競技プログラミングでテストケースを作るためのテンプレートを置きます。 ランダムでのケース自動生成、自動でのファイル作成を前提にしています。 ファイル名はAtcoder形式です。 ・Solve()...問題を解く処理をここに書きます。 ・Form()...入力を生成する…

class RAQxRMQ{ private: ll dat[2*N],laz[2*N]; ll eval(ll k){ dat[k]+=laz[k]; if(k<N)laz[k*2]+=laz[k],laz[k*2+1]+=laz[k]; laz[k]=0;return dat[k]; } public: void Init(){ lol(i,2*N)dat[i]=laz[i]=0; } void Upd(ll l,ll r,ll x){ l+=N,r+=N+1; for(ll a=l,b=r;a<b;a>>=1,b>>=1){ if(a&1)laz[a++]+=x; if(b&1)laz[…</n)laz[k*2]+=laz[k],laz[k*2+1]+=laz[k];>

問題概要 数列があって、一ペア交換したときの転倒数の最小値を求めよ 小課題1 aとbを交換するとき(aがもともと左、a>b)、aとbの間にある数について、aと同じなら1、bと同じなら1、a>x>bなら2だけ転倒数が減る。 任意のペアについて確かめると、O(N^2)回領域…

問題概要 N階のダンジョンがあって、各階で消費する体力とコスト1で回復できる体力が決まっていて、Hを超えない。体力を常に1以上に保ったまま最下層まで行くのにかかる最小コストを求めよ。 小課題1 愚直DPをすると解ける。階数、残り体力を頂点として、コ…

F: 天使とふすま - 技術室奥プログラミングコンテスト #3 | AtCoder 作問した バトルゲームから問題を作って、考えてみたら解けたので投げた 蟻本に類題が載ってて有名問題らしい ソートするだけ

Dinic法 最小カットがO(|E|・|V|^2)でできるっぽい Ford-Fulkerson法より速そう 実装が重すぎるので次回からはコピペすることにした 最大フローを使った問題 700点 Submission #2014890 - AtCoder Regular Contest 085 800点 Submission #2014928 - AtCoder …

頭の整理＋セグ木 方針は分かりやすいが、整理が難しい 構造体を初めて使った セグ木は2Nまで初期化しよう #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i</queue></vector></algorithm></iostream>

木の性質 木は直径の部分にいっぱいくっつけたものと思っとけばいい 解説を見た #include<iostream> #include<algorithm> #define lol(i,n) for(int i=0;i<n;i++) using namespace std; int n,a[110],cnt[110]; int main(){ cin>>n; lol(i,n)cnt[i]=0; int maxi=0; lol(i,n){ cin>>a[i]; cnt[a[i]]++; maxi=max(maxi,a[i]); } bool ok=true; for(int i=0</n;i++)></algorithm></iostream>…

グラフにするやつ 見た目DPに見えるのでそれを考えるが、グラフに変換すると一発 modを取るのを試すとできる #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; int dis[100010],k; typedef pair<int,int> P; priority_queue</n;i++)></queue></vector></algorithm></iostream>

部分の最適化 木を小さく分けてずっと考えてると、最適解が１つだと分かる 速解きは無理 #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; bool dp[5010],cop[5010]; vector<int> v[1010]; int index[1010]; int par[1010]; int…</n;i++)></queue></vector></algorithm></iostream>

bit単位への圧縮 よくある、偶奇とかmod2とかの 0と1にするやつ こうするとNが一つ2になるので、今回は2^26で通った #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; #include<unordered_map> unordered_map<int,vector<int> >v; //…</int,vector<int></n;i++)></queue></vector></algorithm></iostream>

部分問題への分割 基本にのっとって問題の分割をすると、再帰的な問題だと気づく まさか解法が降ってくるとは思わなかった #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i</queue></vector></algorithm></iostream>

式の整理 方針は直感的にわかりやすいが、条件整理が難しい おはじきを使うと考えやすかった #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; ll u[100010]; ll v[100010]; int d[100010]; int main(){ int n,m; cin>>n>>m; lol(…</n;i++)></queue></vector></algorithm></iostream>

グラフの変形をする 600点問題ではない 最短経路問題なので、Dijkstraしやすいようにグラフをつくる 辺の数を少なくするため、経由地的な頂点を使う #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; #include<map> typedef pair<int,int> P; vector</int,int></n;i++)></queue></vector></algorithm></iostream>

座標から面積を出す 三辺の長さのみが分かっているならheronを使うしかないが、大体は三点の座標が分かっているので、これでできる double S(int x1,int x2,int x3,int y1,int y2,int y3){ x1-=x3,x2-=x3,y1-=y3,y2-=y3; double tmp=(x1*y2)-(x2*y1); return…

最大長方形 2 x 2マスの部分を見ると解法が自明だが、強実装で辛い 障害がマスではなく点の最大長方形問題になる #include<iostream> #include<algorithm> #include<vector> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; int dp[2010]; int c[2010][2010]; #include<stack> int BiggestRectang…</n;i++)></queue></vector></algorithm></iostream>

3/10⇨69、69⇨3/10 int MandD_Day(int m,int d,bool uruu){ int cnt[12]={31,28+uruu,31,30,31,30,31,31,30,31,30,31}; int ret=0; for(int i=0;i<m-1;i++)ret+=cnt[i]; return ret+d; } pair<int,int> Day_MandDay(int d,bool uruu){ int cnt[12]={31,28+uruu,31,30,31,30,31,31,30,31,30,31}; int m=0; while(tr</m-1;i++)ret+=cnt[i];>…

高次元DPをやる dp[300][300][300]を作るのは雰囲気でそうなるが、工夫しないとMLEをするので頑張る #include<iostream> #include<algorithm> #include<vector> #include<queue> #define mod 1000000007; #define lol(i,n) for(int i=0;i</queue></vector></algorithm></iostream>

帰納法をちゃんと実装する 解法の方針はわかりやすいが、条件整理が面倒 変数名の勉強をしたので、うまく実装できた #include<iostream> #include<algorithm> #include<vector> #include<string> #include<queue> #define lol(i,n) for(int i=0;i<n;i++) #define inf 1000000007 typedef long long ll; using namespace std; typedef pair<ll,ll> P; priority_queue<P,vector<P>,g…</p,vector<p></n;i++)></queue></string></vector></algorithm></iostream>

単調増加を見つけて累積和にする 割と愚直に解法が見えてくるので、やるだけ こんな雰囲気の600~700点は条件整理や添え字,<と<=の確認とかが鍵だけど、今回は楽だった #include<iostream> #include<algorithm> #include<vector> #define lol(i,n) for(int i=0;i<n;i++) using namespace std; long long a[100010],lis[100010]; long long ans[100010]; int main(){ int n;cin>>n; long long sum=0; l…</n;i++)></vector></algorithm></iostream>

MOD付きコンビネーション数を求める 逆元テーブルとか。 MODが素数のとき限定だが、10^9+7も含めてだいたい素数 計算量は前処理O(Nmax+logMOD)、計算にO(1) #define MOD 1000000007 #define Nmax 200010 long long inv[Nmax],fact[Nmax],invfact[Nmax]; void…

最大公約数を求めるgcd関数 ユークリッド互除法によってaとbのgcdが求まる 計算量はO(log min(a,b) )らしい long long gcf(long long a,long long b){ if(!a|!b)return 0; do{ if(a

競プロをやる segtreeを名乗って競技プログラミングをしている idはynymxiaolongbaoで、AtcoderやJOIが主 はてなブログをやる このぺージは精進表として解いた問題を乗っけたり テンプレートを置いたりする Rating AtCoder : loading Codeforces : loading T…