2020-08-17から1日間の記事一覧
AtCoder
AtCoder300点
ABC-C
パリティ
コーナーケース
場合分け
操作
最適化テク:最適解の形を考える
数学(整数問題)
操作:整数をreplaceしていく
茶色diff
操作をちょうどK回行う
ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう! 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…
AtCoder
AtCoder400点
ABC-D
順列を題材とした問題
操作をK回まで行える
周期性に着目する
グラフ
サイクル
ダブリング
コーナーケース
最適化テク:最適解の形を考える
条件の言い換え
数珠
ある量を固定して考える
テク:循環するものを二週させる
累積和
最大スコア
順列テク:巡回群の直積と見る
水色diff
Functionalグラフ
サイクル検出
順列テク:写像と見る
最適化問題
異様に難しかった!! 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…
AtCoder
AtCoder500点
ABC-E
DP
二次元グリッド
グリッド上のDP
DP状態:個数
二次元平面上のN点の問題
水色diff
鍵やアイテムを題材とした問題
迷路
最大スコア
最適化問題
最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…