elphe
@elphe.bsky.social
とりあえずRustで自作のUnionFindを書いてみた
（英語力がないので関数名が…）
（英語力がないので関数名が…）
![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)
November 9, 2025 at 9:16 AM
とりあえずRustで自作のUnionFindを書いてみた
（英語力がないので関数名が…）
（英語力がないので関数名が…）
ABC431おわりっ！18分11秒でABCD問題をノーペナ4完！
A問題はmax(H,B)-Bが答え
B問題はフラグの配列をもっておいて、加算か減算か決める
C問題はそれぞれをソートして、軽い方の頭から対応する体を決める
対応する体は、極力軽い体を選ぶ貪欲法でOK
D問題はナップサックDP
つまるところ、全体の重さの半分以下を頭部に持ってこれるので、全体の重さの半分をナップサック耐久度としてナップサックDPを行えばよい
E問題はなぜか合わない
マス(i,j)から方向dに光が出たときの答えを01BFSで順次求めていけば良さそうになったけど、サンプルが通らない
F問題まったくわからん
A問題はmax(H,B)-Bが答え
B問題はフラグの配列をもっておいて、加算か減算か決める
C問題はそれぞれをソートして、軽い方の頭から対応する体を決める
対応する体は、極力軽い体を選ぶ貪欲法でOK
D問題はナップサックDP
つまるところ、全体の重さの半分以下を頭部に持ってこれるので、全体の重さの半分をナップサック耐久度としてナップサックDPを行えばよい
E問題はなぜか合わない
マス(i,j)から方向dに光が出たときの答えを01BFSで順次求めていけば良さそうになったけど、サンプルが通らない
F問題まったくわからん
November 8, 2025 at 1:47 PM
ABC431おわりっ！18分11秒でABCD問題をノーペナ4完！
A問題はmax(H,B)-Bが答え
B問題はフラグの配列をもっておいて、加算か減算か決める
C問題はそれぞれをソートして、軽い方の頭から対応する体を決める
対応する体は、極力軽い体を選ぶ貪欲法でOK
D問題はナップサックDP
つまるところ、全体の重さの半分以下を頭部に持ってこれるので、全体の重さの半分をナップサック耐久度としてナップサックDPを行えばよい
E問題はなぜか合わない
マス(i,j)から方向dに光が出たときの答えを01BFSで順次求めていけば良さそうになったけど、サンプルが通らない
F問題まったくわからん
A問題はmax(H,B)-Bが答え
B問題はフラグの配列をもっておいて、加算か減算か決める
C問題はそれぞれをソートして、軽い方の頭から対応する体を決める
対応する体は、極力軽い体を選ぶ貪欲法でOK
D問題はナップサックDP
つまるところ、全体の重さの半分以下を頭部に持ってこれるので、全体の重さの半分をナップサック耐久度としてナップサックDPを行えばよい
E問題はなぜか合わない
マス(i,j)から方向dに光が出たときの答えを01BFSで順次求めていけば良さそうになったけど、サンプルが通らない
F問題まったくわからん
さっきたまたまAtCoderのコンパイルコマンド確認しに行ったら、C++のコンパイルコマンドがとんでもないことになっててびっくりした
大半はインクルード指定のオプションだったけど、よく見るとfconstexpr系のオプションに渡される値が大幅削減されてた（元々の値がデカすぎた）
大半はインクルード指定のオプションだったけど、よく見るとfconstexpr系のオプションに渡される値が大幅削減されてた（元々の値がデカすぎた）
November 8, 2025 at 12:44 AM
さっきたまたまAtCoderのコンパイルコマンド確認しに行ったら、C++のコンパイルコマンドがとんでもないことになっててびっくりした
大半はインクルード指定のオプションだったけど、よく見るとfconstexpr系のオプションに渡される値が大幅削減されてた（元々の値がデカすぎた）
大半はインクルード指定のオプションだったけど、よく見るとfconstexpr系のオプションに渡される値が大幅削減されてた（元々の値がデカすぎた）
四条駅から松ヶ崎駅まで2+4+6+8+10+12+14=56分！？市営地下鉄にしては長すぎやろ！！
（実際は四条駅から松ヶ崎駅までで14分）
（実際は四条駅から松ヶ崎駅までで14分）
November 7, 2025 at 12:41 AM
四条駅から松ヶ崎駅まで2+4+6+8+10+12+14=56分！？市営地下鉄にしては長すぎやろ！！
（実際は四条駅から松ヶ崎駅までで14分）
（実際は四条駅から松ヶ崎駅までで14分）
とりあえず「The Rust Programming Language 日本語版」を5日で1～16章まで読破したけど、かなり苦しいぞ……
特に後半になるほど失速してるので、読み終えるのはいつになることやら……
特に後半になるほど失速してるので、読み終えるのはいつになることやら……
November 6, 2025 at 2:18 PM
とりあえず「The Rust Programming Language 日本語版」を5日で1～16章まで読破したけど、かなり苦しいぞ……
特に後半になるほど失速してるので、読み終えるのはいつになることやら……
特に後半になるほど失速してるので、読み終えるのはいつになることやら……
第2回 岩井星人アンソロジープログラミングコンテストにご参加くださった皆様、ありがとうございました！
初作問にしてDiv.1のB問題とExtraのG問題のwriterを担当させていただきました！
用事が重なってしまい、皆様と興奮をともにすることはかなわなかったのですが、不備なく終えられてよかったです！
初作問にしてDiv.1のB問題とExtraのG問題のwriterを担当させていただきました！
用事が重なってしまい、皆様と興奮をともにすることはかなわなかったのですが、不備なく終えられてよかったです！
November 3, 2025 at 10:17 AM
第2回 岩井星人アンソロジープログラミングコンテストにご参加くださった皆様、ありがとうございました！
初作問にしてDiv.1のB問題とExtraのG問題のwriterを担当させていただきました！
用事が重なってしまい、皆様と興奮をともにすることはかなわなかったのですが、不備なく終えられてよかったです！
初作問にしてDiv.1のB問題とExtraのG問題のwriterを担当させていただきました！
用事が重なってしまい、皆様と興奮をともにすることはかなわなかったのですが、不備なく終えられてよかったです！
僕のコーディングスタイルもRustに大きく影響を受けてるし、そろそろRustに移行しようかな
ライブラリ自作勢なので標準ライブラリが最小限でもあまり困らなそうだし
ライブラリ自作勢なので標準ライブラリが最小限でもあまり困らなそうだし
November 2, 2025 at 10:47 AM
僕のコーディングスタイルもRustに大きく影響を受けてるし、そろそろRustに移行しようかな
ライブラリ自作勢なので標準ライブラリが最小限でもあまり困らなそうだし
ライブラリ自作勢なので標準ライブラリが最小限でもあまり困らなそうだし
デッキに立ち乗りしていて周りに人がいないので、これでもかと言うほど富士山を撮りまくった
November 2, 2025 at 1:34 AM
デッキに立ち乗りしていて周りに人がいないので、これでもかと言うほど富士山を撮りまくった
新幹線、3時間座り続けるのはグリーン席でもキツかったので、帰りは立ち乗りする（車掌さんにもデッキならいいよって言ってもらった）
November 2, 2025 at 1:04 AM
新幹線、3時間座り続けるのはグリーン席でもキツかったので、帰りは立ち乗りする（車掌さんにもデッキならいいよって言ってもらった）
09:42発と10:42発の便を見間違えて新幹線逃すところだった
何で1時間後の便が既に電光掲示板に表示されてんすか
何で1時間後の便が既に電光掲示板に表示されてんすか
November 2, 2025 at 12:47 AM
09:42発と10:42発の便を見間違えて新幹線逃すところだった
何で1時間後の便が既に電光掲示板に表示されてんすか
何で1時間後の便が既に電光掲示板に表示されてんすか
Now located in: 新宿ダンジョン
Scanning area............FAILED
Searching way back............FAILED
Sending rescue signal............FAILED
Scanning area............FAILED
Searching way back............FAILED
Sending rescue signal............FAILED
November 2, 2025 at 12:20 AM
Now located in: 新宿ダンジョン
Scanning area............FAILED
Searching way back............FAILED
Sending rescue signal............FAILED
Scanning area............FAILED
Searching way back............FAILED
Sending rescue signal............FAILED
ホテルのカミソリの使い方わからんくて顔面出血しまくってて草
November 1, 2025 at 10:29 PM
ホテルのカミソリの使い方わからんくて顔面出血しまくってて草
ABC430おわりっ！87分18秒でABCDE問題をノーペナ5完！
A問題は「仮定を満たしつつ、結論が満たされていない」かどうか
B問題は選択範囲の左上を全探索して、選択範囲内の文字の配置をstringかなにかに変換してsetに突っ込み、最終的なsizeを答える
C問題は左からi文字目までに何個のA,Bがそれぞれ出現するかを累積和のように求め、lを全探索してrの存在範囲を累積和上の二分探索で決定する
D問題はset上で二分探索するだけだが、実装が非常に面倒
色々バグらせて時間を失ってしまった
E問題はローリングハッシュで解決
なんでこれを思いつくのに25分もかかるんですかね……
A問題は「仮定を満たしつつ、結論が満たされていない」かどうか
B問題は選択範囲の左上を全探索して、選択範囲内の文字の配置をstringかなにかに変換してsetに突っ込み、最終的なsizeを答える
C問題は左からi文字目までに何個のA,Bがそれぞれ出現するかを累積和のように求め、lを全探索してrの存在範囲を累積和上の二分探索で決定する
D問題はset上で二分探索するだけだが、実装が非常に面倒
色々バグらせて時間を失ってしまった
E問題はローリングハッシュで解決
なんでこれを思いつくのに25分もかかるんですかね……
November 1, 2025 at 1:52 PM
ABC430おわりっ！87分18秒でABCDE問題をノーペナ5完！
A問題は「仮定を満たしつつ、結論が満たされていない」かどうか
B問題は選択範囲の左上を全探索して、選択範囲内の文字の配置をstringかなにかに変換してsetに突っ込み、最終的なsizeを答える
C問題は左からi文字目までに何個のA,Bがそれぞれ出現するかを累積和のように求め、lを全探索してrの存在範囲を累積和上の二分探索で決定する
D問題はset上で二分探索するだけだが、実装が非常に面倒
色々バグらせて時間を失ってしまった
E問題はローリングハッシュで解決
なんでこれを思いつくのに25分もかかるんですかね……
A問題は「仮定を満たしつつ、結論が満たされていない」かどうか
B問題は選択範囲の左上を全探索して、選択範囲内の文字の配置をstringかなにかに変換してsetに突っ込み、最終的なsizeを答える
C問題は左からi文字目までに何個のA,Bがそれぞれ出現するかを累積和のように求め、lを全探索してrの存在範囲を累積和上の二分探索で決定する
D問題はset上で二分探索するだけだが、実装が非常に面倒
色々バグらせて時間を失ってしまった
E問題はローリングハッシュで解決
なんでこれを思いつくのに25分もかかるんですかね……
岩プロコンの作問でご一緒したみうねさんとおしゃべりする機会もあって楽しかった！
shuntaさんとも話したくて探したけど見つけられなかった……（顔も服装も知らない相手を名札だけで約100人の集団から見つけるのはかなり困難）
shuntaさんとも話したくて探したけど見つけられなかった……（顔も服装も知らない相手を名札だけで約100人の集団から見つけるのはかなり困難）
November 1, 2025 at 11:38 AM
岩プロコンの作問でご一緒したみうねさんとおしゃべりする機会もあって楽しかった！
shuntaさんとも話したくて探したけど見つけられなかった……（顔も服装も知らない相手を名札だけで約100人の集団から見つけるのはかなり困難）
shuntaさんとも話したくて探したけど見つけられなかった……（顔も服装も知らない相手を名札だけで約100人の集団から見つけるのはかなり困難）
あかん、寝坊したかも……
（まだ50%を超える確率で間に合いそうではあるが……）
（まだ50%を超える確率で間に合いそうではあるが……）
October 31, 2025 at 10:01 PM
あかん、寝坊したかも……
（まだ50%を超える確率で間に合いそうではあるが……）
（まだ50%を超える確率で間に合いそうではあるが……）
B問題のwriterを担当しております！そんなに難しくないかもですが、ぜひ楽しんでください！
岩プロコン実行委員会 on X: "🪨お知らせ👾 「第2回 岩井星人アンソロジープログラミングコンテスト Div.1」が10/31 21:00から、「第2回 岩井星人アンソロジープログラミングコンテスト Extra」が11/1 15:00から開催されます！ ふるってご参加ください！ https://t.co/abaszvwH8k https://t.co/0F7jDqutMQ" / X
🪨お知らせ👾 「第2回 岩井星人アンソロジープログラミングコンテスト Div.1」が10/31 21:00から、「第2回 岩井星人アンソロジープログラミングコンテスト Extra」が11/1 15:00から開催されます！ ふるってご参加ください！ https://t.co/abaszvwH8k https://t.co/0F7jDqutMQ
x.com
October 31, 2025 at 9:16 AM
B問題のwriterを担当しております！そんなに難しくないかもですが、ぜひ楽しんでください！
偶然お菓子を2つ入手したので、闇の呪文「トリックオアトリート」を唱えられても2回まで耐えられる
October 31, 2025 at 1:59 AM
偶然お菓子を2つ入手したので、闇の呪文「トリックオアトリート」を唱えられても2回まで耐えられる
図書館が静かすぎる
自分の呼吸の音はおろか、心音すら空間全体にこだまするかのようで落ち着かないんだが
イヤホンで爆音のGothic Hardcoreを聴いて心を落ち着かせます
自分の呼吸の音はおろか、心音すら空間全体にこだまするかのようで落ち着かないんだが
イヤホンで爆音のGothic Hardcoreを聴いて心を落ち着かせます
October 28, 2025 at 1:00 AM
図書館が静かすぎる
自分の呼吸の音はおろか、心音すら空間全体にこだまするかのようで落ち着かないんだが
イヤホンで爆音のGothic Hardcoreを聴いて心を落ち着かせます
自分の呼吸の音はおろか、心音すら空間全体にこだまするかのようで落ち着かないんだが
イヤホンで爆音のGothic Hardcoreを聴いて心を落ち着かせます
ABC429おわりっ！ABCDE問題を50分47秒でノーペナ5完！（Unrated参加)
A問題は言われたとおりやる
M≦Nが保証されていないので、変なことしようとすると危険
B問題はAの総和がM以上かつ、(Aの総和)-Mが数列Aに含まれていることと同値
sortとかaccumulateとかbinary_searchとかで楽に記述
C問題は定番の組み合わせの問題
1≦i＜j＜k≦Nは単に順番を区別しないためだけの条件なので気にしなくて良い
Aの度数分布表を作って、重複する値を決め打ちして、その値がAに含まれる個数をcとすると、(c*(c-1)/2)*(N-c)を加算していけばよい
A問題は言われたとおりやる
M≦Nが保証されていないので、変なことしようとすると危険
B問題はAの総和がM以上かつ、(Aの総和)-Mが数列Aに含まれていることと同値
sortとかaccumulateとかbinary_searchとかで楽に記述
C問題は定番の組み合わせの問題
1≦i＜j＜k≦Nは単に順番を区別しないためだけの条件なので気にしなくて良い
Aの度数分布表を作って、重複する値を決め打ちして、その値がAに含まれる個数をcとすると、(c*(c-1)/2)*(N-c)を加算していけばよい
October 25, 2025 at 1:44 PM
ABC429おわりっ！ABCDE問題を50分47秒でノーペナ5完！（Unrated参加)
A問題は言われたとおりやる
M≦Nが保証されていないので、変なことしようとすると危険
B問題はAの総和がM以上かつ、(Aの総和)-Mが数列Aに含まれていることと同値
sortとかaccumulateとかbinary_searchとかで楽に記述
C問題は定番の組み合わせの問題
1≦i＜j＜k≦Nは単に順番を区別しないためだけの条件なので気にしなくて良い
Aの度数分布表を作って、重複する値を決め打ちして、その値がAに含まれる個数をcとすると、(c*(c-1)/2)*(N-c)を加算していけばよい
A問題は言われたとおりやる
M≦Nが保証されていないので、変なことしようとすると危険
B問題はAの総和がM以上かつ、(Aの総和)-Mが数列Aに含まれていることと同値
sortとかaccumulateとかbinary_searchとかで楽に記述
C問題は定番の組み合わせの問題
1≦i＜j＜k≦Nは単に順番を区別しないためだけの条件なので気にしなくて良い
Aの度数分布表を作って、重複する値を決め打ちして、その値がAに含まれる個数をcとすると、(c*(c-1)/2)*(N-c)を加算していけばよい