Tips:数列和の解析式

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

素数系アルゴリズム:エラトステネスの篩

今回は、素数に関するアルゴリズムのうちの基礎中の基礎、エラトステネスの篩です。 唐突ですが、ある自然数 に対し、 が素数であるか否かの判定は で計算することができます。 以下証明です。 が素数でない場合、つまり が 以外の自然数 で割り切れる場合、…

グラフ探索アルゴリズム:深さ優先探索の帰りがけ deque 実装版

以前の記事で、deque を使った深さ優先探索と幅優先探索の python スクリプトや、再帰関数をつかった深さ優先探索の行きがけと帰りがけの python スクリプトをご紹介しました。 deque による深さ優先探索は、前回の記事では行きがけの実装のみの記載となって…

ゲーム理論:パレート最適

今回はゲーム理論の記事です。 戦略型ゲームにおけるパレート最適の定義についてです。 ある戦略型ゲーム において、 について かつ が成り立つとき、 は をパレート支配するといいます。 また、ある について、 に対し、 または が成り立つ場合、 はパレー…

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

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

ゲーム理論:戦略型ゲーム

今回もゲーム理論の記事です。 前回のナッシュ均衡に関する記事や、将来書くかもしれない別のゲーム理論に関する記事において、分析対象となる戦略型ゲームとは何かを記述するのがこの記事です。 戦略型ゲームとは、 自然数 集合のリスト 関数のリスト それ…

ゲーム理論:ナッシュ均衡

今回はゲーム理論の話です。 過去に公開した(まだまだ作成途中の)こちらの記事についてなのですが、 katoufujibanana.hatenadiary.jp 記事の冒頭でナッシュ均衡に触れているものの、その説明を与えないまま話が進んでいってしまっていたので「じゃあ、そも…

DP:フィボナッチ数、階乗、組み合わせ数

タイトルには DP と付けましたが、どちらかというと計算のメモ化の色が強いです。 今回は、あると便利なフィボナッチ数、階乗、組み合わせ数の計算スクリプトをご用意したので記事にいたします。 コンテストに参加していると、ふとした瞬間に「階乗を計算す…

グラフ系アルゴリズム:Union-Find 木

先日書いた記事の katoufujibanana.hatenadiary.jp にて、グラフ上のある2点が接続しているかどうかの判定アルゴリズムとして、Union-Find の名前を出しましたが、どのようなアルゴリズムだったかは触れなかったので今回は Union-Find を取り上げます。 ま…

グラフ+bitDP:巡回セールスマン問題

今回は巡回セールスマン問題(Traveling Salesman Problem: TSP)のコードを書きます。グラフ上のすべてのノードをめぐる最小距離を求める問題です。どちらかというとグラフの探索アルゴリズムというよりかは、DP 的側面の強いアルゴリズムという印象。 素朴…

ゲーム理論:フォーク定理

今日はゲーム理論に関する記事を書きます。表題の通りフォーク定理(folk theorem)に関する記事です。1回の記事だと紙面が足りなくなるので何回かに分ける予定です。 戦略形ゲームにおいてすべてのプレイヤーが戦略を(自分一人だけ)変えるインセンティブ…

AtCoder Beginner Contest 201

Mynavi Programming Contest 2021(AtCoder Beginner Contest 201) - AtCoder たびたび参加はしていましたが、リアタイ更新は約一年ぶり。 結果:4AC(1WA) 1020 位。 問題 A ソートして条件満たすかどうか見て Yes か No 吐いて終わり。 問題 B ソートし…

グラフ探索アルゴリズム:深さ優先探索の行きがけと帰りがけ

グラフを探索するアルゴリズム、深さ優先探索。英語でいうと Depth-first Search (DFS)。深さ優先探索にはタイトルの通り、行きがけと帰りがけのバリエーションがあります。 前回の記事では Python の deque クラスを使用した、深さ優先探索と幅優先探索の実…

グラフ探索アルゴリズム:深さ優先探索と幅優先探索

グラフを探索するアルゴリズム、深さ優先探索と幅優先探索。 英語でいうと Depth-first Search (DFS)、Breadth-first Search (BFS)。 競技プログラミング頻出のアルゴリズム(基礎レベル?)ですが、知らないと自力でひらめくのは難しいはず。いわゆる”知識”…

1x Engineer

何かの折で見かけたこちらのページなのですが、探してみると和訳がなかったので和訳することにしました。 一見、平凡なエンジニアであることの自虐であるかのように見えますが、実態は、本文中でも言及されている 10x Engineer に対するアンチテーゼ、そして…

Node.js, JavaScript 系アプリの雛型コードを公開しました

GitHub - katoufuji-banana/my-application-templates お品書きは以下の3本立て。 サーバーサイド ほぼほぼすっぴん Node.js アプリ(Babel 付き) Express Web サーバー クライアントサイド React.js よければ、皆さんの開発の何かにお役立てください。 で…

スクラムガイド バックナンバー

