対象者 coutを使っている 確認コード 1466ms https://codeforces.com/contest/1220/submission/62112806 78ms https://codeforces.com/contest/1220/submission/62113199 差分 coutの改行でendlを使ったのが1番目、'\n'を使ったのが2番目 500000行ほど出力す…
Quiz https://codeforces.com/contest/1215/problem/B Submission https://codeforces.com/contest/1215/submission/62082416 解法 dpのようにi番目まで考えた時の ansP (正の組み合わせ数) を考える A[]の値は+1, -1に単純化しておく 前から i まで見ていっ…
Quiz https://atcoder.jp/contests/agc039/tasks/agc039_b AC Code (二部グラフ判定＆グラフの直径） https://atcoder.jp/contests/agc039/submissions/7879736 解法 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能 構成可能な場合、グラフの直…
Quiz https://atcoder.jp/contests/agc039/tasks/agc039_a AC Code https://atcoder.jp/contests/agc039/submissions/7879593 ランレングス圧縮 (復元はできない) // ランレングス // 例 s = "aabccc" => [2, 1, 3] VI run_length(string s){ char prev = s[…
Quiz https://yukicoder.me/problems/no/898 Submission https://yukicoder.me/submissions/387090 解法 editorialの通り dijkstraとLCAの過去コードをコピーペースト その他 全点間距離が必要？ワーシャルフロイド？制約的に無理・・・ と思ったけれどLCAを…
Quiz https://atcoder.jp/contests/abc055/tasks/arc069_b AC Code https://atcoder.jp/contests/abc055/submissions/7840056 解法 editorialの通り、添字0, 1の動物を決めてしまえば連鎖的に後ろが決まる 最後に整合性チェックをするのだが、私は最初、動物…
https://codeforces.com/contest/1228/problem/C この問題を解いていて、入力nが1018までなので、long longギリギリまで入力されうる pow(p, k)をナイーブに求めたらoverflowするし、modをとると正しく判定できない ということで判定関数を作った pk > 1018…
Quiz https://atcoder.jp/contests/abc142/tasks/abc142_f Submission https://atcoder.jp/contests/abc142/submissions/7805082 解法 ワーシャルフロイドを使った最小閉路の検出 algorithm - graph - How to find Minimum Directed Cycle (minimum total we…
Quiz https://atcoder.jp/contests/agc038/tasks/agc038_b Submission https://atcoder.jp/contests/agc038/submissions/7654290 解法 editorialは読み、解説放送も見たとする まったく被りなしの場合は答えがN-K+1で、これが最大。ここからダブルカウントし…
Quiz https://atcoder.jp/contests/abc141/tasks/abc141_e 3パターンで解いた。とはいえ完全に「けんちょん」さんの記事に依存している 解いた順に書く あとから検索する用に書いている。1度使ったコードは安心感があるため 1. ローリングハッシュ（ロリハ）…
Quiz E - Who Says a Pun? https://atcoder.jp/contests/abc141/tasks/abc141_e Submission https://atcoder.jp/contests/abc141/submissions/7553482 衝突した状況 途中のデータでWA. 1つのロリハでは衝突してしまったのだろう 衝突回避のために取れる手段…
使った問題 https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加える 範囲和 [a, b)の和を求める (計算量 : それぞれlog(N)) 内部実装 差分をBITで…
Quiz https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c Submission https://atcoder.jp/contests/tenka1-2018-beginner/submissions/7508948 ジグザグに配置 editorialに書いてあるとおり、1, 3, 5と置くより1, 5, 3と置いたほうがよ…
Quiz https://atcoder.jp/contests/abc140/tasks/abc140_d Submission https://atcoder.jp/contests/abc140/submissions/7498421 解法 editorialの別解の方だと楽です（別解じゃない方も通したけど苦労した）。つまり、 連続したL, Rは圧縮して1文字にする …
Quiz https://codeforces.com/contest/1202/problem/A Submit https://codeforces.com/contest/1202/submission/60410011 解法 文字列をs, tとする 2kをかけることは左シフトと同じ tを左に滑らせていき、足して反転させたものを辞書順最小にすればいい 最後…
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グループに分ける方法、と理解しています 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>…
