2020-12-20から1日間の記事一覧
Stern-Brocot 木がちょうどよく使える 問題へのリンク 問題概要 正の整数 が与えられる。分子・分母がともに 以下の正の整数であって、既約分数であるような分数の集合を と表すことにする。 を満たす最大の の要素 を満たす最小の の要素 をそれぞれ求めよ…
AtCoder
AtCoder600点
ABC-F
水色diff
マージテク
DP
Union-Find
Union-Findのマージ過程を表す木を考える
データ構造
クエリ処理問題
色に関する問題
Union-Find上のDP
Eulerツアー
in-place DP
クエリ先読み
中堅以上の典型要素を詰め合わせた教育的問題
マージテクを知らなくても雰囲気で通せるのかもしれない 問題へのリンク 問題概要 人の生徒がそれぞれクラス に所属している。 各生徒はそれぞれの家から出発したあと、他の生徒と合流を繰り返しながら学校へ向かう。一度合流した生徒が分かれることはない。…
AtCoder
AtCoder600点
ABC-F
青色diff
BIT
平面走査
データ構造
二次元グリッド
包除原理
sparseな問題
差分更新
迷路
セグメント木
縦方向と横方向の情報を整理する
壁マス
「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…
AtCoder
AtCoder500点
ABC-E
数学(整数問題)
拡張Euclidの互除法
最大公約数
数珠
水色diff
Euler関数
Giant-Step Baby-Step法
中国剰余定理
マルチテストケース問題
一次合同方程式を解く問題です! 問題へのリンク 問題概要 円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。 高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。 行動:いま座っている椅子から時計…