JOI Kakisemi Contest 2019:D - ふたつのケーキ
問題
https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2155
S 人の人と 2 種類のケーキがある.イチゴケーキは N 個に分かれていて,ショートケーキ M 個に分かれている.イチゴケーキに関しては, S 人に分ける個数が決まっている.ここで,各人について,2 種類のケーキを取る個数の差の 2 乗の和を最小化する問題.
解法
小課題1
S = 2 より人は 2 人しかない.よって,イチゴケーキを分ける境目の個数の近くの切れ目 2 通りを試せばよい.(x / N) >= (y / M) の一次不等式を解けば四則演算のみで解ける.
小課題2
N, M <= 50 より DP を考える.
dp[何人目まで配分を決めたか][ショートケーキを既に配分した個数] とおくと,O(S * M^2) となる.高速化すると O(SM) などにすることができるが,後の小課題にはつながらない.
小課題3
各人について誤差の 2 乗は x 軸を N, y 軸を M とする二次元平面状で下に凸の放物線になる.この放物線の傾きは単調増加なので priority_queue などで O(MlogS) で求められる.
小課題4
ギリギリ (B_i / M) <= (A_i / N) であるような B_i を求めればよい.これは誤差をソートして計算すればよく,小課題3より O(SlogS).
また,微分係数を二分探索しても解くことができる.
JOI Kakisemi Contest 2019:C - 魔法の宝石
問題
https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2154
解法
小課題1
H, W == 2.なので,全てのマスが同じ文字であるか調べればよい.
小課題2
H, W <= 30 なので,約 20 万通りしかなく全通り試せばよい.
小課題3
全ての文字は同じなので,答えは C(H, 2) * C(W, 2).
小課題4
まず 2 行を固定し,2 * W の問題を考える.まず,2 列が異なっているものは採用できない.文字 c ごとに C(2 列が同じ c になっているものの数, 2) を足したものが 2 行を固定したときの答えとなる.これは O(W) で解ける.
あとは拡張して O(H^2 * W) で解ける.
JOI Kakisemi Contest 2019:B - 将棋
問題
https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2153
解法
ビ太郎の左方向の動きを考える.これは,1 行を支配していると考えてよいので,1 行に複数個のビ太郎を置くことはできない.
また,上下右方向の動きは実は無視できる.これは,W >= 3 であるから,ある行の上と下にビ太郎が置かれていても,その行のどれか 1 つのマスには置くことができる.
よって,答えは H - (ビ太郎の個数) となる.
解答