題名を見ればわかると思いますが、今回は技術系の話は皆無です。本当はこういうのはツイッターでつぶやきたいのですが、セトリをネタバレされると嫌な気持ちになる人もいるかもしれないなーと思うと呟けず。 でも感想を吐き出したいんですよね。なので（こっ…

完全に解けていたはずだったのですが、ライブラリがバグっていることに気づかずヒドイことに… 解法 結論から言えば、接尾辞木の上でよくあるゲームをしていると考えると解ける。 結局の所、問題文のゲームが何をしているかというと、 文字列の接尾辞木を用意…

前回 XMLのお勉強その１１ - XML Catalogs - 競プロ備忘録 読んでいく仕様書 原文：ISO/IEC 19757-2:2008 - Information technology — Document Schema Definition Language (DSDL) — Part 2: Regular-grammar-based validation — RELAX NG 和文：なし 今回…

前回 XMLのお勉強その１０ - xml:id Version 1.0 - 競プロ備忘録 読んでいく仕様書 原文：XML Catalogs (OASIS Standard V1.1, 7 October 2005) 和文：なし ちょっと寄り道で、XML Catalogsを見ていきます。何気に初めてのOASISの仕様書です。 なんか調べて…

前回 XMLのお勉強その９ - XML Path Language (XPath) Version 1.0 - 競プロ備忘録 読んでいく仕様書 原文：xml:id Version 1.0 和文：なし また前回から時間があきました。この間に木の実装を済ませ、XPathを実装していました。 XPathの実装を進めるうちに…

前回 XMLのお勉強その８ - XML Base - 競プロ備忘録 読んでいく仕様書 原文：XML Path Language (XPath) 和文：XMLパス言語 (XPath) 前回からかなり時間があきました。そして前回は「次回はC14Nを読んでいきます」みたいなことを言っていた気がしますが、先…

解けなきゃいけない問題でしたが、しょうもないバグと遅すぎるライブラリによってACを逃しました… 解法 引かれた弦で分割されたそれぞれの領域に属する円弧の上の点の集合について、集合の分割と、ある点がその集合に属するかが判定できれば良い。 単純な方…

前回 XMLのお勉強その７ - XML Information Set - 競プロ備忘録 読んでいく仕様書 原文：XML Base (Second Edition) 和文：XML Base （第 2 版）日本語訳 XML Base仕様については、W3C公式からリンクされた和文翻訳が見つからなかったので、ググって出てきた…

前回 XMLのお勉強その６ - SAX - 競プロ備忘録 読んでいく仕様書 原文：XML Information Set (Second Edition) 和文：XML情報セット (第2版) XML Infosetと言われることが多い仕様です。 本編 1. Introduction 「XML Information Set (Infoset)」とは何で、…

前回 XMLのお勉強その５ - Namespaces in XML 1.0 - 競プロ備忘録 読んでいく仕様書 SAX 仕様書と言っていますが、私の知る限りでは、SAXはW3CやOASISのような標準化団体が策定した仕様というわけではなく、上記のホームページが原典だと思います。 あんまり…

前回 XMLのお勉強その４ - XML 1.0 ③ - 競プロ備忘録 正規表現の実装にハマっていて、時間があきました。 読んでいく仕様書 今回はNamespaces in XML 1.0です。 原文：Namespaces in XML 1.0 (Third Edition) 和文：Namespaces in XML 1.0 (Third Edition) …

