強連結 (strongly connected) とは 「有向」グラフにて、各頂点が行き来できる状態 強連結成分分解とは 有向グラフを、強連結なグラフに分解すること 縮約とは 頂点をマージすること DAGとは Directed Acyclic Graph 有向グラフだけどサイクルしていない、つ…

Quiz https://practice.geeksforgeeks.org/problems/longest-valid-parentheses/0 Submission https://practice.geeksforgeeks.org/viewSol.php?subId=14381873&pid=1247&user=peroon 例 4 (()( ()()(( ((()()()))) ()(())( 2 4 10 6 Code ll maxLen(string …

ペアでない数字は2つ(x, y)あるという設定 例 Input: {12, 23, 34, 12, 12, 23, 12, 45} Output: 34 and 45 ソートすれば O(n log n) しかしO(n)の解法がある https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array…

例 https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/ 内容 bfsの引数に vector &path も渡して入れていく 奥まで見に行って見つからなかったら path.pop_back() して詰めたものをキャンセルする

用途 負の値も含みうる数値配列にて、隣接した部分和の最大値をO(N)で求める 読み方はカダネではなく、ケイデインズ 最大部分列和(maximum segment sum)と言われる 最大部分和問題 Maximum subarray problem https://en.wikipedia.org/wiki/Maximum_subarray…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0647 他人の解法 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3593831#1 説明 例えば4人来客、マッチ3本の場合、1つの隙間部分は点けっぱなしにする必要がある 隙間の間隔は小さ…

Quiz https://codeforces.com/contest/1169/problem/C Submission https://codeforces.com/contest/1169/submission/54706301 解法 二分探索 解説 増やす回数を決め打ちした時、配列Aを前から見ていく 列の前方をできるだけ小さく保ちながら増加列にしていく…

Quiz https://practice.geeksforgeeks.org/problems/minimum-swaps/1 Submit https://practice.geeksforgeeks.org/viewSol.php?subId=14251643&pid=700384&user=peroon 解法 例として 2 4 5 1 3 を考える N-1, つまり4回swapすれば確実にソートできる。もっ…

競プロで言うメモリ制限とはスタック領域のことなのだろうか グローバル変数は静的領域にメモリ確保される グローバルなら dp[10000][10000]も可能 だけど「関数内ではスタック領域から確保するからやめようね」と書いてある https://wikiwiki.jp/kyopro/%E3…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589709#1 解法 Kruskal法を使う 辺を列挙し、コストの軽いものから見ていって非連結じゃない頂点をつなぐなら採…

ベルマンフォードとは？ 単一始点最短距離を求める 辺の重みが負でもいい その代わりにダイクストラより遅い。O(VE) 負閉路が検出できる 具体例 Quiz 単一始点最短経路（負の重みをもつ辺を含む） http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589681#1 参考 https://imoz.jp/algorithms/imos_method.html 2次元imosの説明が書いてあり、まさにこれ！ まと…

Quiz Weighted Union Find Trees http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp Submit http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3586483 学習 けんちょんさんの記事で学んだ https://qiita.com/drken/items/cce…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_B 解法など http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3586431 貪欲に「重さ当たりの価値」が高いものから取っていけばいい 「重さ当たりの価値」を求めるには v / w …

前回の説明 http://perogram.hateblo.jp/entry/rolling_hash これでは通らない問題もあった（下記） そこで、蟻本にならってh=264バージョンで書き直すとAC. 先人の知恵 Code // ローリングハッシュ // h = 2^64にすることでmod不要 using ull = unsigned lo…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3610307#1 参考 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2084544#1 解法 各盤面を状態としたb…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp Submit http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3579423#1 座標圧縮とは 大小関係を保ったまま、値のスキマをなくすことで値域を減らす 例 [1, 100, 10000…

if(sw <= W){ ll tv = (lower_bound(ps,ps+m,pll(W-sw,INF))-1)->second; res = max(res,sv+tv); } 後半、こういう箇所がありますよね -1を引くとどうなるか。イテレータの1つ手前を指す 「W-swピッタリの重さがあったら、-1しちゃダメなのでは？」と疑問を…

いつも皆様の解答Tweetには助けられています ただ、TLなので流れてしまうしGoogle検索では見つけづらい Likeした後にTogetterしたら簡単に作れた こうして検索可能になっていると、後から精進する人のサポートになるだろう 1番いいのはリアルタイムでコンテ…

利点 1<<63とかしたときに指摘してくれる（正しくは1LL<<63と書くべき） 書き換え vi ~/.bash_profile 書くこと alias g++="g++ -g -fsanitize=undefined -Wall -std=c++14" 読み込む Terminalを起動したまま設定を反映するなら必要 再度Terminalを開くとき…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_10_C Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3574878#1 参考 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3160740#1 こんな感じでbitsetを使う…

Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3574809#1 Code #include<bits/stdc++.h> using namespace std; using ll = long long; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() ostream& operator<<(ostream</bits/stdc++.h>…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3574803#1 説明 5変数を辞書順にソート 値なら小さい順、文字列なら辞書順なので、2変数ならpairでやっていた …

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_2_A Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3574409#1 説明 AOJも埋めていこうかなと。 上記はstackを使う問題 スタックサイズが0の時にtop(), pop()すると…

Quiz https://codeforces.com/contest/1165/problem/F2 Submission https://codeforces.com/contest/1165/submission/54169433 解法（引用） F:答え決め打ってにぶたん 「x日までに買えるか」の判定問題にした場合、最適な買い方は、「x日までにセールが無い…

Quiz https://codeforces.com/contest/1165/problem/D Submission https://codeforces.com/contest/1165/submission/54147350 解法 Codeforces Round #560 (Div. 3) お疲れ様でしたA:下x桁を見る y桁目は1 それ以外は0にするB:ソートして昇順に見る 次が使え…

解法 E:(最小化すべき関数)=(summation from i = 1 to n){i * (n + 1 - i) * a[i] * b[i]}なので、i*(n+1-i)*a[i]が大きいものから順に小さいb[i]をぶつける— こるとん (@kyort0n) 2019年5月14日 E A[i]は(i+1)*(n-i)回ずつ使われるので、A[i]にかけておく。…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3565113#1 解法 範囲内の最小値を求めるセグメント木を作ればよい その他 Range Sumのセグ木を持っていたのでそ…

Quiz https://yukicoder.me/problems/no/424 Submission https://yukicoder.me/submissions/346632 解法 普通のbfsは上下左右の4点を見るが、今回ははしごも考慮した8点を見る 良い点 問題設定が3DCGで分かりやすく説明されている。 注意点 1 <= sx <= h と…

Quiz https://codeforces.com/contest/1159/problem/B Submission https://codeforces.com/contest/1159/submission/54048500 実験 サンプル3を見る |i-j| = 3のとき、minは717 k x 3 <= 717 k <= 239 これは答えと一致する 解法 |i-j|を幅と呼ぶことにする …