分割数の定義 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のように同一…

Quiz https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a AC Code https://atcoder.jp/contests/tkppc4-2/submissions/6608047 感想 1WAしてしまった yが0以上の偶数であれば、飛ぶ回数は決まる それがn回、たとえば5だとすると、xとして作れるのは-5, …

Quiz https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i AC Code https://atcoder.jp/contests/tkppc4-1/submissions/6601047 解法 editorialの通り https://drive.google.com/file/d/1CApCqwK7Hfgu81nqysUaPxSU2INI7l6R/view ただ、配列D, Uの定義は …

Quiz https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g AC Code https://atcoder.jp/contests/tkppc4-1/submissions/6599079 解法 例えば7なら2x2x3 = 12で最大なので「2に分解していけばいいんやろ？」と思っていたが間違い 6は、2x2x2=8とするより…

1 2 1 2 1 => 5 となるような関数を作った。再利用することがあるかも ジグザグ数と名付けた 冗長に書いてある 使用例 (to verify) D - スキップ https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d AC Code https://atcoder.jp/contests/tkppc4-1/subm…

Quiz https://atcoder.jp/contests/abc135/tasks/abc135_d 内容 解法というか、左からDP, 右からDPのどちらでも解けますというメモです 解法 文字列の左からDP AC Code https://atcoder.jp/contests/abc135/submissions/6595777 公式解説と同じで、DPの添字…

CSS generator https://kawmra.github.io/hatena-syntax-highlight-css-generator/ CSSをはてなブログの設定からCSSに追記 変更後 #include<bits/stdc++.h> using namespace std; using ll = long long; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const</b)></class></bits/stdc++.h>…

LIS 最長増加部分列のこと 部分列において、狭義単調増加(a1 < a2 < a3 ... ) 広義VERもある（下記） 解説 https://ikatakos.com/pot/programming_algorithm/dynamic_programming/longest_common_subsequence 配列L[i] : 長さiのLISの中で末尾の最小値 LISで…

Quiz https://yukicoder.me/problems/no/852 AC Code https://yukicoder.me/submissions/363142 参考 yukicoder 218A Rubyでホイ。FAみたいです。やったね。B 誤読とかオーバーフローしてつらい。各文字について一つも含まない区間を数え上げ。D 素数の個数…

Quiz https://atcoder.jp/contests/abc038/tasks/abc038_c AC Code https://atcoder.jp/contests/abc038/submissions/6545083 解法 単調増加が続いている長さをLとすると、そこから単調増加列は1+2+...+L個取れる

Quiz https://atcoder.jp/contests/arc010/tasks/arc010_2 AC Code https://atcoder.jp/contests/arc010/submissions/6536656 解法 土曜・日曜に休日フラグを立てておく 祝日の場所もフラグを立てる。すでに立っていたら、以降の立っていない箇所を立てる（…

Quiz https://arc011.contest.atcoder.jp/tasks/arc011_3 AC Code https://arc011.contest.atcoder.jp/submissions/6535492 解法 wordをグラフのNodeとする 編集距離が1のNode同士をつなげる （編集距離と言っていいのは微妙。追加・削除がないので） bfsでf…

Quiz https://atcoder.jp/contests/arc012/tasks/arc012_3 AC Code https://atcoder.jp/contests/arc012/submissions/6530124 感想 やるだけかと思っていたが想定漏れが多くて何度もWA 斜めの処理は意外とやったことがなくて練習になった テストケースをあげ…

Quiz https://atcoder.jp/contests/arc009/tasks/arc009_3 AC Code https://atcoder.jp/contests/arc009/submissions/6521277 モンモール数を求める シグマの入った一般式は負の符号が出てくるので避け、漸化式からdp的に求めた 大きい値でWAが出たので対処…

Quiz https://codeforces.com/contest/1178/problem/B AC Code https://codeforces.com/contest/1178/submission/57485678 解法 vvをwに変換 oを見つけるたびに、そのoの左にあるw, 右にあるwの数を求めて答えに足す

制約 荷物数N=100 バッグの容量の最大値W=10000 買うか買わないか(1 or 0) その他 計算量 O(NW) 最も一般的なナップサック問題 解き方 その１：dp[i][j] その２：メモ化再帰 rec(i, j) Quiz https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B AC code http…

