徒然

思いついたら書きます

アルゴリズム

マンカラのシミュレーターを作ってみた

はじめに QuizKnockの動画に触発され、鶴崎さんが作っていたWeb上で遊べるマンカラシミュレーターを自分も作ってみたという記事です。

可変長配列からランダムに要素を取り出したいときのTips

はじめに Pythonならlist、c++ならvectorのような可変長配列からランダムに要素を取り出したいときはどうすればよいでしょうか? ランダムに要素を選んで取り出したいところですが、可変長配列から要素を取り出す操作はかかってしまいます。 そんなときは、…

Mo's Algorithmのイメージを視覚的に理解したい

はじめに Mo's AlgorithmはABC242-GやABC293-Gで出題され、典型アルゴリズムとなりつつあります。 一度理解すれば納得しやすいアルゴリズムなのですが、初めて学習したときに巷の図では個人的に分かりにくかったのでブログ内で整理してみました。

Pythonで動くエラトステネスの篩をさらに高速化してみた話

はじめに 以前の記事でエラトステネスの篩を作成しました。 しかしこの篩ではLibrary CheckerのEnumerate PrimesでTLEしてしまいます。 そこで本記事では篩のさらなる改良を目指します。

Pythonで使えるnext_permutationを実装してみた

今まで配列列挙ではitertools.permutationsに任せきりだったのですが、仕組みを知りたかったので自作してみました。 辞書順で次の組み合わせが欲しいとか、重複なしの組み合わせを列挙したいとか*1、C++に慣れているのでnext_permutation準拠のコードを書き…

いもす法をpythonのclassで書いてみた

はじめに いもす法は割と競プロの中ではメジャーなアルゴリズムですが、毎回書くよりclassで書いたほうが楽じゃないのと思ったけど誰もpythonで書いてなさそうだったので自分で書いてみてみたってやつです。

NKODICEのOCHINCHIN確率問題を動的計画法で解く

はじめに ここ数日NKODICEというダイスゲームが流行っています。 store.steampowered.com これはチンチロリンのように日本語が書かれた6面体サイコロを振って美しい日本語を作るゲームですが、ダイスを振って出た目で「お」「ち」「ん」「ち」「ん」を作れる…

高速で正しく動くエラトステネスの篩をPythonで書く

はじめに 「エラトステネスの篩 python」で検索すると色々実装されたものが出てきますが、一番上に出てくるページのコードは遅い実装である上にコード自体が間違っているという始末です(どのページかは伏せますがmax=4にすると4が素数判定されるのが1つの反…

AtCoder practice contest B - Interactive SortingをPythonで解く

はじめに AtCoder practice contest B - Interactive SortingをPythonで解いた記事が見つからないので、簡単に解説してみます。