@elphe.bsky.social
自称競プロer/大学生 AtCoderにて水色コーダーとして活動中(https://atcoder.jp/users/elphe) アルゴリズム・データ構造が中心の独り言ばっかりになりそう
最近、僕に熱心に電話をかけてくれる人がいるみたいだけど、基本的に僕は
・寝ている
・大学の講義室で授業を受けている
・大学の図書館にいる
・バス／電車の中にいる
・食事／入浴している
・AtCoderコンテストに参加している
のいずれかだから、ほとんど電話には出られないよ！
用事や連絡があるならDMやメールなどの非同期コミュニケーションだったら基本的に対応するよ！
今日大学休みなのに大学に来てしまった……
14.11.2025 00:53 — 👍 1 🔁 0 💬 0 📌 0
atcoder.jp/contests/abc...
解決した
rを強制的にn以下に留めてたせいで「これより右ならどこをとってもいい」の処理がうまくできてなかったのが原因だった
これでもなかった
えぇ…？
気づいた
めちゃくちゃ尺取り法の大事なところで間違えてるやんけ！
見つけたと思った間違い、別に考慮してなくても影響はゼロだから関係ないわ……
じゃあどこが間違ってるんだ？
簡単な尺取り法もまともに書けなくてやや悲しい（間違いは既に多分見つけた）
atcoder.jp/contests/abc...
Rustでセグ木、ようやく書けた！
実装方法はac-library-rsをパｋ、参考にした
struct SegmentTree<T, const DEFAULT: T, const OP: Fn(T, T) -> T>とは定義できないから、このジェネリック引数たちをトレイトに押し込んで、使うときにこのトレイトを実装した構造体を定義するようにすればよかったんだな
試運転も良好！
atcoder.jp/contests/pra...
Rustでセグメント木を書こうとしたら、コンパイルエラーに阻まれて書きたいように書けない……
Rust難しくないですか
( -`ω-)✧ﾌｯﾌｰﾝ（他人のライブラリの使い方を読解する能力がないから自分で作ってるなんて言えない……）
09.11.2025 10:21 — 👍 1 🔁 0 💬 1 📌 0![mod mylib {
pub struct UnionFind {
root_of: Vec<u32>,
size_of: Vec<u32>,
groups: u32,
}
impl UnionFind {
pub fn new(size: u32) -> UnionFind {
UnionFind {
root_of: (0..size).collect::<Vec<u32>>(),
size_of: vec![1; size as usize],
groups: size,
}
}
fn search_true_root_of(&mut self, index: u32) -> u32 {
if self.root_of[index as usize] != index {
self.root_of[index as usize] =
self.search_true_root_of(self.root_of[index as usize]);
}
self.root_of[index as usize]
}
pub fn is_connected_between(&mut self, a: u32, b: u32) -> bool {
self.search_true_root_of(a) == self.search_true_root_of(b)
}
pub fn merge(&mut self, a: u32, b: u32) -> bool {
if self.is_connected_between(a, b) {
false
} else {
let (root_of_a, root_of_b) = (self.root_of[a as usize], self.root_of[b as usize]);
self.size_of[root_of_a as usize] += self.size_of[root_of_b as usize];
self.root_of[root_of_b as usize] = self.root_of[root_of_a as usize];
self.groups -= 1;
true
}
}
#[allow(unused)]
pub fn size_of_group_with(&mut self, index: u32) -> u32 {
let root_of_index = self.search_true_root_of(index);
self.size_of[root_of_index as usize]
}
#[allow(unused)]
pub fn count_groups(&self) -> u32 {
self.groups
}
}
}](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:nf36rsxrgldog5vr2f6nffoq/bafkreiadilwvpk2w5piouiwigocmpplkied7um353ebioc33ee42xp2mxy@jpeg)
mod mylib { pub struct UnionFind { root_of: Vec<u32>, size_of: Vec<u32>, groups: u32, } impl UnionFind { pub fn new(size: u32) -> UnionFind { UnionFind { root_of: (0..size).collect::<Vec<u32>>(), size_of: vec![1; size as usize], groups: size, } } fn search_true_root_of(&mut self, index: u32) -> u32 { if self.root_of[index as usize] != index { self.root_of[index as usize] = self.search_true_root_of(self.root_of[index as usize]); } self.root_of[index as usize] } pub fn is_connected_between(&mut self, a: u32, b: u32) -> bool { self.search_true_root_of(a) == self.search_true_root_of(b) } pub fn merge(&mut self, a: u32, b: u32) -> bool { if self.is_connected_between(a, b) { false } else { let (root_of_a, root_of_b) = (self.root_of[a as usize], self.root_of[b as usize]); self.size_of[root_of_a as usize] += self.size_of[root_of_b as usize]; self.root_of[root_of_b as usize] = self.root_of[root_of_a as usize]; self.groups -= 1; true } } #[allow(unused)] pub fn size_of_group_with(&mut self, index: u32) -> u32 { let root_of_index = self.search_true_root_of(index); self.size_of[root_of_index as usize] } #[allow(unused)] pub fn count_groups(&self) -> u32 { self.groups } } }
とりあえずRustで自作のUnionFindを書いてみた
（英語力がないので関数名が…）
ABC431おわりっ！18分11秒でABCD問題をノーペナ4完！
A問題はmax(H,B)-Bが答え
B問題はフラグの配列をもっておいて、加算か減算か決める
C問題はそれぞれをソートして、軽い方の頭から対応する体を決める
対応する体は、極力軽い体を選ぶ貪欲法でOK
D問題はナップサックDP
つまるところ、全体の重さの半分以下を頭部に持ってこれるので、全体の重さの半分をナップサック耐久度としてナップサックDPを行えばよい
E問題はなぜか合わない
マス(i,j)から方向dに光が出たときの答えを01BFSで順次求めていけば良さそうになったけど、サンプルが通らない
F問題まったくわからん
atcoder.jp/contests/abc...
（Rustでは）人生初AC！！！！
さっきたまたまAtCoderのコンパイルコマンド確認しに行ったら、C++のコンパイルコマンドがとんでもないことになっててびっくりした
大半はインクルード指定のオプションだったけど、よく見るとfconstexpr系のオプションに渡される値が大幅削減されてた（元々の値がデカすぎた）
この図、大変よくないと思う
誰でも累積和とるってこんなん
四条駅からの所要時間表
四条駅から松ヶ崎駅まで2+4+6+8+10+12+14=56分！？市営地下鉄にしては長すぎやろ！！
（実際は四条駅から松ヶ崎駅までで14分）
Stringと&strの区別がある時点でなかなかヤバいですよね……
あと、この記事では触れられてませんが、Rustの文字列型は添字アクセスできないというのも衝撃でした
C++もpythonも添字アクセスできたのに……
とりあえず「The Rust Programming Language 日本語版」を5日で1～16章まで読破したけど、かなり苦しいぞ……
特に後半になるほど失速してるので、読み終えるのはいつになることやら……
Rust言語を勉強してるけど、だいぶ難しい〜
04.11.2025 11:03 — 👍 4 🔁 0 💬 0 📌 0ExtraのG問題は、ナップザック問題の動的計画法をベースとしてもう一歩工夫できるかを問う問題でした！
もともとDiv.2収録予定で話が進んでいたのですが、僕含め全会一致でこの問題が最難と評価され、Div.2の難易度が全体的に高めだったのでExtra送りになりました
なので、他よりテスターさん多めです
Div.1のB問題は、岩井星人さんが大量のWAに襲われるというコンセプトで作問しました！サンプルケースでも岩井星人さんがひどい目にあってます
完全オリジナルのつもりだったのですが、ほぼほぼAnother String of yuusaanのパクリだったようですね……
ちょっとだけ進歩性があるということで許して……
第2回 岩井星人アンソロジープログラミングコンテストにご参加くださった皆様、ありがとうございました！
初作問にしてDiv.1のB問題とExtraのG問題のwriterを担当させていただきました！
用事が重なってしまい、皆様と興奮をともにすることはかなわなかったのですが、不備なく終えられてよかったです！
僕のコーディングスタイルもRustに大きく影響を受けてるし、そろそろRustに移行しようかな
ライブラリ自作勢なので標準ライブラリが最小限でもあまり困らなそうだし
すごい、幻想的だ……
02.11.2025 07:48 — 👍 1 🔁 0 💬 0 📌 0嫌だ、日常に戻りたくない！
02.11.2025 03:25 — 👍 1 🔁 0 💬 0 📌 0麓に雲がかかってるとかめっちゃかっこいいじゃん
02.11.2025 01:36 — 👍 2 🔁 0 💬 0 📌 0
富士山A
富士山B
富士山C
富士山D
デッキに立ち乗りしていて周りに人がいないので、これでもかと言うほど富士山を撮りまくった
02.11.2025 01:34 — 👍 5 🔁 0 💬 1 📌 0新幹線、3時間座り続けるのはグリーン席でもキツかったので、帰りは立ち乗りする（車掌さんにもデッキならいいよって言ってもらった）
02.11.2025 01:04 — 👍 1 🔁 0 💬 0 📌 0!?
合流してから帰ればよかった……
09:42発と10:42発の便を見間違えて新幹線逃すところだった
何で1時間後の便が既に電光掲示板に表示されてんすか