bitsetの使い方 今までは2進数表示でprintするときしか使っていなかった 以下のような使い方ができる int main(){ cin.tie(0); ios::sync_with_stdio(false); bitset<10> dp; dp[0] = 1; dp[3] = 1; cout << dp << endl; dp |= (dp<<1); // 左に1シフトして…

前提環境 Windows 10 Visual Studio Code (VSC)でcppコードを書く VSC内でTerminalを開くとWSLになっているように設定済み g++でコンパイル なくてもコンパイルは通る WSLではincludeパスが通っているのであろう、コンパイルは通る しかし、VSC側で #include<bits/stdc++.h></bits/stdc++.h>…

基本 qiita.com Windows WSL Visual Studio Code内からWSLを読んでコンパイル 追加でoj テストケースDLや実行が楽になる github.com 落とし穴 oj sで提出した後、提出後URLに自動で飛んでくれるが、設定が必要 環境変数設定 vi ~/.bashrc 下記を書く。 expor…

Quiz https://yukicoder.me/problems/no/742 解法 転倒数 計算量 BITを使えばO(NlogN)で求まる。これが想定解であろう 計算量2 バブルソートで数えるとO(N2) 今回の制約の場合、9 * 108 なんとこれでも通ってしまった https://yukicoder.me/submissions/3592…

Quiz https://codeforces.com/contest/1111/problem/C AC Code https://codeforces.com/contest/1111/submission/56781314 解法 考えている範囲で一気に燃やすコスト 考えている範囲を二分割して個別に燃やすコスト 上記２つのうち、安い方を選ぶように再帰…

Article https://codeforces.com/blog/entry/61587 代わりに mt19937 shuffle を使おうとのこと random_deviceじゃだめなのか？ 実装により、出力される乱数が固定される std::random_deviceに騙された。 実装によっては決定的な値しか返さないのか…https://…

Quiz https://codeforces.com/contest/1114/problem/C AC Code https://codeforces.com/contest/1114/submission/56636163 map<ll, ll> factorize(ll n){ map<ll, ll> mp; ll sq = sqrt(n); FOR(i, 2, sq+1){ while(n%i==0){ mp[i]++; n/=i; } } // 残り if(n!=1){ mp[n]++; </ll,></ll,>…

Quiz https://codeforces.com/contest/1114/problem/D AC Code https://codeforces.com/contest/1114/submission/56634318 LCSのvector versionがある 解説 1 2 3 4 5 を考えてみる この場合はどこから始めても、4回の塗りが必要。一般に、N-1回塗れば同色に…

Quiz https://codeforces.com/contest/1189/problem/C AC Code https://codeforces.com/contest/1189/submission/56582743 観察 クエリ数が多いので、1クエリあたりO(1), O(logN)あたりで解かないと間に合わない 愚直にシミュレーションしたら間に合わない …

Quiz https://codeforces.com/contest/1108/problem/E1 AC Code https://codeforces.com/contest/1108/submission/56534524 解法 制限が緩いので全探索 A[i]のそれぞれが最終的にmaxになる値だとする その時、iを含むsegmentを適用する理由はない なので、i…

Quiz https://codeforces.com/contest/1113/problem/C AC Code https://codeforces.com/contest/1113/submission/56527349 解法 上記のように、左端〜右端のXOR=0のものが数える候補 式変形により、もはやcenterを意識する必要がなくなる 任意区間のXORは、…

Quiz https://codeforces.com/contest/1136/problem/D AC Code https://codeforces.com/contest/1136/submission/56483886 参考 https://cinnamo-coder.hatenablog.com/entry/2019/03/12/033934 ポイント 一番後ろ（私）が前の列の人を追い抜くのではなく、…

Quiz https://codeforces.com/contest/1061/problem/D AC Code https://codeforces.com/contest/1061/submission/56465574 解法 showの開始順にソート 空いているTVがあり、それを使った方が「新規に借りるよりも得」の場合は再利用する その時、空いているT…

Quiz https://codeforces.com/contest/1061/problem/B AC Code https://codeforces.com/contest/1061/submission/56446523 参考 こどふぉdiv2A:(s+n-1)/nB:ソートして画像みたいに前の高さ持って橙の部分を選ぶ感じC:dp[j][i]:=iまでで長さjの列を作るときの…