AtCoder Beginner Contest 113:C - ID
問題
解法
(誕生した年,所属する県の番号,入力時の index) で二重 std::pair を作り,素直にソートし,県ごとに誕生した市ごとに番号を割り振っていけばよい.O(MlogM).
解答
C 問題にしては良心的な問題だった(実装だけだったので).
CODE FESTIVAL 2018 qual B:C - Special Cake for CODE FESTIVAL
問題
解法
以下のように X を配置するのがよい.
背景黒文字白の X 以外の X の配置場所には規則性があるので簡単における.背景黒文字白の X は規則性に基づいておいたけれども食べられるマスに配置する.O(N^2).
解答
一発 AC 出来たのでよかった.
Mujin Programming Challenge 2018:E - 迷路
問題
解法
ダイクストラ法を使う.この中で,あるマスである方向に動けるようになるまでずっとループを回していると O(NMKlogNM) になり間に合わないので,時刻 0 ~ K - 1 のそれぞれの時,次に上下左右に動ける時刻を O(1) で求められるように前計算をしておくことで計算量を O(NMlogNM) まで落とすことが出来る.
解答
実装ミスをしていて 6 WA した...