ブログ名

競技プログラミングやお歌のお話をする高菜です。

[工事中]いわゆる期待値 DP の考え方

$$ \newcommand \id { \mathrm { id }} \newcommand \src { \mathrm { src }} \newcommand \tar { \mathrm { tar }} \newcommand \pid { p _ { \id } } $$ 毎回同じ形で出るのになんか混乱するので纏めました。 ※ 「補遺 ~ 執筆後に思ったのですが」にある…

最高に使いやすい Manacher のアルゴリズムの実装方法

参考文献:文字列の頭良い感じの線形アルゴリズムたち2 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ 普通の Manacher のアルゴリズム 入力 $s$ の長さが $n$ のとき、普通の Mancher のアルゴリズムは、$A_i$ が $s$ の場所 $s_i$ を中心とし…

マージテクで、いわゆる auxiliary tree を構築する方法

参考問題: ABC340-G Leaf Color (鹿島建設プログラミングコンテスト2024) 参考文献: 指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木 | Kyopro Encyclopedia of Algorithms LCAをベースに構築するAuxiliary Treeのメモ - 日…

初めてのスタジオレコーディング体験記

まずはこれを再生しましょう! www.youtube.com 再生しましたね。ありがとうございます。では本日はここまでということで、ありがとうございました 以下あとがきになります。 あとがき 前提(私がライブ苦手なお話) 私はいわゆるちゃんとした歌枠をしたこと…

2023年振り返り&2024年の目標

例年通り、旧念の目標の達成状況を見て反省をし、また新年の過ごし方、目標を立てていきます。 とりあえず過去記事おいておきます。 2023: 2023年の目標と、旧年の振り返り - ブログ名 2021: 2021 年の目標について - ブログ名 2020: 2020 年の抱負 - ブログ…

2次元累積和の4つの形と8つの構築方法、4種類の長方形和クエリ、そして閃光のごとく現れた1人の天才こと私です。オススメ実装もあります!

どもども~~ こんにちは。ながたでございます。 先日の ABC 331 D - Tile Pattern を見て、執筆したくなりました。 この記事は、2次元累積和の亜種や実装方針などを網羅的に検討して回った結果、結局「コレ」でよいですよねという感じの記事になっておりま…

全ての AVL 木が赤黒木になるような彩色をもつこと

AVL 木を赤黒木になるように彩色する方法をご紹介します。

Hopcroft–Karp の Rust による短くて易しい実装

Hopcroft–Karp のアルゴリズムは、二部グラフ $G = (V (= L \cup R), E)$ の最大マッチングを $O (E \sqrt V)$ で計算します。(ただし、$E = \Omega(V)$ を仮定します。)詳しくは Wikipedia へどうぞです…! この記事の方法は行数でいうと全部で 40 行以下…

長方形に割られた漫画のコマの読む順序の定義

マンガ初心者の方に向けて、コマをどのような順序で読んでいけばよいのかをレクチャーしていく記事です。 こちらの問題を解いていきましょう! 図みたいな漫画のコマ割りを見て「読む順序として正しいものを答えなさい」って言われたら大体みんな正解すると…

2023年の目標と、旧年の振り返り

旧年の振り返り 目標とその達成 去年は、(人気がどうというよりも)お歌が「上手になりたい!」を圧倒的第一に掲げ、活動してきました。それに最も資する定量目標は何かと考えたところ、投稿頻度でしょうかになりました。 歌ってみた動画を1年間で 保守的目…

世田谷区脱出ゲームに1年以上掛かったお話(お引越し体験記)

こんにちは、ながたです。 私は長らく世田谷区に住んでいました。旧居には不満も様々ですが、3.9 万円のお家賃を考えるとあまりに良いお部屋でした。しかしそんなお子様な私もいつしか、高級マンションに住みたいお年頃となってくるわけです。というわけでこ…

年収 1000 万円未満のみなさまに贈る、よりよい人生を送るための道標、ないし戦略についてです。

個人的におすすめな戦略 年収 1000 万円がいただけるお仕事につくとよいです。

最高に魂を揺さぶるおすすめ歌動画 10 選

隠していたのですが私は YouTube が大好きでして、多いときには一日に 40 時間くらい動画を観ていたりします。 みなさま、お歌の動画などご覧になりますでしょうか。私は多いときには一日に 4 億時間くらい観させていただいております。そんな私の「最高に魂…

ベル数でお馴染みの指数型母関数の exp がどのような数え上げに対応しているのか、どのようなタイプの問題が解けるのかを解説していきます。

