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