2021-06-11

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

アルゴリズム競技プログラミング

はじめに

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

2021-06-03

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

アルゴリズム

はじめに

ここ数日NKODICEというダイスゲームが流行っています。

store.steampowered.com

これはチンチロリンのように日本語が書かれた6面体サイコロを振って美しい日本語を作るゲームですが、ダイスを振って出た目で「お」「ち」「ん」「ち」「ん」を作れると役満のような扱いで特別な演出が発生します。

さてこのゲームで使われる $N$ 個のダイスを振ってOCHINCHINを出す確率はどれくらいでしょうか？
Twitterで確率を求めようとしていた先駆者がいたようです。

togetter.com

このTogetterの最後の方でPythonで総当りで見つけようとしているのを見かけましたが、競技プログラミングをしている自分にとってこれは動的計画法で効率的に解けそうだなという勘が働いたので解いてみました。

2021-05-14

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

競技プログラミングアルゴリズム

はじめに

「エラトステネスの篩 python」で検索すると色々実装されたものが出てきますが、一番上に出てくるページのコードは遅い実装である上にコード自体が間違っているという始末です(どのページかは伏せますがmax=4にすると4が素数判定されるのが1つの反例です)。
自分で早く動く(はずの)ものを実装してみたのでメモ代わりに残しておきます。

2021-01-25

嬉野流対策の端角棒銀研究

将棋

はじめに

嬉野流への対策には棒銀が有効とされており、特に以下の記事は必見です。

west-shogi.com

しかし先の記事で深堀りされていない変化で負けることも多いので、研究ついでに記事を書いてみました。

2020-05-02

scipy.optimize.bisectを使った二分法を競プロで使う

競技プログラミング

はじめに

今日のyukicoder contest 246で関数の二分法に関する問題が出ました。

競プロPython勢ではAtCoderのD - 高橋君ボール1号をニュートン法(scipy.optimize.newton)で解く方法が有名かとは思いますが、二分法でもscipyのモジュールで解けるようなので使ってみました。

2020-04-24

scipyでABC061 D Score Attackを解こうとして解けなかった話

競技プログラミング

はじめに

今までAtCoderをやってきて最短経路問題を避けてきたのですが、レート水色目前にしてようやく重い腰を上げFloyd-Warshall法やDijkstra法などを勉強しました。
その中で最短経路問題を解くのにscipyのライブラリを使えることを知りました。 note.nkmk.me https://juppy.hatenablog.com/entry/2019/06/04/scipy%E3%81%AEFloyd-Warshall%E3%81%A8Dijkstra%E3%81%AE%E3%81%99%E3%81%99%E3%82%81_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_1juppy.hatenablog.com kawap23.hatenablog.com じゃあ自分もやってみよー、せっかくだし負の辺があってジョンソン法が使われる問題でやってみよーと思って解いてみたのが今回の話です。