枝刈り
AtCoder
AtCoder600点
数学(整数問題)
入力が定数個
テク:約数の個数は少ない
素因数分解
全探索:ビット全探索
全探索
拡張Euclidの互除法
中国剰余定理
枝刈り
互いに素
オーバーフロー
ある量を固定して考える
青色diff
【問題集】整数変数の式で表された条件を扱う探索
中国剰余定理使う問題楽しいよね! 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…
めちゃくちゃ面白い!!! 問題へのリンク 問題概要 (意訳) 思いを寄せている先輩に 週後に告白したいので、その日までに先輩の好感度を最大化しておきたいです。最初、「所持金」と「好感度」はともに 0 です。毎週、以下のいずれかの行動を起こすことがで…
AOJ
JAG
3-SAT
SAT
ランダムウォーク
操作
全探索
応用的な探索
スイッチ
盤面を予め変更する
復元
二次元グリッド
枝刈り
パズル
計算量が本質的に改善する枝刈り
JAG模擬地区
AOJ-ICPC
AOJ-ICPC900点
指数探索系問題
マルチテストケース問題
(定数)×Nのグリッド
枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…
Codeforces
最大公約数
ある量を固定して考える
解空間:O(N^2)通りの選択肢
数列
数学(整数問題)
互いに素
バケット
調和級数
包除原理
約数系包除
Greedy
枝刈り
stack
データ構造
エラトステネスの篩
メビウス関数
ならし計算量解析
約数
前処理
制約:数値が10^6以下
最大公約数の値を固定して考える
個人的要復習
高速メビウス変換
CodeforcesDIV2
CodeforcesR2800
思わず解きたくなる興味深い良問
高度典型
操作をstackを用いて高速化する
勉強になった...けど、これ知らずにできるもんなの!? 問題へのリンク あと、LCM の最小値バージョンもある! drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …