動機 codeforcesでこの問題が解けなかった https://codeforces.com/contest/1201/problem/B 内容：数列Anからどれか2つを選んで-1することを繰り返し、数列を全ゼロにできるか i != j 解答は、max x 2 > sum のときNo, それ以外でYes maxが飛び抜けちゃうと…
Quiz https://atcoder.jp/contests/abc136/tasks/abc136_d AC Code https://atcoder.jp/contests/abc136/submissions/6718753 解法 ダブリングやDPを使わない方法です 大量に移動した後は、どこかのRLに落ちて振動します 全てのRLの位置を調べておく 各子供…
意味 N人をKグループに分ける方法、と理解しています AC Code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3786812#1 読んだ https://qiita.com/drken/items/f2ea4b58b0d21621bd51
Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B AC Code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3784044#1 関数化した。Code VI topological_sort(VV& G){ ll N = G.size(); // 入次数 VI IN(N, 0); REP(i, N){ fo…
n個の互いに区別できない品物を、m個以下に分割する方法の総数をnのm分割と言い、m=nのとき特にnの分割数と言う。 Quiz https://yukicoder.me/problems/no/269 AC Code https://yukicoder.me/submissions/364228 解法 先にK円ずつ増えていく分を徴収する 残…
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 最長増加部分列のこと 解説 https://ikatakos.com/pot/programming_algorithm/dynamic_programming/longest_common_subsequence 問題を解いてVerify http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3776378#1 計算量 O(N logN) Note ll N; cin >…
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でfirst wordからlast wordまで到達できるか調べる 経路復元 …
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 Quiz https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B AC Code https://onlinejudge.u-aizu.ac.jp/status/users/peroon/submissions/1/DPL_1_B/judge/3754207/C++14 感想 ナップサックはいろいろな亜種が…
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); cout << dp << endl;…
前提環境 Windows Visual Studio Codeで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 観察 n!内にbがいくつ含まれるかが答え n, b共に値域が広く、O(N)では間に合わない ルジャンドルの定理 n! に含まれる素因数 p の数 …
Quiz https://codeforces.com/contest/1114/problem/D AC Code https://codeforces.com/contest/1114/submission/56634318 解説 1 2 3 4 5 を考えてみる この場合はどこから始めても、4回の塗りが必要。一般に、N-1回塗れば同色にできる 1 2 3 2 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…
