2021-05-01から1ヶ月間の記事一覧
数学 Hall の定理、Dilworth の定理、Koenig の定理などの同値性の証明を追った。 ノート: Hall <=> Koenig <=> Dilworth · GitHub 開発 WASM のチュートリアル: 進捗なし rust-number-theory: 進捗なし GitHub - koba-e964/rust-quantifier-elimination: Qu…
競プロ CODE FESTIVAL 2014 Hard - AtCoder: D を解説 AC した。 ABC 203: 参加。 F で詰まりまくった。
競プロ Code Festival Team Relay (Parallel) - AtCoder: G, I を解説 AC し、J を解いた。 J: ネタバレ→n^2 が通る制約なので最初はフローかと思ったが、冷静に考えたら [0, i) までの情報を持っておける + 区間で更新する際前計算が効く ということに気づ…
競プロ https://atcoder.jp/contests/hbpc2012: C と D を解いた。 C: 構文解析がだるかった。 D: 負けそうなときは -min(遷移先評価値) + 1 を、勝ちそうなときは -min(遷移先評価値) - 1 を評価値にしないといけないのにそれに思い至るまでに時間がかかっ…
競プロ 自明を数問倒した。
競プロ CODE FESTIVAL 2017 Elimination Tournament Round 3 (Parallel) - AtCoder: E を解き、F を解説 AC した。 E: https://atcoder.jp/contests/cf17-tournament-round3-open/editorial/1946 F: ネタバレ→サイクルに含まれる頂点集合を全探索すればよさ…
その他 スプラ 2 時間。
数学 Hall の定理、Dilworth の定理、Koenig の定理などの同値性の証明を追った。 ノート: Hall <=> Koenig <=> Dilworth · GitHub 競プロ ARC120: D を解いた。
数学 進捗なし 開発 WASM のチュートリアル: 進捗なし rust-number-theory: 進捗なし GitHub - koba-e964/rust-quantifier-elimination: Quantifier elimination: 進捗なし 競プロ 競プロ典型 90 問 41-47 解き。 パ研合宿2020 第2日「パ研杯2020」 - AtCode…
競プロ ABC202: F 解説 AC。
競プロ Japanese Student Championship 2021 - AtCoder: F, H を解説 AC した。 F: ネタバレ→平衡二分探索木があれば解けそうかなというのはわかっていたが詳細を詰め切れなかった。セグメント木は貧者の平衡二分探索木なので、平衡二分探索木が必要そうなと…
競プロ dwangoプログラミングコンテスト - AtCoder: C を解いた。
競プロ 京都大学プログラミングコンテスト2012 - AtCoder: J を解いた。 J: ネタバレ→最適二分探索木の構築と同様に Knuth-Yao speedup で O(n^2) 時間。←ネタバレ Indeedなう（オープンコンテスト） - AtCoder: F を解説 AC した。 F: ネタバレ→愚直はフロ…
競プロ 自明な問題を何問か通した気がする。
競プロ パ研合宿2020 第2日「パ研杯2020」 - AtCoder: D, E を解いた。 D: ネタバレ→トポロジカルソートに帰着させる。そのままだと辺の本数が O(N^2) になってしまうので、動物用のノードを挟めばよい。←ネタバレ E: ネタバレ→直線と点は双対的な関係にある…
競プロ 凸包のライブラリを Rust で書いた。
数学 進捗なし 開発 WASM のチュートリアル: 進捗なし rust-number-theory: 進捗なし GitHub - koba-e964/rust-quantifier-elimination: Quantifier elimination: 進捗なし 競プロ 競プロ典型 90 問 35-40 解き。 JOIG 2021 過去問 - AtCoder: F 解き。 JOI …
競プロ 自明な問題は載せるのをやめます。 code thanks festival 2014 B: 解いた。 H: ネタバレ→単純な必要条件の列挙 (連結成分 - 1, 奇数次数の点 / 2 - 1) ではうまくいかない。偶数次数の点しかない連結成分を別の連結成分と繋ごうとする時、絶対に奇数…
競プロ 第2回早稲田大学プログラミングコンテスト: A-D, F-H を解いた。 F: ネタバレ→8NML 頂点のグラフを作ったら MLE して嫌な気持ちに。結局 辺の行き先を usize ではなく i32 で持ってメモリ半減・グラフを Vec> ではなく一本の Vec で持ってアロケーシ…
競プロ AtCoder の Rust での AC 数のランキングで、自分の両隣の人との AC 数の差を表示するスクリプトを書いた。 Add atcoder/ranking.py · koba-e964/contest@1b291c9 · GitHub
競プロ ARC118 A-D を解いた。 D: ネタバレ→数学的な解法に最初目が行ったが、よく考えたらグリッド状に数を並べることができさえすればあとはグリッドの一筆書きに帰着できるので、グリッドにした時点で数学をやめるべきだった。図を描くのは大事。←ネタバレ
競プロ JOI 2020/2021 本選: D を解説 AC した。ネタバレ→「辺 e を通った後、同じ色の辺 e 以外の辺を通る」という制約をグラフの形にエンコードするのがかなり難しいと思ったが、よく考えたら同じ辺を 2 度通るのは最短経路としてはあり得ないので、「辺 e…
競プロ 競プロ典型 90 問 35-37 を解いた。 JOI 2020/2021 二次予選 過去問の E を解いた。2-SAT っぽい考察で面白かった。 JOI 2020/2021 本選: A, B, C を解いた。
競プロ JOIG 2021 過去問 - AtCoder: F を解いた。考察にかなり時間がかかってしまった。私の解法だと定数倍が厳しかった。 JOI 2020/2021 二次予選 過去問の A-D を解いた。
数学 Enumerative Combinatorics のゼミに参加。3.11 をやった。 開発 WASM のチュートリアル: 進捗なし rust-number-theory: 進捗なし GitHub - koba-e964/rust-quantifier-elimination: Quantifier elimination: 進捗なし 競プロ 競プロ典型 90 問 30-34 …
競プロ 最小費用流のライブラリ整備をやった。 JOIG 2021 過去問 - AtCoderの A-E を埋めた。
数学 Enumerative Combinatorics のゼミに参加。3.11 をやったが、中身があまり追えていない。
その他 「風の声を聴きながら」の耳コピをした。一番だけ。 スロウスタート観たい気分に…。
数学 Enumerative Combinatorics のゼミ。
競プロ PAST 第二回を、答えを知っている状態で通した。ダラダラやっていて + 実装が迷走して M にかなり時間をかけてしまった。 第二回日本最強プログラマー学生選手権: 解いている途中。 F: 配列に対する二分探索、部分配列の rotation, 部分配列の和の計…
