レポート

私の活動の報告です。

レポート

Euclidean MST (Library Checker) correct.cpp の解説

背景 競プロでは、ユークリッド距離最小全域木の計算方法として、 Fortune のアルゴリズムでドロネー図(Delaunay diagram)を構築し、ドロネー図の最小全域木を計算するという方法がよくとられていま...
レポート

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 の記録をもとに思い出しています。実際の開発と数日分ずれている...
タイトルとURLをコピーしました