スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

AGC025 B - RGB Coloring を形式的冪級数で解く

AGC025 B - RGB Coloring を解いた後にこの問題を Twitter で検索してみたら「形式的冪級数を使うと考察をすっ飛ばせてすごい」という声が多数ヒットしたので、 形式的冪級数を使って改めて解いてみたところ本当に「やるだけ」の問題になってびっくりしたよ~~という記事。

問題

atcoder.jp

続きを読む

「良いぞ!便利だぞ!」リスト (青変記念)

苦節16ヵ月、やっと青になれました。いや~~学生の間に達成できてよかった。そして、いっぱいいいねもらえてうれしい(満たされる承認欲求)。

f:id:scol:20200914100428p:plain:w500
やったぜ!

青変記念に、僕が今まで競プロをしてきた中で「これ良いぞ!/ 便利だぞ!」と感じたものをジャンルを問わず超適当にリストアップした。

続きを読む

DPの配列使いまわしテクニックに関するメモ

この記事は swap を使った配列使いまわしテクニックのメモ。

インデックスの偶奇を使った配列使いまわしテクニックは蟻本の悪習だという話を聞いた。確かに、この方法ではコードの見た目は悪いし、「初期化 or 出力するのは偶奇のどっちの配列だろう?」とかを考える手間が生じる。 これを回避するために、偶奇で更新する配列を判断する代わりに、dp1 を古い配列、dp2 を新しい配列と決めて、配列を swap しながら DP する。

続きを読む