atcoder.jp 問題はこちら。 はじめに問題文を読んだとき、「平衡二分木か…？」とも思いましたが、競プロ界隈有名事実の「ヒープキューを２つ使えば、削除も対応可」を思い出しことなきを得ました。（一日置いて考え直してみると、座圧して Fenwick Tree ２本…

問題の元ネタはこちら。 ABC の F 問題で、約数系包除原理の問題が出るような時代になったみたいです。 atcoder.jp 約数系包除原理で検索すると、見つかる有名どころの解説記事はここらへんでしょうか。本記事ではあまり包除原理自体の説明には踏み込まない…

震源地はこちら。 [問] 下記のネストすごろくをクリアできる確率はいくらでしょうか？ネストすごろく：ゲームが始まると、下記のように START のマスにいる状態になります。サイコロを振り、出た目の数だけ右に進みます。GOAL に達するとクリアです。(GOAL …

素数に関する定理で、面白いものを見つけたのでメモ。 自然数 について、素数全体の集合を と置くとき、 表題の定理の場合は が素数 となっています。 が素数でないときの、 で割った余りがいくつになるかも、ひと手間加えれば示せるので、先のような書き方…

atcoder.jp ご参加された皆々様、お疲れさまでした。 得点：121,539,661 点 順位：184位（1447人中） でした。ヒューリスティックで青パフォは初だったのでうれしい。 解法はこちらです。 いわゆる貪欲 + モンテカルロ系解法（のはず）です。 atcoder.jp 一…

元ネタその１ atcoder.jp 元ネタその２ en.wikipedia.org 早速ですが python スクリプトをドン。 def eulerian_number(n, m, MOD=998244353): ans = 0 sign = 1 comb = 1 for i in range(m+1): ans += sign * comb * pow((m + 1 - i), n, MOD) ans %= MOD si…

問題はこちら atcoder.jp で、AC コードはこちら atcoder.jp 第一引数が float の場合の python の pow 関数の計算量について詳しくないのですが、もし int の場合と同じであれば計算量 の解答となります。 やっていることは、公式解説をもとに、簡単なさん…

問題はこちら atcoder.jp タイトルの通り、公式解説の「[1]条件の言い換え」の流れを仔細に追ってみようという記事です。そういう意味では、話題としては軽めかも。 示したい内容は以下の２つの条件が同値であることです。 言い換え前の条件がこちら。 は以…

問題はこちら atcoder.jp 今回の記事は、ARC146 の C 問題について。ちびちびとした話を詰め合わせる形で。 まずは問題文に関する話題から。 Twitter で「問題文の意味取り違えていた...」みたいな反応がちらほら。私も間違えて最初は の方の個数数えてまし…

問題はこちら。 atcoder.jp 私もコンテスト中は「普通の」二分探索だと思い、普通の二分探索を書いて、運よく回答を通すことができましたが、実は探索範囲の指定を間違えると WA になってしまうことが分かったので、その解説記事になります。 比較のためこち…

話題とする問題はこちら。 知らなかったので、細かいところの実装コストが膨れて解けなかったので備忘のため。 atcoder.jp 本記事の主張内容はおおむね解説にある通りなので、当記事はお手軽に使える python スクリプトがあるよ、ということでお願いします。…

話題とする問題はこちら。 atcoder.jp ゲームってことは xor？と思いきや、不偏ゲームは両プレイヤーの操作が同じ場合の話なので、今回のようなケースだと解けません。 もしかしたら適切にアドホックな改修を加えれば解けるのかもしれませんが。 カテゴリ的…

問題はこちら。 atcoder.jp 概要としてはこんな感じ。 以上 以下の自然数を、 のマス目に1つずつ書く。 行 列の値を と表すとき、すべての が以下を満たすような書き込み方が何通りあるか答えよ。 または 制約は です。 大きい数になるので、 で割ったものを…

今回は競技プログラミングに関する記事です。 以前 Prim Jarnik 法に関する記事を公開したのですが、間違えた内容であることが分かったので内容を修正した記事となります。その節はご迷惑をおかけしました。 もうひとつの最小全域木生成アルゴリズムである K…

AGC057 に Unrated 参加してきました。AB 2完（1 WA）で順位は195位とのこと。 B 問題を解いているうちに「あれ、計算量どうやって減らすんだ...？」と十数分悩んだのち、解けたときすごい感動しちゃったので記事残しておきます。 解説ではしれっと２行くら…

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

競プロのアルゴリズムです。 契機としてはこちら。 atcoder.jp 定理本体の説明や、数学的証明はこちら参照。 manabitimes.jp algo-logic.info ざっくりいうと、 を前計算 、クエリ で計算することができるアルゴリズムです。ただし は素数。 素朴に実装する…

掲題の通り。 ここ気になるな―という点のメモです。 正しい用語回しできていなかったら恐縮です。フィーリングで読んでくれ。 家計消費の効用関数 消費額 に対する効用 について、 を置くの、結構強い仮定を置いているような気がする。 それどころか具体的な…

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

練習問題としてはこことか、こことか。 atcoder.jp atcoder.jp 一般に桁 DP でぐぐると、「桁を一個一個みていく DP だよ！」みたいな記事を見かけがちですが、冒頭の問題のように「 以下の」といった条件がある場合、文面通り桁だけ見ていくと条件を満たし…

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

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

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

ゲーム理論です。ポエムです。 表題の通り、ゼロサムゲームにおけるパレート最適解が何かについての記事です。たぶん簡単な内容なので、広く一般に知れ渡っているような気もしますものの。 パレート最適解については、過去に記事を書いているのでそちらもご…

ゲーム理論です。ポエムです。 今回の記事は、以下二つの記事の合いの子のような記事です。 ゲーム理論：戦略集合が拡大することによるナッシュ均衡解への影響 - katoufujiBanana’s blog ゲーム理論：「～かつパレート最適解となる解は存在するか？」系記事…

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

今日はゲーム理論の記事です。ほぼほぼポエムです。まじめに記号や定義入れると大変なので。 突然なのですが、素朴な心情といたしまして、 「人々の選択肢が増えることで、より一人ひとりにあった選択をすることができるので、選択肢の増加が起きたときは、…

Promise Promise - JavaScript | MDN Promise.prototype.then() - JavaScript | MDN Promise.prototype.catch() - JavaScript | MDN Promise.prototype.finally() - JavaScript | MDN async/await 非同期関数 - JavaScript | MDN await - JavaScript | MDN f…

ポエムです。 仕事上、いろいろな入力パターン試してスクリーンショットをとる、プロジェクトによっては Excel に貼り付けて管理するなどの、多くのエンジニアの心身を蝕む業務があるのですが、この不幸からエンジニアを守るためにはどうすればよいかなとい…

走り書きのゲーム理論です。 むかーし、こちらの記事 ゲーム理論：繰り返し戦略型ゲーム - katoufujiBanana’s blog で言及した、混合戦略を繰り返し戦略型ゲームに拡張する方法についてこの記事で述べます。ちゃんとした定義にはならぬのですけれども。ご容…