2020-09-20から1日間の記事一覧
AtCoder
AtCoder500点
ABC-E
ダブリング
周期性に着目する
サイクル
数学(整数問題)
数列
漸化式
鳩の巣原理
総和を求める
操作:整数をreplaceしていく
緑色diff
Functionalグラフ
サイクル検出
グラフ
操作
この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…
AtCoder
AtCoder400点
ABC-D
DP
DP高速化
DP高速化:累積和
累積和
いもす法
DP高速化:いもす法
数え上げ問題
部分和
多項式・FPS(形式的冪級数)
級数和を求める
FPS(形式的冪級数)の高等演算
水色diff
区間
N個の区間の問題
操作列を数え上げる問題
典型要素を詰め合わせた教育的問題
【問題集】DPのステップアップ
disjointな区間の集合を管理する問題
迷路
すごろく
一次元グリッド
DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした!) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …
AtCoder
AtCoder600点
ABC-F
オセロ
操作:flip
データ構造
クエリ処理問題
遅延評価
セグメント木
二次元グリッド
単調性に着目する
しゃくとり法
ならし計算量解析
差分更新
青色diff
縦方向と横方向の情報を整理する
駒(コマ)や石やコインを扱う問題
遅延評価セグメント木
【問題集】遅延評価セグメント木
早速遅延セグ木があればできる問題来た!! AC Library の出番かと思った!!! 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…