競プロのTipsまとめ

Tips:群とか環とか体とか

とあるご縁で掛け算とか足し算のあたりの話を読む機会があり「そういえば定義なんだっけ...?」となり見返したものを整理した記事です。 しかし出来上がったのは、掛け算や足し算を定義する一歩手前の記事になってしまいました。なぜでしょう。 競プロでも、…

Tips:Σ[r=0...A] nCr を、n = 0, 1, ..., N で求める

元ネタはこちら。 atcoder.jp 写像12相からの包除原理とかいう、そこそこゴツめな知識を要求した後に、 をすべて求めることを要求されます。 実際には、 の場合の総和も求める必要がありますが、 の場合の は であるとすれば、総和は となるので割愛です。 …

Tips:k 種類の文字をそれぞれ最大 n1, n2, ..., nk 個使って並び替えてできる文字列の個数数え上げ

元ネタはこちらの問題です。 atcoder.jp 問題とにらめっこしていると、以下のように読み替えることができます。 種類の文字 が存在する。 このとき、以下の条件をすべて満たす文字列 の個数を数え上げよ。 ・ は空文字列ではない。 ・ は 以外の文字を含まな…

Tips:順列を引数にとり、返り値が自然数な関数の最大値・最小値を求める

元ネタはこちらです。 atcoder.jp ↑ のページにもありますが、こういった問題でも使えるテクニックとのこと。 E - Permutation E - Traveling Salesman among Aerial Cities さて、考えたい問題は以下のような問題です。 ある自然数 が存在し、 を並び替えた…

Tips:半分全列挙

典型問題はこちらです。 atcoder.jp ちょっとひねった問題はこちら。 atcoder.jp 半分全列挙が使える問題は(完全に個人的な感想ですが)どんな問題なのか、わかりづらくないですか? 私だけでしょうか。 すこーし考えてみたので本ブログにメモっておきます…

Tips:comparator を使用した Python でのソート

競技プログラミングの Tips 記事です。 Python でリストをソートする際、もっともシンプルな書き方ですと以下のように書くことになるかと思います。 l.sort() sorted(l) 上が破壊的なソート、下が非破壊的なソートですね。 ソートされる順番を制御したい場合…

Tips:Binary Indexed Tree で転倒数

今回は、競技プログラミングに関する記事です。 Binary Indexed Tree(以降:BIT)をつかってこんなこともできちゃうぞ、という趣旨の記事です。 BIT 自体に関する記事はこちらからどうぞ。 katoufujibanana.hatenadiary.jp 記事のタイトルの通り、BIT を使…

Tips:素数の個数

今回は、競技プログラミング Tips 系記事、素数の個数についてです。 素数やら約数やらが出てくるような問題の場合、回答の計算量が、 以下の素数の個数、みたいになることがあります。たとえば、過去に紹介した素因数分解のアルゴリズムには、計算量に 以下…

Tips:数列和の解析式

今回は数学的なお話をします。数学的といっても、中学数学か高校数学の範疇のはずです。指導要領が私のころと変わってるはずなんで、今の子たちはいつ頃やるんでしょうかね? ここら辺の範囲。 きっかけとしては、数え上げ系の問題や、「先頭から数えて K 番…

Tips:隣接リストと隣接行列

今回は小ネタ的な記事です。 グラフを表現するデータ構造には、隣接リストと(Adjacency list)と隣接行列の(Adjacency matrix)の二つがあります。 それぞれデータの中身としてはこんな感じになります。 # 隣接リスト graph = [ [1, 2, 3, 4], [0], [0, 3]…