過去のスクラムガイドへのリンクが公式のダウンロードページから消えていたので、サルベージしてきました。 スクラムガイド 2020年 英語版 スクラムガイド 2020年 日本語版 スクラムガイド 2017年 英語版 スクラムガイド 2017年 日本語版 スクラムガイド 201…

AtCoder Beginner Contest 162

AtCoder Beginner Contest 160 - AtCoder 結果:4AC(1WA) 3240 位。みなさん解くの早すぎません? 問題 A, B 特にいうことなし。 問題 C いざ書いてみたら計算量なのに、ずっと頭の中でだと勘違いし続けて、時間を消費。 問題D 第一条件を満たすパターンか…

AtCoder Beginner Contest 160

AtCoder Beginner Contest 160 - AtCoder 結果:5AC(1WA) ほげーーー。グラフわからん。 問題A 言ってることそのまま式に。 うっかり添え字を1引き忘れてて提出するところだった... 問題B 500円玉の枚数を最大化。 問題C 一番間隔が広い家のペアを求めて、…

AtCoder Beginner Contest 159

AtCoder Beginner Contest 159 - AtCoder 結果:5AC(4WA) 落としたのは問題E。なんだかなぁ。もう少し時間があれば行けそうな気がしたんですが。 後の祭り、粛々と解説読んで「あー」っていう仕事をしましょう。 問題A を正しく計算できますか問題。 これ…

パナソニックプログラミングコンテスト2020

Panasonic Programming Contest 2020 - AtCoder これ、実質 ABC なのでは?? 結果:4AC(3WA) 問題Bゆるすまじ 問題A リストにぽい。 問題B とが両方奇数の場合とそうじゃない場合で場合わけすりゃ一発でしょ~ => WA ( 'ω')? ( 'ω') ( 'ω')???????????? …

日立製作所 社会システム事業部 プログラミングコンテスト2020

Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 - AtCoder 三度目の企業主催コンテスト。 結果:2AC(1WA) 配点から見て、「AとBは解けて、あとどれくらい解けるかが勝負かなー。Cが解けるといいなぁ」と思いつつ…

AtCoder Beginner Contest 158

AtCoder Beginner Contest 158 - AtCoder 結果:4AC(2WA) あまり芳しくない。残念。 問題A, B, C は、あまり特筆することもないかなぁって。 問題D は、解説にある通り計算量を押さえる工夫が必要。 工夫せず提出して、一回 LTE を踏んで、1WA。 問題E 最…

AtCoder Beginner Contest 156

AtCoder Beginner Contest 156 - AtCoder 勝ち申した。 6AC 達成しました!! 問題A 逆算できるかな問題。 問題B 高校のときセンターの勉強でやったなぁと思いつつ、記憶にある解法通り実装すると、底が2でないときに誤差が発生することが発覚。 「高々桁を…

AtCoder Beginner Contest 155

AtCoder Beginner Contest 155 - AtCoder 久々の参加からの解答確認即ブログ更新。 今回難しかったですね。結果3AC でヒヤッとした。 問題A 33-4 -> AC。雑に Python の Set に投げて、長さなら OK~って。 問題B アルストツカに栄光あれ! -> 「ならば」は…

AtCoder 経過報告

AtCoder Beginner Contest 152 - AtCoder AtCoder Beginner Contest 153 - AtCoder 実は参加してました。 (152 が 5AC で 153 が 4AC) そんなことより ABC 153 までやった現在での Rating の遍歴がこちら。 目標は水色なのですが、このままやっていると、…

キーエンス プログラミング コンテスト 2020

Keyence Programming Contest 2020 - AtCoder 宣言通り、キーエンスさん主催のコンテスト参加してきました。 ↓ 結果:2AC ドワンゴのときもでしたが、企業主催のやつ戦績悪いな? 解いてる最中の感想(簡略版) 問題A:雑に割ればえんちゃう? → AC*1 問題B…

AtCoder Beginner Contest 151

AtCoder Beginner Contest 151 - AtCoder ではでは予告通り、ABC 151にチャレンジ。 問題A, B, C, D, E 素直な気持ちで実装して、5 AC(D で 2WA、E で 1WA)。 問題F あれ、実数の世界に入っちゃった...。 これはわからん。 問題F(解説をみる) あ~~なる…

第6回 ドワンゴからの挑戦状 予選

Dwango Programming Contest 6th - AtCoder ニコ動のドワンゴさんも問題つくってるんだなぁ、っていいながらチャレンジ。 ↓ 結果:惨敗。問題 A のみ AC。 解説を見よう コンテスト中、自分が思いついたアルゴリズムの計算量と、解説の計算量を比較してみま…

AtCoder Beginner Contest 150

AtCoder Beginner Contest 150 - AtCoder 会社でお昼ご飯食べてたらスマホが鳴ったので、何かと思ってみてみたら ABC 150 の告知が。まじか。よっしゃいくぞー! 問題50X ほう。 おお、エラーページ。 トップページもダメ。 AtCoder くん、かわいそう... 数…