徒然

思いついたら書きます

Rustで競プロするときの書き方メモ

競技プログラミング Rust

最近勉強のため（とヒューリスティクスコンテストのため）にRustで競プロしているのですが、これどう書けばいいんだっけ？となったときのための自分用メモを残しておきます。 内容は雑多に書いてます。

続きを読む

情報処理技術者試験の開示請求をしてみた話

資格

はじめに

令和5年度春期の情報処理技術者試験が終わってやることがなくなったタイミングで、以前の試験の答案の開示請求をしてみようと思い立ちました。
しかしIPAの個人情報に関する開示請求ページを見てもよくわからなくて一度挫折した経験がありました。
そんなとき以下の記事を見つけ開示請求の流れを理解できたので、自分も開示請求してみました。

wktk.jp

続きを読む

「確率 mod 998244353」とか「期待値 mod 998244353」って何なの？という話

競技プログラミング

はじめに

分数のmodって何？AtCoderの注釈を読んでも意味わからないんだけど？といった方向けの記事です。
なおこの記事上は法(998244353や1000000007など)が素数であることを前提とします。

続きを読む

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

アルゴリズム

はじめに

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

そんなときは、末尾の取り出しがO(1)なことを利用して、末尾と要素を入れ替えてから取り出すと高速になります。

続きを読む

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

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

はじめに

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

続きを読む

AtCoder Beginner Contest 292 F - Regular Triangle Inside a Rectangle 解説

競技プログラミング

はじめに

ABC292のF問題で幾何問題が出ました。
自分は他の方と解答アプローチが異なったので解説記事を書いてみます。

続きを読む

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

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

はじめに

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

続きを読む

AtCoder青色になりました

競技プログラミング

トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)にて、AtCoder開始以来ずっと目標にしていた青コーダーになりました！
初参加から3年少々かかりました。

atcoder.jp

続きを読む

AtCoder上でscikit-learnを使って機械学習してみたい

競技プログラミング

はじめに

皆さんはAtCoderでscikit-learnが使えるのをご存知でしょうか？
現在*1のAtCoderでは以下のライブラリが利用できます。
numba, numpy, scipy, scikit-learn, networkx
今回はせっかくなのでscikit-learnを利用して問題を解いてみました。

*1:2022年8月現在

続きを読む

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

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

今まで配列列挙ではitertools.permutationsに任せきりだったのですが、仕組みを知りたかったので自作してみました。

辞書順で次の組み合わせが欲しいとか、重複なしの組み合わせを列挙したいとか*1、C++に慣れているのでnext_permutation準拠のコードを書きたいとかいったときにお使いください。

記事の後ろにprev_permutationもあります。

*1:more-itertools.distinct_permutationsがAtCoderで使えれば良いけど2022/1現在は使えない2023/8の言語アップデートから入りました！

続きを読む