この記事でやること 注意事項 いもす法について 発想：2回累積和を取る 初項が0の場合 初項が一般の場合 ソースコード 例題 略解 この記事でやること 数列の区間に等差数列を加算するクエリを高速に処理する方法を解説します。 具体的には、数列 をで初期化…

この記事でやること 注意 0回戦敗退 A問題 B問題 C問題 D問題 E問題 F問題 G, Ex問題 感想 最後に この記事でやること Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder の参戦記（？）を書きます。多少は問題解説を…

はじめに 経歴 基本的にやるべきこと 体系的に学ぶこと その他私がやっていたこと 競プロゼミ 組合せ論ゼミ おわりに はじめに 私事ですが、先日行われた大和証券プログラミングコンテスト2022 Autumn（ABC277）にて念願の入青を達成しました！ 本記事では、…

この記事でやること 注意事項 モチベーション lowlinkの基本 前提：DFS木と後退辺・横断辺 DFS木 後退辺 横断辺 命題：グラフからDFS木を取ったとき、使われなかった辺は全て後退辺となる lowlinkでやること ordの定義 lowの定義 ordとlowの求め方 lowlinkの…

この記事でやること 実現方法の説明 イベントソートとは？ 平面走査による解法 平面走査のための前準備 ソースコード 余談：どうせなら区間演算も遅延セグ木なしでやりたい おわりに この記事でやること 0埋めで初期化された配列に対する以下のようなクエリ…

この記事でやること 前提知識：（最小）ヒープとは 発想 push(x), get_min(), get_max() erase(x) ソースコード この記事でやること Python3のheapqを使い、以下の操作ができるデータ構造を実装します： push(x): xを追加 erase(x): xを削除 get_min(): 最小…

2022/07/08に開催された ICPC 2022 国内予選に、大学の先輩2人とチーム【thorny castle 】を組んで参加しました。 icpc.iisf.or.jp そして、結果は4完で47位。 https://icpcsec.firebaseapp.com/standings/ 公式の発表はないので手計算での集計ですが、おそ…

注意事項 ACコードとして載せてある言語は、全てPyPy3(7.3.0)を使用しております。 有名アルゴリズムを用いる際は、他のサイトやブログへのリンクを貼らせて頂いておりますので、詳しい解説等が知りたい方はそちらを参照して頂ければと思います。 ABC257のリ…

Union-Findなどでお馴染みの、「経路圧縮」のテクニックを利用して解いた問題を紹介。 経路圧縮とは 森のグラフで、ある頂点の根を知りたいとき、初めは愚直に親を辿っていき、帰りがけに各頂点の辺を直接その根に繋げなおすことでそれ以降の探索を高速化す…