yukicoderでよく使うのでメモ bool is_kadomatsu(ll a, ll b, ll c){ if(a==b || b==c || a==c){ return false; } ll diff0 = b-a; ll diff1 = c-b; if(diff0*diff1<0){ return true; }else{ return false; } }

Quiz https://yukicoder.me/problems/no/721 AC Code https://yukicoder.me/submissions/355611 その他 C++で日時を扱うより、Pythonとかの方が楽 うるう年とか 閏年の日だけ、カレンダーを書き換えると楽 Code うるう年と、カレンダー bool is_uruu(int y) …

Quiz https://atcoder.jp/contests/abc131/tasks/abc131_e AC Code https://atcoder.jp/contests/abc131/submissions/6142889 解説 https://img.atcoder.jp/abc131/editorial.pdf その他 N==2の時は最短距離が2のものは1本も作れない、よって-1を返して終了…

Quiz https://codeforces.com/contest/1183/problem/E string sが与えられる K個の部分文字列を作るのに必要な最低コストを求めよ 部分文字列tを作るコストは、sから取り除いた文字数である AC Code https://codeforces.com/contest/1183/submission/5617960…

Quiz https://yukicoder.me/problems/no/673 AC Code https://yukicoder.me/submissions/354019 解法 1日目はBC 2日目はBC(1+C) ... D日目はBC(1+...+CD-1) よって等比数列の和の公式から解ける 前提知識 フェルマーの小定理と繰り返し二乗法 https://www.ha…

Quiz https://yukicoder.me/problems/no/731 AC Code https://yukicoder.me/submissions/354013 最小二乗法とは (2次元の場合) (x, y)の点がいくつか与えられた時、それに一番フィットする直線 y = ax + b を求める方法のこと 公式解説 https://yukicoder.me…

Quiz https://yukicoder.me/problems/no/778 0を根とする木にて、a

Quiz No.771 しおり https://yukicoder.me/problems/no/771 AC https://yukicoder.me/submissions/353958 他の人の解説記事 はまやんはまやんさん https://www.hamayanhamayan.com/entry/2019/01/02/214632 解法 Bit DP 蟻本(v2)で言うと、p173の巡回セール…

Quiz https://yukicoder.me/problems/no/747 AC Code https://yukicoder.me/submissions/353782 文字列のmod 前提：10000桁などはlong longに収まらないので文字列として受け取って処理する そういう巨大な数のmod2, mod3, mod6の求め方は以下 mod 2 1の位を…

Quiz https://yukicoder.me/problems/no/539 AC Code https://yukicoder.me/submissions/353645 感想 やるだけなのだが、意外と骨が折れる 文字列で表された数字の和はたまに作ることがあるので関数化しておきたい 文字列で表された数字の和 string zero_pad…

Quiz https://codeforces.com/contest/1180/problem/D 内容 (1, 1)からスタートしてm x n のグリッドの各マスを踏んでいく その時の移動をベクトル(dx, dy)とする 同じベクトルを使わずに、グリッドをすべて踏むような移動を構築せよ AC Code https://codefo…

Quiz https://codeforces.com/contest/1180/problem/C AC Code https://codeforces.com/contest/1180/submission/55893151 観察 シミュレーションしてみる 一番大きい値が左端に来た後は、居座る その後は、左端以外で周期的になる a, mの範囲が広いので周期…

Quiz https://codeforces.com/contest/1180/problem/B AC Code https://codeforces.com/contest/1180/submission/55881910 観察 3 <--> -4 のように、操作を2回やると同じ値に戻ってくる 正→負に変換したときに絶対値が増える 解法 同じ操作をすれば元に戻る…

Quiz https://codeforces.com/contest/1180/problem/A AC Code https://codeforces.com/contest/1180/submission/55876143 解法 数列は1, 5, 13, 25, ... OEISに聞く https://oeis.org/search?q=1%2C+5%2C+13%2C+25&language=english&go=Search 計算量 O(1)

Quiz https://yukicoder.me/problems/no/755 AC Code https://yukicoder.me/submissions/353176 解法 二次元累積和 その他 1-indexedで考えて、添字0の箇所は0で埋めておくと、sumを求めるときの引き算が統一的に扱えるのでバグりにくい ll sum = A[x1][y1] …

Quiz https://yukicoder.me/problems/no/594 AC Code https://yukicoder.me/submissions/353171 解法 x, y, zそれぞれに三分探索 探索範囲が200 2クエリで範囲を2/3にできる 2/3を15回繰り返せば200は1より小さくなり、30クエリ程度で各座標を特定できる ク…

#include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/tag_and_trait.hpp> using namespace __gnu_pbds; これね。K番目の値をlogNで取り出せるsetのようなデータ構造(tree)が使えるそう ext以下がほしい githubのサブディレクトリをDLしたい svn exportすればいいそうだが、フォルダのみでファイルが落ち</ext/pb_ds/tag_and_trait.hpp></ext/pb_ds/tree_policy.hpp></ext/pb_ds/assoc_container.hpp>…

Quiz https://atcoder.jp/contests/arc001/tasks/arc001_3 8クイーン問題で、3つのクイーンがすでに置かれている。残りの5つを配置せよ AC Code https://atcoder.jp/contests/arc001/submissions/6028256 解法 最初の3つが条件を満たして置かれているなら、…

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 = s…

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度回転を実装すると楽 注意※ 上記ACでは文字の行列を回転し…

Quiz https://codeforces.com/contest/1176/problem/E 高々N/2個の頂点で点被覆せよ AC https://codeforces.com/contest/1176/submission/55399046 bfsで黒と白(0, 1)に塗っている 解法 グラフを2色に塗る（例えば白と黒とする） 現在見ているノードを白で塗…

用語 LSB : least significant bit 一番右の立っているビット MSB : most significant bit 一番左の立っているビット LSB 求め方 a = 1010 -a= 0110 (足すと0になる) a & (-a) = 0010 (LSB) その1: LSBを0にする 一番右の立っているビットを消す 例 101010 (…

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)で求められる