Quiz https://atcoder.jp/contests/arc001/tasks/arc001_3 AC Code https://atcoder.jp/contests/arc001/submissions/6028256 解法 最初の3つが条件を満たして置かれているなら、まだ空いているX座標、Y座標は共に5つ候補がある それらをnext_permutationで…
Quiz https://atcoder.jp/contests/arc001/tasks/arc001_2 AC Code https://atcoder.jp/contests/arc001/submissions/6027127 解法 ワーシャルフロイドでも解けると解説に書いてあったので、その方法をあえて使ってみる -10, -5, -1, 1, 5, 10度差の状態へは…
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 = ss.str(); r…
const int N_MAX = 1e7 + 10; bool is_prime[N_MAX]; // エラトステネスのふるい void Eratosthenes(){ FOR(i, 0, N_MAX){ is_prime[i] = true; } is_prime[0] = false; is_prime[1] = false; for(ll i=2; i*i<=N_MAX; i++){ if(is_prime[i]){ int p = i; in…
Quiz https://yukicoder.me/problems/no/513 インタラクティブ問題 query(x, y)を投げると、宝までのマンハッタン距離が返ってくる 最大100クエリで場所を求めよ ACコード https://yukicoder.me/submissions/351288 x, yは独立に求められる 以下ではxを求め…
Quiz https://codeforces.com/contest/1182/problem/E Note Editorial https://codeforces.com/blog/entry/67614 天才かよ！？と思った点 cxを分解（分配）することでcx fxの形にできる 三項の積になるが、g(x, p)を導入して三項の和にする するとトリボナッ…
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度回転を実装すると楽 成果物 行列の回転 行列の拡大 …
Quiz https://codeforces.com/contest/1176/problem/E ACコード https://codeforces.com/contest/1176/submission/55399046 解法 グラフを2色に塗る（例えば白と黒とする） 現在見ているノードを白で塗ったなら、隣はできるだけ黒で塗るようにする 塗り終わ…
用語 LSB : least significant bit 一番右の立っているビット MSB : most significant bit 一番左の立っているビット その1: LSBを0にする 一番右の立っているビットを消す 例 101010 (n) 101001 (n-1) ------ (&) 101000 その2: 2のべき乗判定に使える nが2…
Quiz https://yukicoder.me/problems/no/267 Submission https://yukicoder.me/submissions/350277 解法 vector<pair<int, int> > Aをソートすると、firstの昇順でソート、firstが同じグループの中ではsecondの昇順でソートされる それを使うことを見越して絵柄(D, C, etc)</pair<int,>…
Quiz https://yukicoder.me/problems/no/71 Submission https://yukicoder.me/submissions/350266 考察 N=5 普通のそろばんと同じ数 1, 4に分けると0〜9までの10種類を表現できる 一方、サンプルケースでは2, 3に分けることで11種類を表現できる 等分すると…
Quiz https://yukicoder.me/problems/no/754 Submission https://yukicoder.me/submissions/350209 解法 N=3で書いてみると以下の和を求めればいいと分かる 配列AかBの累積和を持っておけば、和はO(N)で求められる
#include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> #include <iostream> namespace mp = boost::multiprecision; // 任意長整数型 using Bint = mp::cpp_int; // 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする) using Real = mp::number<mp::cpp_dec_float<512>>; 参考 https://qiita.com/tubo28…</mp::cpp_dec_float<512></iostream></boost/multiprecision/cpp_int.hpp></boost/multiprecision/cpp_dec_float.hpp>
Quiz https://atcoder.jp/contests/utpc2012/tasks/utpc2012_04 Submission https://atcoder.jp/contests/utpc2012/submissions/5719321 解法 点(a, b)が点(b, c)に縮小・回転・移動されている 縮小・回転は複素数の掛け算・割り算、平行移動は複素数の和・…
Quiz https://atcoder.jp/contests/utpc2012/tasks/utpc2012_03 Submission https://atcoder.jp/contests/utpc2012/submissions/5717188 解法 N=5000など大きい時、辺の本数 N*(N-1)/2 = 125万ほど Q=100000で辺を取っても木になりえないので全てN より厳密…
強連結とは 「有効」グラフにて、各頂点が行き来できる状態 強連結成分分解とは 有向グラフを、強連結なグラフに分解すること 縮約とは 頂点をマージすること 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)で求める 例 1 2 3 -2 5の場合 全てを取った時が最大で、答えは9 参考 https://ark4rk.hatenablog.com/entry/2018/01/08/002508 Quiz https://practice.geeksforgeeks.org/problems/kadanes…
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…
![はてなブックマーク - グローバル変数ならint dp[10000][10000]してもOK !? (400MB)](https://b.hatena.ne.jp/entry/image/http://perogram.hateblo.jp/entry/2019/05/23/135253)
Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589709#1 解法 Kruskal法を使う 同じグループ判定にUnion Findを使う エッジコストの小さい順に取り出…
Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589692#1 参考 https://ei1333.github.io/luzhiled/snippets/graph/bellman-ford.html その他 競プロでの問題で…
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 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/cce6fc5c579051e64fab その他 r…
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 …