前回 XMLのお勉強その３ - XML 1.0 ② - 競プロ備忘録 前回はXML 1.0仕様書の３章まで読んだので、４章から読んでいきましょう。 本編 4 Physical Structures 「実体」「内容」「実体名」の定義です。 [Definition: An XML document may consist of one or ma…

前回 XMLのお勉強その２ - XML 1.0 - 競プロ備忘録 前回はXML 1.0仕様書の２章まで読んだので、３章から読んでいきましょう。 前回注記をつけておくべきだったかも知れませんが、仕様書の焼き増しになるだけなので、基本的に原文の引用は載せません。 ただ、…

前回 XMLのお勉強その１ - 前書きなど - 競プロ備忘録 読んでいく仕様書 題名がパッと見意味不明ですが、XML自体の仕様を読んでいきます。最新版は第五版になります。 原文：Extensible Markup Language (XML) 1.0 (Fifth Edition) 和文：Extensible Markup …

前置き 最近XMLに入れ込んでいます。もとはXMLそのものというよりExcelとかのOffice形式ファイルをRustでいじりたかったのですが、そのためにOOXMLに触れることとなり、気づいたらXMLに入れ込んでいました。 OOXMLを触ることを考えると、DOMでXMLを編集でき…

ただの備忘録です。 Javaは本当に門外漢も門外漢なので、書いてあることはアテにしないでください。普通にウソだらけだと思います。 背景 RustでDOM Level 2のメソッドを実装しました。 実装が合っている確認したかったので、DOM Test Suiteを拾ってきて、な…

前から気になっていたのですが、c2rustというC言語のコードをRustに変換するツールがあります。 https://crates.io/crates/c2rust C言語の資産は歴史の積み重ねもあってものすごく豊富だと思いますが、それをツール1つでRustに変換してくれたら夢が広がりま…

いつもどおりAtCoderの問題を解くために新規のクレートを立ち上げたら、Rust-Analyzerの補完が効かなくなっていました。エラーメッセージを見てみると、Rust 1.82が最低サポートバージョンになったとのこと。 Release Noteを見に行くと、確かに昨日(2025/3/3…

典型考察がハマって気持ちよかったです。 解法 簡単のため、すべての項は異なる値を持つとする。 まず、の値が増えるというのがどういうことか考えてみる。 これはからを昇順に並べ、ある項を隣接項と比較したとき、差がより大きかったときの値は大きくなる…

E問題で死ぬほど詰まって焦りましたが、こっちは割とスムーズに考察できました。 解法 E問題とほぼ同じ設定なので、鏡餅の個数を決め打って、先頭個を区間内のそれ以降の餅と貪欲にマッチングさせることで構築可能かの判定が可能であり、個数の上限で二分探…

どう見ても貪欲にしか見えないけど、どう貪欲にとってもWAする恐ろしい問題でした。 と思いきや、実は正当な解法も貪欲法を使うという。 解法 問題文の感じから、二分探索できそうだとアタリがつけられる。 二分探索ができるとすれば、判定問題は「組の鏡餅…

以前からスイッチが1台欲しいなあと思っており、新品・中古含めて検討していました。 何週間か探した結果、中古のCatalyst 3850-48P-Eが6万で売られているのを発見し、買いました。 選定の経緯 希望としては、 CLIで設定ができること PoEをサポートすること …

多倍長整数でサボろうとしたのですが、TLEするな〜と思って思いとどまりました。 解法 各数値について、の位に何回寄与するか考える。 桁目の数値について考えると、 桁目から開始して桁目で終わる数値に、の位として寄与 桁目から開始して桁目で終わる数値…

競プロでは、どんなに非効率なコードを書いたとしても、要求された時間内に正しい答えが出せれば正義です。 なので、基本的には速いコードを書くことにそこまでこだわる必要はないです。 とは言っても速いコードを求めることは無意味ではなく、犯罪解法で計…

大きなC言語のコードをRustに移植しようとしたのですが、流石にいきなりRustっぽいコードに書き換えるのは難しかったです。 なので、とりあえずRustっぽくないコード（ポインタ使いまくり、libcクレート依存など）でテストが動く状態を作ってから、徐々にRus…

ただの備忘録です。 本題 mkfifoというのを使うといいらしいです。 回答プログラムがanswer、ジャッジプログラムがjudgeとして $ mkfifo fifo $ cargo run --bin judge < fifo | cargo run --bin answer teeを使えばログにも落とせます。便利。 $ cargo run …

本番めっちゃ詰まって困りました。 解法 をソートしておくと、どの文字列も隣の文字列とのLCPの長さが最大になる。 をソートしたあとの列について、隣の文字列とのLCPの長さを順にメモした配列をとしておく。 問題で求められているのはすべての文字列の組み…

最近、Online Dynamic Connectivityとか言われているデータ構造を実装しようと奮闘しています。 これを実装するのにEuler Tour Treeというのが必要なのですが、結構面白かったので備忘録です。 ちなみに、以下のスライドを参考にしているというか、なぞって…

素数modで問題を解くためのアルゴリズムは色々有名なものがありますが、合成数modだとうまくいかないものも多いです。 このようなとき、素因数分解によって素数modの問題に分解することができれば、中国剰余定理を用いて元の問題の解を復元できることがあり…

3完しかできなくてひどい目に遭った… ふと思い返すと、ひどい目に遭ったときしかブログ書いてない気がする。 そんなことはどうでもよくて、Dは解けそうにないし面白い要素もないので、Eをずっと考えていた。 こっちは考えごたえがあってとても面白かったので…