perogram

B - 共通部分文字列 (※LCSとは違う)

JOI

Quiz https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_b ABRACADABRA ECADADABRBCRDARA の最大共通部分列文字列は ADABR 文字列は連続である必要 LCSとは違う(LCSは飛び飛びOK) AC code https://atcoder.jp/contests/joi2008ho/submissions/102362…

C - タイル (Tile)

JOI

Quiz https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_c AC Code https://atcoder.jp/contests/joi2011yo/submissions/10218261 Code (抜粋) int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin >> N; ll Q;cin>>Q; while(Q-…

No.982 Add

Quiz https://yukicoder.me/problems/no/982 公式解法 https://yukicoder.me/problems/no/982/editorial 考えたこと gcd=1じゃなければ-1 lcmの部分まで考えれば良さそう 実際にそれで求まるのだが、公式解説や他の人の解説では分からなかった それは私の数…

C. Cow and Message

Quiz https://codeforces.com/contest/1307/problem/C 解法 https://codeforces.com/blog/entry/73953 補足 indexの関係は「arithmetic progression(等差数列)」になっていなければいけない なので、s=aaabbcccの場合の答えは9が正しい 3x2x3=18ではない i…

精進してても周りの同色より成長しないとレートは上がらないことに気がついた

レートが停滞する時ってありますよね。精進していれば解ける問題が増えていき、レートも上がっていくと何故か思っていた。しかしレートは相対評価。1つ上の色に行きたいなら、同色の人以上の精進をしないと抜きん出ることはできない。 頑張っている人のレー…

重複組み合わせには「数学的なもの」「蟻本的なもの」の2種類がある

数学的なもの nHrと表記されるもの https://mathtrain.jp/tyohukuc 例:{R, G, B}の玉が「無限に」あって、r個選ぶときの場合の数 これはnCrが求められればいいのでn=106程度まで求められる 蟻本的なもの n種類の物体がある i番目の物体は「Ai個」ある r個選…

D. Edge Deletion ~MSTとDijkstraは似ている?~

MST? minimum spanning tree 最小全域木のこと Dijkstra? ダイクストラアルゴリズムのこと Quiz Edge Deletion https://codeforces.com/contest/1076/problem/D 解説 editorialの通り、Dijkstraしつつ辺を追加するごとにカウントアップし、途中で打ち切れば…

D. Fun with Integers 図示

Quiz https://codeforces.com/contest/1062/problem/D 観察 サンプル1より、a=2からスタートしたときはジャンプを繰り返して戻ってこれる。図示すると、 aとbが整数倍関係(0倍、1倍は不可。範囲内にあること)にあるとき、このループが作れる ループの途中…

6月-音楽祭 ~範囲和の最大値~

Quiz https://www.hackerrank.com/contests/tkcon/challenges/6- AC code https://www.hackerrank.com/contests/tkcon/challenges/6-/submissions/code/1320248583 公式解説 https://drive.google.com/drive/folders/1nCXiOd4K1GxJVRazWKUg5cojlJZFRIE5 感想…

D - 日本沈没 (Japan Sinks) JOI

Quiz https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d AC code https://atcoder.jp/contests/joi2019yo/submissions/9864231 補足 公式解説 https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t4-review.html これでなんとなく分かるのだが、実装…

JOI 古本屋(Books)

DP

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0561 AC code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4146908#1 要素 ソート 累積和 DP 解法 各ジャンルごとに高い順にソートしてよい そしてDP // ジャンル i までで // 合…

AOJ Paint Color ペンキの色

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531 AC code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4146310#1 座標圧縮(変換テーブルVER) // 座標圧縮 // 変換テーブルを返す VI make_compress_table(vector<ll>& A){ // </ll>…

D. Strange Device

Quiz https://codeforces.com/contest/1270/problem/D 解法 editorialや解説Blogの通り ただ、私の場合は文章よりも図で説明してもらう方が分かりやすいので、理解した後に描いた図をここに添えておく。誰かの理解の助けになれば幸いである プログラミングコ…

modintを導入 ~snuke's mint~ D. Santa's Bot

Quiz ちょうどいい問題があった D. Santa's Bot https://codeforces.com/contest/1279/problem/D AC https://codeforces.com/contest/1279/submission/69267347 modintの借り先 snukeさんのmint https://github.com/atcoder-live/library/blob/master/mint.c…

1269D - Domino for Young

https://codeforces.com/contest/1269/problem/D editorialではよく証明が分からなかった こちらを見てわかった https://tinumukiti631.hatenablog.com/entry/2019/12/23/175055 同じ高さの2列があったら消してよい ぷよぷよじゃないしなぁ?と思うかもしれ…

競プロでいう「DSU」って何?

Disjoint Set Unionの略。すなわちUnion Findのことである codeforcesでよく見かける。世界的にはDSUって呼ぶのかな? プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~作者:秋葉拓哉,…

D - Swap and Flip ~bit全探索解法~

Quiz https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d AC https://atcoder.jp/contests/keyence2020/submissions/9586830 解法 i番目が表か裏かをbit全探索 表裏を決めた時につじつまが合っているかチェック チェックを通ったなら、最終的なin…

F - Enclose All 参考リンクのみ cpp c++

Quiz https://atcoder.jp/contests/abc151/tasks/abc151_f 参考 https://codeforces.com/blog/entry/23554 最小包含円・最小包含球 内容 中心を平均などで適当に決め、一番遠い点の方に少し近づける調整を繰り返す 計算量 O(N x R) R : 繰り返し回数(求めら…

B - Fusing Slimes 泥臭いエスパー解法

Quiz https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b AC https://atcoder.jp/contests/dwacon6th-prelims/submissions/9431139 解法 N=5の場合の順列(4! = 24通り)を全て描いて観察する 隣り合う丸の間(上記画像のアーチ)の…

Problem D: Tunnel (立命館大学競技プログラミング合宿2019 Day2)

Quiz https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/D 問題意図のみ説明 貪欲に(柱の角に向かって引く)取ればいいんじゃないの?と思ったが違った 画像のように、柱の上辺を交差するように引くと合計が小さくなる 解法 DP htt…

立命館大学競技プログラミング合宿2019 問題と解説のリンク

立命館大学(理系−全学統一方式・学部個別配点方式、薬学方式) (2020年版大学入試シリーズ)作者:出版社/メーカー: 教学社発売日: 2019/05/25メディア: 単行本 Day 1 (立命館大学) https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day1 解説 http:…

セグメント木で使える演算子

目的 これってセグ木でできる?をまとめる 参考コードを探すときの高速化 モノイド 結合律 単位元 モノイドの例(随時追記) min max sum or https://atcoder.jp/contests/iroha2019-day1/submissions/5205846 タコヤキ https://atcoder.jp/contests/arc008/…

K - 巨大企業 / Conglomerate ~LCA~

Quiz https://atcoder.jp/contests/past201912-open/tasks/past201912_k AC https://atcoder.jp/contests/past201912-open/submissions/9277571 解法 LCA Code // LCA set VV G; const int N_MAX = 150010; const int MAX_LOG_V = 20; ll depth[N_MAX] = {};…

E - Handshake ~二分探索・累積和・格子点~

図 9 14 1 3 5 110 24 21 34 5 3 の場合の図 (サンプル2) Quiz https://atcoder.jp/contests/abc149/tasks/abc149_e AC https://atcoder.jp/contests/abc149/submissions/9230235 解説 editorialより複雑なことをしてしまった気がするが、解けたので共有 全…

編集距離 O(N^2) DP

Quiz https://yukicoder.me/problems/no/225 AC https://yukicoder.me/submissions/408789 解説 編集距離そのものの問題 int dp[1050][1050]; i : sのi文字目 j : tのj文字目 までを一致させるための最小コスト としてDPで解く。O(N2) Code // 編集距離 cons…

累積XOR, XORの性質

説明 累積XORとは、累積和と同じように事前計算しておくことで範囲のXORをO(1)で求める方法のこと XORの性質 a xor a = 0 a xor 0 = a 上記を利用すると、A = a xor b xor c xor d xor e の値を持っていて c xor d xor e の値が知りたいときは A xor a xor b…

2次元vectorのresizeに注意

Code VV A(5, VI(5)); // 10x10で確保したくなった A.resize(10, VI(10)); for(auto a : A){ debug(a); } exit(0); Result [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0…

桁DP

お得? 桁DPは「知らなきゃ解けないけど、知っていればやるだけ」らしい 習得しておきたい 問題「D - 禁止された数字」 https://atcoder.jp/contests/abc007/tasks/abc007_4 AC https://atcoder.jp/contests/abc007/submissions/8900569 解法 // keta // sma…

D - 道路の老朽化対策について ~サイズ付きUnion Find~

Quiz https://atcoder.jp/contests/abc040/tasks/abc040_d AC (verified) https://atcoder.jp/contests/abc040/submissions/8891107 解説 editorialの通りですが、ポイントとしては「橋の構築」と「クエリ」を同じvectorに入れてyearでソートした後、yearの…

No.845 最長の切符 ~最長距離・ダイクストラ・ベルマンフォード・bit DP~

Quiz No.845 最長の切符 - yukicoder https://yukicoder.me/problems/no/845 AC https://yukicoder.me/submissions/405827 解法 // i : また訪れてない頂点フラグ // j : 現在地 // とした場合の最長距離 int dp[1<<16][16]; としてbit DP 以下、(間違った考…