テク:reverse/rotateしてもう一回やる
AtCoder
AtCoder525点
ABC-F
黄色diff
二次元グリッド
二次元セグメント木
セグメント木
長方形を3枚並べるときの切れ目に着目する
テク:reverse/rotateしてもう一回やる
最適化問題
最大スコア
最大安定集合問題
二次元累積和
累積max
DP
典型要素を詰め合わせた教育的問題
差分更新
累積和テク:左右両端からの累積和や累積結果を前処理
コーナーケース
鳩の巣原理
面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…
AtCoder
AtCoder525点
ABC-F
コーナーケース
場合分け
SをTにすることが目的の操作の問題
最短路問題
最小回数・最小個数を求める
テク:スタートを0としてよい
変数変換して扱いやすい同型な問題を見出す
最適化テク:操作の流れを単純化する
入力が定数個
パズル
鍵やアイテムを題材とした問題
アニメやゲームを元ネタとした問題
テク:reverse/rotateしてもう一回やる
水色diff
最適化問題
怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…
AtCoder
AtCoder400点
水色diff
ABC-D
DP
グリッド上のDP
二次元グリッド
解空間:O(N^2)通りの選択肢
始点と終点がともに動く経路を走査する
マンハッタン距離
最小コスト
テク:reverse/rotateしてもう一回やる
場合分け
テク:2点や2区間の配置関係を考える
ある量を固定して考える
条件の言い換え
最適化問題
結構アドホックな感覚が必要な DP で難しいと思う！ 緑色よりは上の色だろうと思ったら、案の定水色上位だった。 問題へのリンク 問題概要 のグリッドが与えられ、各マス には値 が書かれている。 グリッドから異なる 2 マス を選ぶとする。その 2 マスのス…
