Quiz https://codeforces.com/contest/1206/problem/D 2000人が解いているので解けなきゃいけない Submit なし 解法 https://codeforces.com/blog/entry/69158 まず、ビットで考えた時に同じビット位置が１のものが３つ存在したら、サイクルの長さ３で終了 …

Quiz https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_b Submission https://atcoder.jp/contests/cf16-exhibition-final-open/submissions/7185546 成果物のライブラリ // ヘロンの公式（三角形の面積） double heron…

https://youtu.be/JTH27weC38k?t=2936 この辺の話題 LとRをペアにする方法は何通りあるか？ これは左から人間が右に歩いていき、Lがあれば溜め込み、Rとぶつかったら溜め込んだLのどれかとマッチングさせてLを1減らすことを繰り返せばいい 具体的に数えてみ…

gcd(a, b) = gcd(b, a) gcd(a, 0) = a gcd(a, 1) = 1 gcd(x+y, x) = gcd(y, x) gcd(2x, 2y) = 2 gcd(x, y) 係数を前に出した

動機 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グループに分割する方法 N>=K グループは区別しない（箱に名前はない）し、箱の順番もない ( (1,3,1)と(1,1,3)などは同じものとする) AC (old, 漸化式埋めVER) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3786812#1 (new, memo) http…

関数化した。code トポロジカルソートを使う別の問題 (verified) トポロジカルソートとdfs逆順の関係 木ではない帰りがけの使用例 Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B AC ✅http://judge.u-aizu.ac.jp/onlinejudge/revie…

分割数の定義 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://…