GitHub - liyin2015/python-coding-interview: A middle-to-high level open source algorithm book designed with coding interview at heart!You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
ABC113-D 「Number of Amidakuji」 発展解法 - Mister雑記
この記事は以下に移植されました。 tiramister.net
ABC113-D:Number of Amidakuji - 思考の墓場
フィボナッチ数列が登場しがち。 問題 D - Number of Amidakuji 解法 こういうのはdpが有効である。を位置まででに行くようなあみだくじの数とおく。の遷移先はのいずれかである。あとはそれぞれの遷移先について，そこに遷移するような位置での横線の置き方の数がわかればよく，これはbit全探索することででできる。本番でここが思いつかなかった。悲しいね。 ところで，次のような事実がある。 縦棒が本のあみだくじのある位置での横線の置き方の数は，フィボナッチ数列の第項をとすると，に等しい。フィボナッチ数列とは，で定義される数列である。 証明 に関する帰納法で示す。左から順に縦棒にと番号をつけることにしよう。のときはそれぞれ通りである。での成立を仮定して，のときの横棒の置き方の数を求めよう。縦棒と縦棒の間に横棒を置かないとき，横棒の置き方はからまでの横棒の置き方に等しく，通りある。縦棒
【PDF】包除原理 解ける数え上げの範囲を広げよう
tsutaj (@_TTJR_) Hokkaido University M1 October 16, 2018 tsutaj (Hokkaido Univ.) October 16, 2018 1 / 78 1 2 ϕ Uncommon Ball and Boxes 3 lahub and Permutations 3 LCM Rush Enumeration 4 (2) Rotated Palindromes Everything on It 5 tsutaj (Hokkaido Univ.) October 16, 2018 2 / 78 ▶ 積集合 (intersection) 和集合 (union) tsutaj (Hokkaido Univ.) October 16, 2018 3 / 78 ▶ ▶ ▶ (intersection) ▶ (union) 1 積集合 (inter
UnionFindTree に関する知見の諸々 - noshi91のメモ
2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか？ 競プロでは恐らく最も使用頻度の高いデータ構造だと思います*1。この記事ではプログラミングコンテストで役に立つものから全く役に立たないものまで、UnionFindTree に関するいくつかの知見を書き留めておきます。記事の最後に各内容の実装例を貼っておきます。 計算量と実装のバリエーション UnionFindTree の操作辺りの計算量が O(α(N)) であることは良く知られていますが*2、この計算量を達成するアルゴリズムはいくつかのバリエーションがあります。併合時に木の高さと大きさのどちらを指標にするかという
競技プログラミングで青になるまでにやったこと - hogecoder
リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。 自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒業できるように頑張っているところです。なので「青色になったので書いている」わけではないのですが、青を目指している人々にとって参考になる記事になっていれば幸いです。 水色 → 青 これは Twitter などでもよく言われていることなのですが、 AtCoder の ABC / ARC の D がコンスタントに通せる ようになると青が見えてくると感じています。問題セットにもよるので一概には言えませんが、 C 問題は呼吸、 D 問題は最低でも 20 分以内には片付けたいところです。なので、コンスタントに通すにはどのよう
NUPSC招待講演：アルゴリズムで広がる世界
「金融予測アルゴリズムを評価するときに、あまり一般的ではないけども自分としては皆に気にかけてほしいこと」を伝えたいと思い MarketTech Meetup #01 (https://alpaca.connpass.com/event/108066/) で話したときのスライドです
A - Uncommon/みんプロ2018本戦 - D言語で競プロ
問題概要 集合が与えられる。 各整数k = 1, 2, ..., Mについて、kと互いに素であるAの要素の個数を求めよ。 制約 解法 愚直にやると少なくともO(N*M)かかってしまうのでまとめて数え上げるなどの高速化が必要になります。 kを固定したときに、kとa_iが互いに素であるというのは、gcd(k, a_i) = 1であるというのが定義ですがこの条件はまとめて数え上げようとするときには少し使いにくいので別の同値な条件に言い換えてみます。 という感じにkを素因数分解したとします。(p_jは素数) このとき、kとa_iが互いに素であることの必要十分条件は、a_iがどのp_jでも割りきれないこととなります。逆に、kとa_iが互いに素でないことは、a_iがあるp_jで割り切れることと同値です。 この事実を使ってkと互いに素でないa_iの個数を求めることにします。その個数をn(k)とします。
Graph Golf参加記
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。 前提知識として知っておいてほしい単語は以下の2つくらいです。 グラフ(点と点が繋がってるアレのこと) 次数(頂点に繋がってる辺の本数のこと) 問題内容 自
典型データ構造まとめ - beet's soil
なんか前回伸びたので 参考 hamayanhamayan.hatenablog.jp ei1333's page 宣伝 beet-aizu.hatenablog.com 以下とりあえず辞書順（そのうち典型度順にしたい） Binary Indexed Tree 一点加算、先頭からの区間和、k番目に大きい値が で可能 library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub 容易に多次元に拡張が可能（実用上は2次元くらい？ library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub Binary Trie 二進数を管理するTrie木 全体にXOR、k番目に大きい値、lower_bound等が で可能 library/binarytri
競技プログラミングは役に立たない : プログラマ・プログラミングまとめ
>>7 いや就職はあるだろ glassdoor/careercup見ればわかる、アルゴリズム問題ばっかやぞ
確率DPを極めよう - 確率と期待値の問題解説
DP tsutaj (@_TTJR_) Hokkaido University B4 February 20, 2018 tsutaj (Hokkaido Univ.) DP February 20, 2018 1 / 54 1 2 ( ) ( ) HSI 3 4 RareItems (Hard) 5 tsutaj (Hokkaido Univ.) DP February 20, 2018 2 / 54 (Dynamic Programming) tsutaj (Hokkaido Univ.) DP February 20, 2018 3 / 54 DP DP DP tsutaj (Hokkaido Univ.) DP February 20, 2018 4 / 54 A P(A) = A : 6 1 5 P(x ≥ 5) = 1+1 6 = 1 3 A P(Ā) = 1 − P(A)
競プロにおけるNim、Grundy数とNimK - かっさのなにか
この記事は、 「競プロ!!」 競技プログラミング Advent Calendar 2017 21日目 の記事です。 昨日は DEGwer さんの「数え上げテクニック集」でした。まだ全部読んでないけど凄かったです。 こっちでも同時に競プロのアドベントカレンダーが進められています。 Nim,grundy数がわかっていると、盤面を共有して二人で対戦し、勝敗が必ず決するタイプのゲーム問題がわりとサクッと解けます。 最近では 5日前、2017/12/16 の Atcoder Regular Contest 087 E で Grundy数の問題が出ました。 この記事の本題はNimの拡張されたゲーム、NimKの話です。 導入として、Nimとかgrundy数を知らないひとにもわかるようにスライドを作成しました。 絵を描くだけのつもりだったのにスライドになってしまいました。 適当すぎてわからん！と思うひとも
Grundy数 その2 - へなちょここーだー
前回はGrundy数とは何かを説明しました。Grundy数に関する基本的な求め方は前の記事をご覧ください。augusuto04.hatenablog.com ただ、これだけではあまり多くの問題に使えないのでもう少し発展的な使い方を紹介します。 Nim 私は知りませんでしたが、有名なゲームらしいですね。ルールは次の通り。 n個のコインの山があります。プレーヤーは１つの山を選んで、その山から1枚以上のコインを取り除きます。これを2人で交互に行い、取り除くコインがなかったらその時点で負けになります。 ここで、上のような場合を(4, 2, 1)と今回は表します。 とりあえず各山についてGrundy数を求める まずは、各山についてGrundy数を求めます。 もし、0枚の山があるとするとここからは遷移できないのでGrundy数は0。 1枚の山からは0枚の山に遷移できるのでこれ以外で最小は1。 2枚の山
Grundy数 その１ - へなちょここーだー
Grundy numberについての勉強をしたので、そのまとめ（自分用のメモでもある）。ちなみにNimberとも言うみたいですね。実際にいくつかのゲームを考えながら説明をしていきます。最後の結論まで少し長いです。 そもそもGrundy数ってなんだろう 具体例は後で出すとして、とりあえずGrundy数の求め方から紹介します。 ある状態におけるGrundy数はそこから遷移できる状態におけるGrundy数以外の最小の0以上の整数。 えーと・・・。これだけでは良く分かりませんね（笑）。じゃあ実際にあるゲームを考えてみます。 30を言ったら負けゲーム 以前、伊東家の食卓というテレビ番組で紹介されたゲームです。ルールは次の通り。 先手と後手が交互に1つ以上3つ以下の整数を1から順に30まで言っていく。 先手は1から初め、30を言った人が負け。例えば、先手:1, 2, 3 後手:4 先手:5, 6 後手
Grundy number - ペケンペイのブログ
Grundy number (Nimber) について説明する。 Nimber - Wikipedia Sprague–Grundy theorem - Wikipedia Grundy number はゲームにおいて先手・後手必勝の判定に使われる。Grundy number は「現在の状態から遷移できる状態達の Grundy number の中に存在しない最小の自然数」として再帰的に定義される。形式的に定義するならば、ゲームの状態全体 $S$ に対して Grundy number は関数 $g\colon S \to \mathbb{N}$ であり以下で定義されるものである。 \begin{align} g(x) = \mathrm{mex}\{g(x') \mid x' \in N(x) \} \end{align} ここで $N(x)$ は $x$ から遷移できる状態全体の集合であり
nCr mod mの求め方 - uwicoder
これはCompetitive Programming Advent Calendar Div2012に投稿された記事のようです。 今年ははてなではなくatwiki(こちら)のほうでやります。はてなはTeXが汚かったりソースコードの折りたたみができない等色々アレなので・・。 さて、今回は数え上げ・数学ゲーの常連、Combinationの剰余の計算について書きます。正確にはBinomial Coefficient(2項係数)ですね。ここでは1秒以下で求められることを目安に制約をつけてそれぞれについて解説します。 TeX的に楽な式で書きたいとおもいます。 0o_ ※一応Javaコードを添えてはいますが、完全なものとは限らないので、全部欲しい場合は関数名から察するか@uwitenpenにmentionください。 mがsqaurefree(4以上の平方数で割り切れない)のとき mを素因数分解して素数
競プロに強くなりたい人におすすめの本 : Grenache's blog
競プロに強くなりたい方、蟻本以外のいいもの見つけました。 すでに強い方は当然知っているようなことでしょうが、なかなか初心者から抜け出せない私にとってはいいなと思った本です。 「数え上げの問題」に強くなる 「マスター・オブ・場合の数」をおすすめします。 「数え上げの問題」って、なかなかいい参考書がないと思っていました。数え上げ問題に出会うたびに、解説を読んで勉強しますが、なかなか解けるようになりません。知識としていろいろ知っておかなければいけないというよりは、テクニックやノウハウ的な部分が大きいからなのかと思います。しかし、それらにも典型というのはあって、それを知っているのと知らないのでは大きく違うようです。 この本は、典型的な問題がカテゴリ別に整理してあり、解法が詳しく記載されています。また、ちゃんと問題を解くと、同じ系統の問題を何度も練習することになり、いい訓練になりました。解法が1つだ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
互いに素である a,b の組を効率良く列挙しよう
サンタコンペで二度全完した話
