けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2018-02-01から1ヶ月間の記事一覧

CS Academy 061 F - Xor the Graph (超鮮やかなオイラー閉路!)

こうきさんに聞いて解いてみた。 木を最小個数のパスで被覆する問題はとりあえず2種類あって、辺の重複ありの場合は昨日のCSA 069 D. Cover the Treeで適切に葉同士で繋ぐ感じにする。辺の重複無しの場合は奇数次の点に適当に辺を張ってオイラー閉路作って切…

CS Academy 069 DIV2 E - The Wall

とにかく整理に苦労したけど、本番中に通せて嬉しかったん CSA 069 DIV2 E The Wall 図は N = 5 の場合である。 N 段の壁を作りたい。ただし、どのレンガも下にあるレンガが完成してからでないと積み上げられない。 N 段の積み上げる順番の総数はいくらか。1…

CS Academy 069 DIV2 D - Cover the Tree

本番はツリーDPな方向性に走って詰め切れなかった。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そう... CSA 069 DIV2 D Cover the Tree N 頂点からなるツリーが与えられる。 ツリーのすべての辺を最小本数のパスで覆え。そのようなパスの集…

CS Academy 069 DIV2 C - Build Correct Brackets (最短経路数も一緒に求める最短路!)

まさにこれだったん。 CSA 069 DIV2 C Build Correct Brackets ()()))(())() のようなカッコ列が与えられる。 最小回数flipして正しいカッコ列にせよ。 また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。 ・1 <= 文字列長 <= 2500 まさに最短路…

CS Academy 069 DIV2 B - Reverse Subarray

B なのに難しかったのん。 CSA 069 DIV2 B Reverse Subarray N 要素からなる数列が与えられる。 ここから連続する区間を reverse することで元の数列全体が単調非減少となるようにしたい。 そのような区間の選び方は何通りあるか? またそのような区間のうち…

yukicoder 649 ここでちょっとQK!

yukicoder 649 ここでちょっとQK! K は固定で与えられる。数の集合 S に対する以下の Q 個のクエリを処理してください。i 番目のクエリは以下のいずれかです。 タイプ 1: S に数 v[i] を追加する。 タイプ 2: S に含まれる数のうち K 番目に小さい数を答…

AtCoder ARC 008 D - タコヤキオイシクナール (試験管橙色)

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…

最短経路の個数も一緒に数え上げる最短経路アルゴリズム

ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp…

【ライブラリ】mod の値が大きいときの mod 演算

昨日の CSA 068 DIV2 E Sliding Product Sum で、まさかのときのために作っていたライブラリがドンピシャで役に立ちました!!! 「1000000007 で割った余りを答えよ」という問題は多いですが、「m が与えられて m で割った余りを答えよ」となると往々にして…

AtCoder Petrozavodsk Contest 001 E - Antennas on Tree (黄色, 900 点)

はじめに 昨年末 DEGwer さんの数え上げテクニック集 がとても勉強になる資料として話題になりました。その中の P. 9 の「4. 条件の言い換え」のところに、「必要条件を列挙したらそれが十分条件だった」がありました。 こないだの APC 001 E - Antennas…

スターリング数と、問題まとめ

この間分割数の記事についての記事を書いたときに続けてスターリング数も次回書くつもりですっかり忘れていたので書こうと思い立ちました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含…

hoge木

Qiita に移植しました 重みつき Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて