テーマ解説記事
AtCoder を攻略していく上で、 に慣れることは大きな課題です。特に、有理数 は、初見では何を言っているか分からないと感じる方も多いかもしれないですね。下図は ABC 323 E - Playlist の補足を表示したものです1。 本記事では、有理数 を徹底解説します!…
競プロにおいて、「Project Selection」や「2 変数劣モジュラ関数の和の最小化」などと呼ばれるテクニックがあります。いずれも、最小カット問題に帰着して解くことができます。これらは次のような関係にあります。なお、俗に「燃やす埋める」と呼ばれている…
Cartesian Tree を実装しよう! 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、そ…
多くの競プロerにとって、標準ライブラリ以外で自分の手で初めて実装するデータ構造は Union-Find でしょう。 自分でデータ構造を実装するとき、その中身がどうなっているかをきちんと把握できないと不安を感じてしまうこともあるでしょう。そこで本記事では…
Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…
結論 先に結論から。 リテラル に対して、以下の条件 A, B, C は同値である。 A: のうち、True であるのは 1 個以下である B:任意の () に対して、節 を充足する C:新たなリテラル の値を適切に定めたとき、以下をすべて充足する 1:節 () 2:節 () 3:節…
競プロの上達のためには、解けなかった問題の復習がとても大切になって来ます。 しかし、そんなことは分かっていても「解説を読んで分からないことが多々ある」ことが大きな壁になっていると感じる方も多くいると思います。とくに、数式が多いと難しく感じら…
ミラー・ラビンの素数判定法は、その背景にある整数論的考察もめっちゃ面白いので、ぜひそれも味わいましょう!! 1. はじめに 本記事では正の整数 が与えられたときに、 が素数であるか否かを判定する問題を考えます。 よく知られた方法は、 を で順に試し…
私たちは、グラフアルゴリズムとして DFS や BFS を学ぶと 頂点 s から頂点 t へ辿り着けるかどうかを判定する 連結成分の個数を求める 二部グラフ判定する トポロジカルソートする などといった例題を次々とこなしていき、グラフ探索スキルを高めていく道を…
競技プログラミングで時々問われる「座標圧縮」について簡単に解説します。 1. 座標圧縮とは 数列 が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていく作業を、競プロ界では座標圧縮 (座圧) とよびます。 たとえば A = (8, 100…
ARC 106 F に関連して、頂点次数制約のついた全域木の個数を求める問題がまさにあったので、その解説を。 問題へのリンク editorial 問題概要 (New Year Contest 2015 E - ひも) 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものが…
時は 2020 年 5 月 3 日。 ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています!!! AtCoder ABC 165 C - Many Requirements (昨日のやつ) AtCoder ABC 114 C - 755 AtCoder ABC 119 C - Synthetic Kadomatsu A…
めちゃめちゃ簡単な実装で良いことがわかったので。 なんか、DFS 2 回か、全方位やるかなのかと思ってたけど、とても簡単な木DPで直径が求められることを知った。 問題へのリンク 問題概要 頂点の重み付き木が与えられるので、その直径の長さを求めよ。 制約…
円と多角形の共通部分の面積を求めるライブラリ、一念発起して整備した!!! サブルーチンとして「円と "線分" の交点を求める」というライブラリが必要となる。 問題へのリンク 問題概要 原点を中心とした半径 の円と、 頂点の多角形が与えられる。これら…
0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見て…
きっかけは、タピオカ流競プロ優勝ガール、マリーさんのツイートでした。 100個ぐらいある整数から自由に選んでK円になる組み合わせを探せ!複数通りある場合は列挙!みたいな仕事がだるすぎてdpで列挙してくれるやつ作った競プロは事務員を救う— マリー (@C…
0. はじめに ビット演算については、以下の記事で特集しました。 qiita.com しかし、この中で、bit 全探索に関する説明がだいぶ簡潔すぎたので、ちゃんと書きたいなと思って、この記事書きます!!!ただし、ビット演算に関する知識は前提としているので、そ…
0. はじめに プログラミングコンテストにおいて、連立一次方程式を解くことに帰着できる問題は数多く出題されています。 連立一次方程式は Gauss Jordan の掃き出し法によって解くことができるのですが、「その解の個数を求めよ」などと言われたときに詰まり…
ふと TL に出してみた。絶対既出だと思ったから流したけど、どこかにあるかな...??? アイディア自体は SRM 309 DIV1 Hard StoneGameStrategist POJ 1704 Georgia and Bob (蟻本の例題) と同じものだったりする。むしろ問題に対してある種の同型変換を施す…
K 以下の整数を分類する 今日の ABC D 問題 で話題になったので書いてみます。競プロで 非負整数 が の範囲を動くときの、〜〜〜の最大値を求めよ 非負整数 が の範囲を動くときの、〜〜〜という条件を満たすものは何通りあるか という形をした問題は非常に…
なんか登場頻度高い割にいつも混乱するので...ちょっとちゃんと整理したいなと。。。 なんかこうすべきというのがあったらちゃんと勉強したい。 r = 0 のとき の倍数のうち、 以上となる最小の値を求めたい。 これはいわゆる「 を で割って、あまりを切り上…
1. 典型的な二項係数の求め方 競プロをしていると、「 mod 」を計算する場面にしばしば出くわします。最近では、 であることが多いですね。 mod の計算方法は、時と場合によって色んな方法が考えられますが、すぐ下で紹介する方法が最も頻繁に使用されていま…
ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp…
この間分割数の記事についての記事を書いたときに続けてスターリング数も次回書くつもりですっかり忘れていたので書こうと思い立ちました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含…
こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、…
この記事は、Competitive Programming Advent Calendar Div2013の22日目の記事として書きました。今年は「ナイーブにやるとO(2^n)になりそうな問題の計算量を落とす系の問題」を集めました。例えば、区間スケジューリング問題は、ナイーブに全探索しようと思…
僕は、最小全域木を求めるKruskal法をココロから納得するのにとても長い時間が掛かってしまいました。本記事では、備忘録的な目的を兼ねて、少しKruskal法について書いてみたいと思います。 僕は、Kruskal法は今年5月頃初めて知ったのですが、そのときはどう…
この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何…