perogram

dfsで閉路検出 D - Subway

Quiz https://codeforces.com/contest/131/problem/D AC code https://codeforces.com/contest/131/submission/74636017 解法 閉路が1つだけあることが決まっているので、dfsして再訪した点があれば、それは閉路内の点 dfsしながら親を記録しておけば、閉路…

F - Knapsack for All Segments

Quiz https://atcoder.jp/contests/abc159/tasks/abc159_f 解説 私の解説ではないですが、良さそうな解説がTweetされていたのでたどり着ける人が増えるようにここに書いておく ABC159-F: Knapsack for All Segments の解説を書きました.DPの問題を,センス…

prefix palindrome

文字列のprefixのうち、最大の回文を求めたい この問題で必要だった https://codeforces.com/contest/1326/problem/D2 editorialを見てもよく分からず、tester codeを見てもよく分からなかった。コードはこれ https://pastebin.com/St9RUYvN const int M = (…

全方位木DPについてBlogを読むより先に見るべき動画

Educational DP Contest / DP まとめコンテスト (EDPC) : V - Subtree 解説動画 jupiroさんの動画 木DPは理解済みとする rerootingという言葉を使っていて、しっくりきた この動画でイメージを掴んだ後に https://atcoder.jp/contests/dp/tasks/dp_v を解い…

2次元imos (二次元いもす) ~yukicoder No.60 魔法少女~

Quiz https://yukicoder.me/problems/no/60 AC code https://yukicoder.me/submissions/443826 クラス化してみた struct Imos2D{ VV A; ll H,W; Imos2D(ll h, ll w){ H = h; W = w; A.resize(H, VI(W)); } // [(y0,x0), (y1,x1)] void add(ll y0, ll x0, ll …

No.41 貯金箱の溜息(EASY)~コインDP~

Quiz https://yukicoder.me/problems/no/41 AC code https://yukicoder.me/submissions/443691 DP表の定義 // i円玉まで使って // j円以下を作る方法 ll dp[10][100100]; j円「以下」というところがポイント DP表の図示 解法 M円を111111で割った値をM'とし…

隣接積の和の最小値をOEISに聞いてみる練習

Quiz https://yukicoder.me/problems/no/831 AC code https://yukicoder.me/submissions/442812 N=1~9までの答えを全探索で求め、その数列をOEISに与えて一般項を得る https://oeis.org/search?q=1%2C4%2C11%2C21%2C37%2C58%2C87%2C123%2C169&sort=&languag…

Range Mindex Query (最小値とindexのペアを返すセグメント木)

Quiz https://yukicoder.me/problems/no/875 AC code https://yukicoder.me/submissions/442780 補足 クエリに答えるときに、min値を持つ場所のindexを返す必要がある だから min + index = mindex というタイトルなのだろう 遅延なしSegTreeは書いたことが…

No.999 てん vs. ほむ

Quiz https://yukicoder.me/problems/no/999 公式解説 https://yukicoder.me/problems/no/999/editorial 私の解説 累積和を使わなかったので書いておく ほむちゃんが左から攻める領域と、右から攻める領域は2つは左右に分割されるので、切れ目を全探索。各切…

Zアルゴリズムを使って文字列sから文字列tを見つける

Quiz No.1005 BOT対策 https://yukicoder.me/problems/no/1005 AC code https://yukicoder.me/submissions/442411 説明 別解でO(N)で解ける方法としてZアルゴリズムが挙げられている 使ったことが1度だけあるが、再度使って練習してみた 文字列sから文字列t…

Magic Bullet ~3次元幾何ライブラリを借りて~

AOJ

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2641&lang=jp AC code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4239654#1 code抜粋 int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N,Q; cin>>N>>Q; // …

幾何・円の交点 (2次元)

Quiz https://atcoder.jp/contests/abc157/tasks/abc157_f AC code https://atcoder.jp/contests/abc157/submissions/10485169 交点コードはここにある 解法 snukeさんの解説放送を見て、snukeさんの幾何コードを貼る https://www.youtube.com/watch?v=TdR81…

Bananas Multiplier (Easy/Hard)

Quiz https://www.hackerrank.com/contests/yfkpo3-2/challenges/bananas-multiplier-easy https://www.hackerrank.com/contests/yfkpo3-2/challenges/bananas-multiplier-hard (hardも通る)解法 (0-indexedとする) 頂点0からの最短距離(辺の本数)を各頂点…

JOIOJI

JOI

Quiz https://atcoder.jp/contests/joisc2014/tasks/joisc2014_h 公式解説 https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d3-joioji-review.pdf 解説 サンプルの文字列に公式解説を適用するとこうなる JO[i]==JO[j] かつ JI[i]==JI[j] の組の中で…

A - JJOOII (JJOOII) ~文字列のランレングス(文字情報あり)~

Quiz https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho1 AC code https://atcoder.jp/contests/joi2012ho/submissions/10256473 解法 Oの連続数に注目する 例えばOOOがあったとき(連続したOが3個でその隣は違う文字)、レベル3しか作りえない レベル…

bfsのたたき台

bfsってやるだけなんだけど、これまで汎用化していなかった たたき台としてここに書いておく verified E - チーズ (Cheese) https://atcoder.jp/contests/joi2011yo/submissions/10254552 code ll d[1050][1050]; ll H,W,N; int dx[4] = {-1, 0, 1, 0}; int …

D - カード並べ

JOI

Quiz https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_d AC code https://atcoder.jp/contests/joi2010yo/submissions/10252516 解法 next_permutationで全ての並び方を考慮し、先頭k個を採用する 3200msかかりますが、10秒制限なので大丈夫 code抜…

D - 薄氷渡り

JOI

Quiz https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d AC code https://atcoder.jp/contests/joi2009yo/submissions/10251707 解法 dfsで経路を全探索 dfs内でdfsをさらに呼ぶ時、呼ぶ前に状態を変更して、読んで戻ってきた後に状態を戻すテクがあ…

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 公式解説(JOI) https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf これの「5」 要素 座標…