きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 113:C - ID

問題

beta.atcoder.jp

解法

(誕生した年,所属する県の番号,入力時の index) で二重 std::pair を作り,素直にソートし,県ごとに誕生した市ごとに番号を割り振っていけばよい.O(MlogM).

解答

beta.atcoder.jp

C 問題にしては良心的な問題だった(実装だけだったので).

f:id:babcs2035:20181105204039p:plain

CODE FESTIVAL 2018 qual B:C - Special Cake for CODE FESTIVAL

問題

beta.atcoder.jp

解法

以下のように X を配置するのがよい.

f:id:babcs2035:20181104154602p:plain

背景黒文字白の X 以外の X の配置場所には規則性があるので簡単における.背景黒文字白の X は規則性に基づいておいたけれども食べられるマスに配置する.O(N^2).

解答

beta.atcoder.jp

一発 AC 出来たのでよかった.

f:id:babcs2035:20181104154853p:plain

Mujin Programming Challenge 2018:E - 迷路

問題

beta.atcoder.jp

解法

ダイクストラ法を使う.この中で,あるマスである方向に動けるようになるまでずっとループを回していると O(NMKlogNM) になり間に合わないので,時刻 0 ~ K - 1 のそれぞれの時,次に上下左右に動ける時刻を O(1) で求められるように前計算をしておくことで計算量を O(NMlogNM) まで落とすことが出来る.

解答

beta.atcoder.jp

実装ミスをしていて 6 WA した...

f:id:babcs2035:20181103171304p:plain