<< 前回 次回 >>（最終回のため、なし） はじめに この記事でやること マインスイーパーに関する諸定義 説明に使う用語 細かい設定 マインスイーパーのZDDによる解法 ZDDによる爆弾配置の表現 新たな隣接マスの追加 ヒント数字を適用する演算 爆弾総数を適用…
<< 前回 次回 >> はじめに この記事でやること 前回のおさらいと効率化アイディア 共有リスト その他の効率化ポイント マスの添え字を逆順に振る 左右反転解を省略する 実験結果 おわりに 参考文献 はじめに すっごく久しぶりの投稿です。本当はもっと早く投…
次回 >> はじめに この記事でやること ZDD(Zero-suppressed Binary Decision Diagram, ゼロサプレス型二分決定グラフ) ZDDとは？ どうやって表現するの？ ZDDのプログラム上での表現方法と実装準備 ZDDクラスのコンストラクタ Diagramクラスのコンストラクタ…
はじめに この記事でやること 注意点 （前半）マトロイドと貪欲法 マトロイドの定義 【定義 1.1.1】*2 マトロイドに関する用語 【定義 1.2.1】 【定義 1.2.2】 【定義 1.2.3】 【定義 1.2.4】 【命題 1.2.5】*3 マトロイドと貪欲法 【定義 1.3.1】 【定義 1.…
この記事でやること 全永続セグ木って？ 全永続セグ木の実装例 区間mexクエリの処理方法 オフラインの場合 オンラインの場合 実装例 終わりに 参考文献 この記事でやること 全永続セグ木のPython (PyPy3) による非再帰実装 区間mexクエリのオフライン処理方…
この記事でやること 彩色多項式とは 木の彩色多項式 彩色多項式の漸化式 単純連結グラフの彩色多項式 ACコード 参考文献 この記事でやること ABC294-Ex問題 にてグラフ彩色の通り数に関する問題が出題され、その際彩色多項式なるものを勉強したので備忘録と…
この記事でやること はじめに（茶番） 注意点 Dinic法の概要 概略 実装例 計算量評価 実用上の高速化ポイント BFSは頂点t に到達した時点で打ち切る 実は頂点s からDFSするより頂点t からDFSした方が速い（らしい？） 二部マッチングにおけるDinic法の計算量…
この記事でやること 注意事項 いもす法について 発想：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などでお馴染みの、「経路圧縮」のテクニックを利用して解いた問題を紹介。 経路圧縮とは 森のグラフで、ある頂点の根を知りたいとき、初めは愚直に親を辿っていき、帰りがけに各頂点の辺を直接その根に繋げなおすことでそれ以降の探索を高速化す…
