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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

小売店で発注ミスをしてしまった方の気持ちが、今ならばわかります。 どーん！ 50 食のボンカレー あの！？！？ だって数量 10 って書いて 10 袋届くなんて思わないじゃないですかぁああ！！！ あの！？！？ （ここ大暴れカット） ……ぜぇ、ぜぇ。ひとしきり…

3 月の成果 問題埋めは基本的に 600 点に注力しましたが、3 問だけ解けなくて残ってしまいました。残ったのはこちらの 3 問です。ちょっと辛くなってきましたので、来月は読書とゆる 700 点でしょうか。（700 もさくっと通せるのはなくなってきてしまいまし…

第一章 ドキュメンタリー 時は 16:30、急激に襲う吐き気。 これはなんですか？ 午前中は万全の状態だったのですが、アッまた俺なにか食べちゃいました？笑 ともあれ動くのもやっとな状態、体調には大きな波があるよでしたから、動ける瞬間を見計らって call …

私はキャベツです。美味しいキャベツがいかに培養され、出荷するのかをキャベツ視点でお送りしたいと思います。 きっかけ 「純粋培養競技プログラマが就職して１年」みたいなブログがよみたい。どんなことを身に着けて何が出来るようになったかみたいな。— c…

2 月の成果 AtCoder Scores 1 月と 2 月の比較です。400 点、500 点を埋め終わりました。 2021-01 600点以下 2021-02 600 点以下 こういう図のほうがわかりやすいですかね。1300 まで入りますし。 2021-02 1300 点以下 コンテスト参加 AtCoder のコンテスト…

1 月について ngtkana.hatenablog.com 進捗報告 600 点以下埋め これ中心でやるつもりだったのですが、結局序盤に 300 以下埋めてご無沙汰でした。 600点以下 700 点以上埋め 700 点をいくつか埋めました。 700点以上 他 700 点を埋めでDISCO presents ディ…

なんだか振り返りがアツすぎて（やったことを振り返る系）色変記事のようになってしまいました…… あれこれ取り組んでみて、結局ダメだったバージョンの記事がこちらです。思い返すと本当にいろいろ試して、躓いて、様々なことを成し遂げたもののレーティング…

要約 お盆休みに蟻本を完走（記事へのリンク）して、とてもためになったのを踏まえ、長期休暇にはなんらかテーマを決めて取り組んで見ることにいたしました。 この冬休みは『アルゴリズムイントロダクション』の 第 V 部（高度なデータ構造） 第 VI 部（グラ…