JOI Kakisemi Contest 2019：A - マルバツスタンプ２
問題
https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2152
解法
正しいマルバツスタンプは 2 通りしかないので，この 2 つのうち操作が少ない方を採用すればよい．
解答
大手前プロコン 2019：G - 空をかけるピ太郎 (Pitaro, who Leaps through Air)
問題
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g
解法
N が大きいので，P, Q, R, S, A_i, B_i, C_i, D_i を x, y 座標に分けて座標圧縮をする．また，上下・左右方向にワープ可能な領域をそれぞれ累積和で求めておく．このとき，別のワープ可能な領域が隣り合っているとき，隣り合っているところをまたぐ際にコストが生じるので，累積和を求める段階で 0 を検出したらコストがかかると判定する必要がある．これで各マス間の移動のコストが求まったので，二次元平面上でダイクストラ法を使って (P, Q) から (R, S) の最短距離を求めればよい．O(M^2 * logM)．
解答
https://atcoder.jp/contests/otemae2019/submissions/6723072
実装がかなり大変だった．
大手前プロコン 2019：F - 天秤とコイン (Balance and Coins)
問題
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f
解法
以下の DP を考える．
dp(i, j) := i 日目で右側に j 枚コインがあるとき，i + 1 日目以降のコストの和の最小値
遷移は，右側にのせるコインは j 枚のまま次の日にいくか，右側にのせるコインを 1 枚増やすかの 2 通りになる．dp(i, j) = min( dp(i + 1, j) + std::abs(M[i][j] - (M[i][N] - M[i][j])), dp(i, j + 1) ) とすればよい．1 ~ k 枚目までのコインの重さの総和を O(1) で得られるようにするため，前処理で累積和を各日ごとにとっておく．O(ND)．
解答
https://atcoder.jp/contests/otemae2019/submissions/6701800