$$ \newcommand {\braced} [1] {\left \lbrace #1 \right \rbrace} \newcommand {\bracked} [1] {\left \lbrack #1 \right \rbrack} $$ 指数型母関数といえば、添字のシフトが微分になったり、二項係数で重み付けられたコンボリューションが積になったりなど…

Convex hull trick などの実装に応用のある、Rust の BTreeSet / BTreeMap 1本だけで、2通り以上の二分探索を実現する方法

イントロ Convex hull trick では直線の列を、傾きに関して単調増加になるように管理するのですが、二分探索の検索クエリは傾きだけでは足りません。次のように2種類の二分探索が欲しくなります。 傾きに関して二分探索 最小を達成する区間に関して二分探索…

[暫定]Rust の `Box` を使った易しい平衡二分木の実装

イントロ 平衡二分木は、いろんな意味で難しいです。アルゴリズム自体は(難しくはあるもののお)そこまで長大とまではならないのですが、細かい機能を整備していくとどんどんコードが長くなっていく印象です。 そこでこの記事では、「挿入・削除・併合・分…

歌ってみたの機運について

みなさま ABC 229 お疲れ様です。決意表明の流行する今日このごろです。 さて、実は私の趣味は競技プログラミングだけではありません。たとえば最近はお歌にお熱です。長らく一人で楽しんでいたのですが最近は、やはりみなさまにも聴いていただきたい!人気…

整数のまま行う偏角ソート(行列式のあれです。)の実装バリエーションの検討とご紹介です。

ねぼこさんのこちらの記事に触発され、私の方法もご紹介したい! という気持ちになりました。 nebocco.hatenablog.com この記事の初めの方は Rust でのコーディングを主眼においてご説明しておりますが、最後の方に C++ 向けのお話も追記させていただきまし…

`next_permutation` と同様に列挙できるもの一覧

1. 置換(permutation) 長さ $N$ の数列 $A$ の置換を列挙します。辞書順で $A$ より大きな最小の置換 $A$ があればそれを求め、なければ報告するアルゴリズムが作れればよいです。 C++ に std::next_permutation がありますね。言わずとしれた C++ ナニコ…

バタフライ演算で高速化できるものまとめ

TODO: バグっているし読みづらいので書き直す TODO: 問題例追加 Editorial - AtCoder Regular Contest 132 を集合、 を要素数 の全順序有限集合 、 を写像とします。 この が写像族 の合成 で表し、さらに各 が写像族 の直積(すなわち (for )が成り立つ)…

Convex min-plus convolution を実現するアルゴリズムの実行時間を比較するベンチマークを作りました。

GitHub のレポジトリの REDME.md にすべてが書いてあります。はてぶはそれの宣伝です。みなさまよろしければご協力くださるととても嬉しいです。 github.com 今後 range query などもっとポピュラーなあたりに手を出しても良いかもですね。いろいろなベンチ…

Windows を購入したは良いものの邪魔なので徹底的に隔離しました。

私はもともと Linux (Ubuntu 20.04 LTS) しか使っていませんでした。用途は 競技プログラミング ソフトウェア開発 ツイッター 動画鑑賞 です。事足りました。 しかし Windows も欲しくなりました。デュアルブートには HDD がたりなさそうなのもあり、PC を購…

Low-link と関節点・橋、そして 2-連結成分・2-辺連結成分分解について

案外この形でまとめている記事が見つからなかったのと、ライブラリの上手な作り方を思いついてしまいまったのとで、執筆意欲です。 他の既存記事 Low-link と関節点・橋、2-辺連結成分分解まではかなり記事があるのですが、 2-連結成分分解はなかなか見つか…

2021 年のお盆は『コンピュータ代数ハンドブック』を読んで少しだけ基礎に詳しくなりました。

休暇シーズンには書籍を開きがちことながたかなと申します。今年のお盆も豪華9連休ということで予てよりのこちらです。ででーん。 コンピュータ代数ハンドブック作者:J.フォン ツァ ガテン,J.ゲルハルト朝倉書店Amazon …… 私が購入する本だいたい購入後に a…

髪を切っていただきました。

今朝の私は髪が長かったです。そこで、美容院で髪を切っていただきました。すると髪が短くなりました。具体的には、胸にかかるくらいの長さだったのが肩にかからないくらいの長さになりました。すごいですね。伸びるのには数年かかるのですが、切るのには、…

procon-bundler を作り直しました。

予め用意したソースコード(ライブラリ)を使いたい! しかしソースコードを 1 ファイルにして提出いといけませんね…… そんな私の需要に答えたのがこちら、procon-bundler なのですが、この度ソースコードを全消しして書き直しましたのでお知らせいたします…

キーエンス プログラミング コンテスト 2019 F - Paper Cutting の公式解説とは異なる、クローズドフォーミュラによる解法

問題リンク atcoder.jp 解法 ( h + w ) ! / ( w + w - k ) ! 通りのカットが等確率で起こるとして、スコア X の期待値 E [ X ] を計算しましょう。これは実は Θ ( lg p ) (除算が律速)で解けます。 各 1 ≤ i ≤ k に対して、第 i 回のカットによるスコアを …

CADDi 2018 F - Square の 2 状態 DP による解法です。

問題へのリンク atcoder.jp 解法 5 重対角成分のみ考えればよいというところまで、公式解説と同じです。公式解説では(例示にすぎませんが)5 マス分の状態を管理するとよいとありましたが、私は 1 マス分で解けましたので共有させていただこうかとです。 ケ…

AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) B - Three Coins の想定解とは異なる解法

atcoder.jp 長さ n の 0 と 1 の列であって、000 -> 111 と 111 -> 000 を用いて 00000..... から作れるものを、実行可能解と呼び、1 の部分に対応する a _ i の合計をそのスコアと呼びます。まずは実行可能解の構造を見てみましょう。 実行可能解は次の 2 …

サイコロの目の最大値から理解する subset convolution

1 から 6 の目が均等に出るサイコロを 2 回振ったとき、最大値が 4 になる場合の数は 36 個中いくつでしょう。そうですね。7 通りです。どのように計算しましたでしょうか。4 × 4 - 3 × 3 と計算した方、おめでとうございます。高校入試典型完全理解の方です…