2020-04-05から1日間の記事一覧
AtCoder
AtCoder400点
数学(整数問題)
二分探索
最大公約数
クエリ処理問題
前処理
単調性に着目する
ランレングス圧縮
unrated公式コン
数列
操作
操作:整数をreplaceしていく
操作後の結果を求める問題
テク:ステップ数がlogオーダーで抑えられる
面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…
AtCoder
AtCoder500点
ABC-E
Greedy
各kに対して
補集合を考える
DP値:ペア値
累積和
累積和テク:左右両端からの累積和や累積結果を前処理
前処理
N個のものうち1個を変更・削除したものを解く
青色diff
0と1の問題
N個からK個を選ぶ設定の問題
制約条件:ちょうどK個
隣接2要素に制約や目的関数のある問題
典型要素を詰め合わせた教育的問題
累積和テク:累積和や累積結果を前処理しておく
最適化テク:解に確実に含まれる要素を列挙する
一次元グリッド
発想は AtCoder ABC 125 C - GCD on Blackboard (300 点) AtCoder ARC 074 D - 3N Numbers (500 点) とかに似てる。 問題へのリンク 問題概要 長さ の o と x で構成された文字列 が与えられる。 の index から 個選ぶ方法のうち 選んだ index はすべて o で…
これは問題文がいかめしいけど、ちょくだいさんのこのツイートが全てかなと思う! C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあります。ゴールまでの距離がxです。Kマスずつ進めますが、ゴールを通り過ぎてしまう場合は折り返します…
AtCoder
AtCoder400点
ABC-D
見積り大事
priority_queue
データ構造
Greedy
DFS
queue
K番目を求める
二分探索
DP
leading zero
BFS
整数を「10倍してaを足す」で捉える
緑色diff
全探索:再帰関数
【問題集】DFS・BFSのステップアップ
隣接2要素に制約や目的関数のある問題
【問題集】ビット全探索が困難な再帰全探索問題
DP状態:どの桁まで見たか(広義の桁DP)
この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…