C - パズルのお手伝い (8 queens, 8クイーン問題)

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度差の状態へは…

N進数 7進数 変換 C++

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…

エラトステネスのふるい ver 2

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を求め…

E. Product Oriented Recurrence

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) や、交換回数をカウントして反転数を求めるときに少し付け足すだけで…

No.565 回転拡大

Quiz https://yukicoder.me/problems/no/565 行列の回転(90度刻み)、拡大(整数倍)を実装せよ ACコード https://yukicoder.me/submissions/350976 その他 90度回転を何度か重ねがけすることで180, 270度回転を実装すると楽 成果物 行列の回転 行列の拡大 …

E. Cover it!

Quiz https://codeforces.com/contest/1176/problem/E ACコード https://codeforces.com/contest/1176/submission/55399046 解法 グラフを2色に塗る(例えば白と黒とする) 現在見ているノードを白で塗ったなら、隣はできるだけ黒で塗るようにする 塗り終わ…

n & (n-1)

用語 LSB : least significant bit 一番右の立っているビット MSB : most significant bit 一番左の立っているビット その1: LSBを0にする 一番右の立っているビットを消す 例 101010 (n) 101001 (n-1) ------ (&) 101000 その2: 2のべき乗判定に使える nが2…

No.267 トランプソート

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,>…

No.71 そろばん

Quiz https://yukicoder.me/problems/no/71 Submission https://yukicoder.me/submissions/350266 考察 N=5 普通のそろばんと同じ数 1, 4に分けると0〜9までの10種類を表現できる 一方、サンプルケースでは2, 3に分けることで11種類を表現できる 等分すると…

No.754 畳み込みの和

Quiz https://yukicoder.me/problems/no/754 Submission https://yukicoder.me/submissions/350209 解法 N=3で書いてみると以下の和を求めればいいと分かる 配列AかBの累積和を持っておけば、和はO(N)で求められる

多倍長(自分用メモ)C++

#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>

D - 地図が2枚

Quiz https://atcoder.jp/contests/utpc2012/tasks/utpc2012_04 Submission https://atcoder.jp/contests/utpc2012/submissions/5719321 解法 点(a, b)が点(b, c)に縮小・回転・移動されている 縮小・回転は複素数の掛け算・割り算、平行移動は複素数の和・…

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になる

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

有効な括弧の最大長さ Longest valid Parentheses

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つの数字を見つける。XOR

ペアでない数字は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…

木で値を探しながら経路(path)も保存するbfs

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

kadane's algorithm

用途 負の値も含みうる数値配列にて、隣接した部分和の最大値をO(N)で求める 例 1 2 3 -2 5の場合 全てを取った時が最大で、答えは9 参考 https://ark4rk.hatenablog.com/entry/2018/01/08/002508 Quiz https://practice.geeksforgeeks.org/problems/kadanes…

Stove (AOJ)

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つの隙間部分は点けっぱなしにする必要がある 隙間の間隔は小さ…

C. Increasing by Modulo (Div2)

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

Minimum Swaps to Sort

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すれば確実にソートできる。もっ…

グローバル変数ならint dp[10000][10000]してもOK !? (400MB)

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

最小全域木 MST (minimum spanning tree)

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を使う エッジコストの小さい順に取り出…

ベルマンフォード bellman ford 実装

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 その他 競プロでの問題で…

2次元imos DSL_5_B いもす

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の説明が書いてあり、まさにこれ! まと…

重み付きUnion Find (Weighted Union Find Tree)

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…

割り算を避ける(doubleを避ける)

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 …