ライブラリ
Quiz https://yukicoder.me/problems/no/60 AC✅https://yukicoder.me/submissions/443826 クラス化した struct Imos2D{ VV A; ll H,W; Imos2D(ll h, ll w){ H = h; W = w; A.resize(H, VI(W)); } // [(y0,x0), (y1,x1)] void add(ll y0, ll x0, ll y1, ll x1…
Quiz https://yukicoder.me/problems/no/875 AC code https://yukicoder.me/submissions/442780 補足 クエリに答えるときに、min値を持つ場所のindexを返す必要がある だから min + index = mindex というタイトルなのだろう 遅延なしSegTreeは書いたことが…
Quiz https://atcoder.jp/contests/abc157/tasks/abc157_f AC code https://atcoder.jp/contests/abc157/submissions/10485169 交点コードはここにある 解法 snukeさんの解説放送を見て、snukeさんの幾何コードを貼る https://www.youtube.com/watch?v=TdR81…
Quiz https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho1 AC code https://atcoder.jp/contests/joi2012ho/submissions/10256473 解法 Oの連続数に注目する 例えばOOOがあったとき（連続したOが3個でその隣は違う文字）、レベル3しか作りえない レベル…
bfsってやるだけなんだけど、これまで汎用化していなかった たたき台としてここに書いておく verified E - チーズ (Cheese) ✅https://atcoder.jp/contests/joi2011yo/submissions/10254552 D - Grid Repainting ✅https://atcoder.jp/contests/abc088/submiss…
Quiz https://atcoder.jp/contests/past201912-open/tasks/past201912_k AC https://atcoder.jp/contests/past201912-open/submissions/9277571 解法 LCA Code // LCA set VV G; const int N_MAX = 150010; const int MAX_LOG_V = 20; ll depth[N_MAX] = {};…
Quiz https://yukicoder.me/problems/no/225 AC https://yukicoder.me/submissions/408789 解説 編集距離そのものの問題 編集距離で可能な操作：文字の挿入・削除・置換 int dp[1050][1050]; // dp[i][j]として i : sのi文字目 j : tのj文字目 までを一致さ…
説明 累積XORとは、累積和と同じように事前計算しておくことで範囲のXORをO(1)で求める方法のこと XORの性質 a xor a = 0 a xor 0 = a 上記を利用すると、A = a xor b xor c xor d xor e の値を持っていて c xor d xor e の値が知りたいときは A xor a xor b…
Quiz https://atcoder.jp/contests/abc040/tasks/abc040_d AC (verified) https://atcoder.jp/contests/abc040/submissions/8891107 解説 editorialの通りですが、ポイントとしては「橋の構築」と「クエリ」を同じvectorに入れてyearでソートした後、yearの…
Quiz 最大長方形 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=jp 壁のあるグリッド内で作れる最大長方形の面積を求めよ AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4010799#1 解法 （１）まず、各行を底としたヒ…
Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607 AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4008533#1 解法 毎日売ると考えてよいので、今日と明日だけを見て利益を最大化すればいい 画像のように荷物に置き換えて、個…
動機 1次元累積和クラスはよく使っているため 2次元累積和を使う問題と出会ったため Code // 2次元累積和 struct AccSum2D{ VV Ac; // accumulate ll W; ll H; AccSum2D(){} AccSum2D(VV &A){ H = A.size(); W = A[0].size(); Ac.resize(H+1, VI(W+1)); // i…
参考 http://hos.ac/slides/20140319_bit.pdf そのままC++で実装するとこんな感じ(1-indexed, x,y順の変数) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4890859#1 自分用 0-indexed, y,x順の変数 E： たい焼きマスターと食べ盛り - Taiyaki-Mast…
Quiz E - MUL https://atcoder.jp/contests/arc085/tasks/arc085_c AC Code https://atcoder.jp/contests/arc085/submissions/8316327 解法 アルメリアさんの解説の通り その他 割る・残すは右左のどちらでもいい（今回たまたまアルメリアさんとは逆になった…
Quiz https://atcoder.jp/contests/abc036/tasks/abc036_c 解法 座標圧縮（座圧と呼ばれる）をするだけ AC https://atcoder.jp/contests/abc036/submissions/8143705 // 座標圧縮 // Aをそのまま書き換えるVER void compress(vector<ll>& A){ // 変換表 auto B =</ll>…
// 隣接行列 ll d[100][100]; int main(){ // input ll N, M; cin >> N >> M; // 隣接行列の初期値。infにする rep(i, N){ rep(j, N){ if(i!=j) d[i][j] = inf; } } // 距離データ入力 rep(i, M){ ll a, b, c; cin >> a >> b >> c; a--; b--; d[a][b] = c; d…
Quiz https://atcoder.jp/contests/agc039/tasks/agc039_b AC✅ (解法：二部グラフ判定＆グラフの直径） https://atcoder.jp/contests/agc039/submissions/7879736 解法 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能 構成可能な場合、グラフの…
Quiz https://atcoder.jp/contests/agc039/tasks/agc039_a AC Code https://atcoder.jp/contests/agc039/submissions/7879593 ランレングス圧縮 (復元はできない) // ランレングス // 例 s = "aabccc" => [2, 1, 3] VI run_length(string s){ char prev = s[…
注意 range add, range updateは区別しよう 今回はrange add 使った問題 C - Attack Survival https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加…
意味 N人をKグループに分割する方法 N>=K グループは区別しない（箱に名前はない）し、箱の順番もない ( (1,3,1)と(1,1,3)などは同じものとする) AC (old, 漸化式埋めVER) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3786812#1 (new, memo) http…
関数化した。code トポロジカルソートを使う別の問題 (verified) トポロジカルソートとdfs逆順の関係 木ではない帰りがけの使用例 Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B AC ✅http://judge.u-aizu.ac.jp/onlinejudge/revie…
分割数の定義 n個の互いに区別できない品物を、m個以下に分割する方法の総数をnのm分割といい、m=nのとき特にnの分割数という // 例 5の分割数は、7。なぜならば、 1,1,1,1,1 2,1,1,1 3,1,1 2,2,1 4,1 3,2, 5 の7種類があるから ※1,3,1 == 3,1,1のように同一…
ACコード https://yukicoder.me/submissions/352443 Code baseで割って余りを記録し、逆順に読む ※バグあり string change_base(ll a, ll base){ if(a==0) return "0"; stringstream ss; while(a){ ll rest = a%base; ss << rest; a /= base; } string s = s…
Quiz https://yukicoder.me/problems/no/397 ACコード https://yukicoder.me/submissions/351014 その他 バブルソートは関数化しておくと、今回のように交換したインデックスの組 (i, j) や、交換回数をカウントして反転数を求めるときに少し付け足すだけで…
Quiz https://yukicoder.me/problems/no/565 行列の回転（90度刻み）、拡大（整数倍）を実装せよ AC https://yukicoder.me/submissions/350976 その他 90度回転を何度か重ねがけすることで180, 270度回転を実装すると楽 注意※ 上記ACでは文字の行列を回転し…
用途 負の値も含みうる数値配列にて、隣接した部分和の最大値を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=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 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…
vector<string> split_str(string s, char c){ vector<string> ret; stringstream ss; FOR(i, 0, s.size()){ if(s[i]==c){ ret.push_back(ss.str()); ss.str(""); ss.clear(); }else{ ss << s[i]; } } ret.push_back(ss.str()); return ret; } How to use vector<string> S = split_s</string></string></string>…
