2019-04-04から1日間の記事一覧
AtCoder
AtCoder400点
AGC-B
個別の要素の動きに注目する
主客転倒
区間
順列を題材とした問題
順列テク:逆順列を考える
総和を求める
setの上手な使い方
差分更新
データ構造
stack
非自明な線形時間
解空間:O(N^2)通りの選択肢
青色diff
「次の要素」へのポインタを求める
解空間:O(N^2)個の区間
操作をstackを用いて高速化する
教育的な典型問題! 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…
AtCoder
AtCoder500点
AGC-B
数珠
数列
いもす法
いもす法的変換
変数変換して扱いやすい同型な問題を見出す
操作
操作:区間に等差数列を足す
最大値や最小値に着目する
条件の言い換え
SをTにすることが目的の操作の問題
Yes/No判定問題
操作:区間
青色diff
状況がゴチャゴチャとして来て、整理するのが大変だった 問題へのリンク 問題概要 個のマスがあって最初は全マスに が書かれている。これに以下の操作を好きな回数だけ好きな順序で行って数列 にできるかどうか判定せよ。 を巡回させてできるものを足す 制約…