私の活動の報告です。
レポート Euclidean MST (Library Checker) correct.cpp の解説
背景
競プロでは、ユークリッド距離最小全域木の計算方法として、 Fortune のアルゴリズムでドロネー図(Delaunay diagram)を構築し、ドロネー図の最小全域木を計算するという方法がよくとられています。一方で、 Lib...
レポート Double-Ended Palindromic Trees 解説
Library Checker への提案を踏まえ、 で提案された Double-Ended Palindromic Trees の原理をさらい、これを実際のプログラムとして実装する過程を解説します。
arXiv preprint...
レポート 転置原理まとめ
競プロやってても使わないテクニック
転置原理とは
転置原理(Tellegen's Principal)は、アルゴリズムの変形方法です。主に多項式関連の問題で利用され、応用例は現在 (2024年) も拡大しています。
...
レポート 区間代入/区間積 O(logN)/query で償却計算量にしないアルゴリズム
changelog
2024-02-23 問題文中の積の説明を改善。実行時間測定用の例題の具体的な問題を説明。
概要
こういうものがあります。
:
その記事によると、計算量を償却することで空間 ...
レポート 第34回高専プロコン競技 大阪公立大高専 #procon34
トーナメント 32→16 で敗退しました。残念。
ビジュアライザのデザインの紹介
比較的明るくないマスが池を表します。
白い星印が城を表します。
城壁は、マス内側に四角の枠を描画して表現します。
$...
レポート paizaレーティング 2700 台という意味不明な環境
paizaレーティングとは
paiza のスキルチェック問題に取り組んだ結果から計算される数値です。計算のための理論がある程度公開されています。 paizaレーティングの仕様はすべてこの文献の内容を参考にします。ただし、グリ...
レポート IOI2022 参加を振り返る記
JOI春2023 でいきなり思い出して書くやつ（あまり体裁まで気にすることができなかった）
インドネシア！
海外初めて
移動
飛行機は片道 7 時間かかり、できることが限られるので、その往復の時間で↓の解法を丁寧に...
レポート 競プロAdC やってるみたいなので Library Checker の解法紹介をぶっこむ
競プロ Advent Calendar 2022 の 1 日目担当の Nachia です。よろしくお願いします。
時間で変化する状態については、 2022/11/10 以降に取得した情報で書きます。
ライブラリ作り（盆栽）って...
レポート 高専プロコン2022競技部門・理論値解法
1回戦からエキシビションまでで参加した全問題で理論値（ $\stackrel{\text{def}}{=}$ 最も良い値）の得点を出して勝ち進んだので、「理論値解法」として紹介します。実装（特に並列化）が丁寧ではないので確かではないですが...
レポート Nachia が #procon32 に向けてやったこと
第32回高専プロコン競技部門の実施に感謝と敬意。ありがとうございました。それはそうとして、競技部門が企業賞を頂けなかったのがかなり悲しかった。
※この記事の日付は git の記録をもとに思い出しています。実際の開発と数日分ずれている...