AtCoder Beginner Contest 258 の E 問題。循環するリストの累積和のテクニック

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

AtCoder Regular Contest 143 の C 問題の解説の行間を埋める

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

AtCoder Regular Contest 143 の B 問題で出会った面白い等式

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

最小全域木:Prim Jarnik 法

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

AtCoder Grand Contest 057 の B 問題の考察

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

Tips:群とか環とか体とか

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

組み合わせ:Lucas の定理

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

お勉強:マクロ経済の入門本読んで思ったこと

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

スキル棚卸し:2021年度 冬

前回の記事はこちら。 katoufujibanana.hatenadiary.jp この記事は、定期的に「今、自分が(システム開発で)どんなことができるかなー」というのを整理するための、完全に自分のための記事です。赤文字のところが今回の追加分、青文字のところが前回の記事…

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

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

DP:桁 DP

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

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

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

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

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

Tips:半分全列挙

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

ゲーム理論:ゼロサムゲームにおけるパレート最適解

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

ゲーム理論:繰り返し戦略型ゲームで変化するナッシュ均衡解は、変化前と比べて「よい」ものであるか?

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

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

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

ゲーム理論:戦略集合が拡大することによるナッシュ均衡解への影響

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

JavaScript の非同期処理あたり

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 で言及した、混合戦略を繰り返し戦略型ゲームに拡張する方法についてこの記事で述べます。ちゃんとした定義にはならぬのですけれども。ご容…

ゲーム理論:展開型ゲーム

ゲーム理論の走り書きです。 一般的な展開型ゲームの定義の記事です。が、走り書きなので厳密な定義ではないです。 定義のノリは ゲーム理論:繰り返し戦略型ゲーム - katoufujiBanana’s blog で定義した、繰り返し戦略型ゲームのそれに似ています。あっちで…

ゲーム理論:記憶力に限界があるプレイヤーたちによる有限回繰り返し戦略型ゲーム

ゲーム理論です。走り書きです。 繰り返し戦略型ゲームの定義において、 回目の戦略を選択するに際し、 回目までの全プレイヤーの戦略の選択履歴を引数にしましたが、これを直前1回だけにするとか、直前数回にするとかといったバリエーションが存在します。…

ゲーム理論:「~かつパレート最適解となる解は存在するか?」系記事で紹介した戦略に関して、どのようなパレート最適解が選択されるか?

今回はゲーム理論に関する記事です。 今回も厳密に書く余力がないため、走り書きです。 表題の通り、 ゲーム理論:有限回繰り返し戦略型ゲームにおいてナッシュ均衡解かつパレート最適解となる解は存在するか? - katoufujiBanana’s blog ゲーム理論:有限回…

ゲーム理論:「~かつパレート最適解となる解は存在するか?」系記事に関する但し書き

今回はゲーム理論に関する記事です。 ただ、内容を整理しきれていないため、厳密に記号などを使わない形で書かせてください。そのうち整理して清書したものを、なんらかの媒体で出せればなと思っています。 ゲーム理論:有限回繰り返し戦略型ゲームにおいて…

Python 系アプリの雛型コードを追加しました(Flask, Gunicorn を使用した WebAPI サーバー。node.js 系テンプレートに dotenv を追加)

以前こちらの記事で更新した雛型コード置き場のリポジトリに、Python の WebAPI サーバー用テンプレートを追加しました。 katoufujibanana.hatenadiary.jp Flask 製です。Production 環境で使う際は gunicorn を使用して起動してください。詳しくは README.m…

最小全域木:Prim Jarnik 法(2022/05/28 追記あり)

(2022/05/28 追記) 当記事は内容に誤りがあります。 修正版の記事を公開したのでそちらをご参照ください。 なお、記事中紹介している Python スクリプト自体は正しい Prim Jarnik 法のものとなっております。もしスクリプトをコピーされてしまっている場合で…

最小全域木:Kruskal 法

今日は競技プログラミングに関する記事です。 最小全域木という、なかなか聞きなれない単語ですが、「ある無向グラフがあって、その辺の一部だけを選んで残して木にしたもののうち、もっとも辺のコストの総和が小さいもの」のことを指します。 ひどい実装を…

グラフ系アルゴリズム:01BFS

今回は競技プログラミングに関する記事です。 以前、グラフのノード間の最短距離を求めるアルゴリズムとしてこちらの3つをご紹介いたしました。 グラフ系アルゴリズム:ダイクストラ法 - katoufujiBanana’s blog グラフ系アルゴリズム:ベルマン・フォード…

DP:ダブリング

今回は競技プログラミングに関する記事です。 初めてみたとき、アルゴリズム名から何をやってるのかよくわからなかったアルゴリズム、ダブリングのご紹介です。 ある関数 が定義されており、 の値はいくらか、というのを計算する際に効力を発揮するアルゴリ…