perogram

C++の改行でendlは'\n'の20倍遅い

対象者 coutを使っている 確認コード 1466ms https://codeforces.com/contest/1220/submission/62112806 78ms https://codeforces.com/contest/1220/submission/62113199 差分 coutの改行でendlを使ったのが1番目、'\n'を使ったのが2番目 500000行ほど出力す…

B - The Number of Products

Quiz https://codeforces.com/contest/1215/problem/B Submission https://codeforces.com/contest/1215/submission/62082416 解法 dpのようにi番目まで考えた時の ansP (正の組み合わせ数) を考える A[]の値は+1, -1に単純化しておく 前から i まで見ていっ…

B - Graph Partition ~二部グラフ判定&グラフの直径~

Quiz https://atcoder.jp/contests/agc039/tasks/agc039_b AC Code (二部グラフ判定&グラフの直径) https://atcoder.jp/contests/agc039/submissions/7879736 解法 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能 構成可能な場合、グラフの直…

A - Connection and Disconnection

AGC

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[…

No.898 tri-βutree ~LCA~

LCA

Quiz https://yukicoder.me/problems/no/898 Submission https://yukicoder.me/submissions/387090 解法 editorialの通り dijkstraとLCAの過去コードをコピーペースト その他 全点間距離が必要?ワーシャルフロイド?制約的に無理・・・ と思ったけれどLCAを…

D - Menagerie

Quiz https://atcoder.jp/contests/abc055/tasks/arc069_b AC Code https://atcoder.jp/contests/abc055/submissions/7840056 解法 editorialの通り、添字0, 1の動物を決めてしまえば連鎖的に後ろが決まる 最後に整合性チェックをするのだが、私は最初、動物…

pのk乗はoverflowするか?

https://codeforces.com/contest/1228/problem/C この問題を解いていて、入力nが1018までなので、long longギリギリまで入力されうる pow(p, k)をナイーブに求めたらoverflowするし、modをとると正しく判定できない ということで判定関数を作った pk > 1018…

F - Pure ~ワーシャルフロイドと最小閉路~

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…

B - Sorting a Segment

Quiz https://atcoder.jp/contests/agc038/tasks/agc038_b Submission https://atcoder.jp/contests/agc038/submissions/7654290 解法 editorialは読み、解説放送も見たとする まったく被りなしの場合は答えがN-K+1で、これが最大。ここからダブルカウントし…

同じ問題をZ-Algorithm, Suffix Array, Rolling Hashで解く

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つのロリハでは衝突してしまったのだろう 衝突回避のために取れる手段…

BITを2つ使って範囲更新・範囲和 (区間更新・区間和)

使った問題 https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加える 範囲和 [a, b)の和を求める (計算量 : それぞれlog(N)) 内部実装 差分をBITで…

C - Align

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と置いたほうがよ…

D - Face Produces Unhappiness

Quiz https://atcoder.jp/contests/abc140/tasks/abc140_d Submission https://atcoder.jp/contests/abc140/submissions/7498421 解法 editorialの別解の方だと楽です(別解じゃない方も通したけど苦労した)。つまり、 連続したL, Rは圧縮して1文字にする …

A. You Are Given Two Binary Strings...

Quiz https://codeforces.com/contest/1202/problem/A Submit https://codeforces.com/contest/1202/submission/60410011 解法 文字列をs, tとする 2kをかけることは左シフトと同じ tを左に滑らせていき、足して反転させたものを辞書順最小にすればいい 最後…

D. Shortest Cycle

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

B - Inscribed Bicycle

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…

【数え上げ】L, Rのマッチング。Lを溜め込んで歩いてRとぶつかったら

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

gcd 性質

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) 係数を前に出した

「別のクラスの人と3人組を作ってきてください」

動機 codeforcesでこの問題が解けなかった https://codeforces.com/contest/1201/problem/B 内容:数列Anからどれか2つを選んで-1することを繰り返し、数列を全ゼロにできるか i != j 解答は、max x 2 > sum のときNo, それ以外でYes maxが飛び抜けちゃうと…

D - Gathering Children

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…

No.269 見栄っ張りの募金活動 ~分割数~

n個の互いに区別できない品物を、m個以下に分割する方法の総数をnのm分割と言い、m=nのとき特にnの分割数と言う。 Quiz https://yukicoder.me/problems/no/269 AC Code https://yukicoder.me/submissions/364228 解法 先にK円ずつ増えていく分を徴収する 残…

A - Jumping!! ~負値をmodするべからず~

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, …

I - school competition 1

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の定義は …

G - バラバラ掛け算

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とするより…

ジグザグ数 zigzag

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…

D - Digits Parade ~右からDP, 左からDP~

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

コードの背景色は黒でしょ!CSSを変更しました。

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