ABC037 考察

abc037 A - 饅頭

C / MIN(A, B) (/ は切り捨て) で求められる。

https://atcoder.jp/contests/abc037/submissions/16766617

abc037 B - 編集

N, Q <= 100 なので 2 重ループ (O(NQ)) で間に合う。

https://atcoder.jp/contests/abc037/submissions/16766710

abc037 C - 総和

K, N <= 10^5 なので 2 重ループ (O(KN)) では間に合わない。区間が 1 つ右にずれるごとに K 個の和は - A_i + A_{i + k} ずつ変化する。最初に先頭から K 個の和を求めておき変化した和を合計すれば O(N) となり間に合う。

https://atcoder.jp/contests/abc037/submissions/16766899

abc037 D - 経路

値の大きいマスから小さいマスへと順に移動経路の個数を求める。理由は問題文の通りの移動で小さいマスから計算すると何度も途中の経路の計算が必要だからだ。各マスの移動経路の個数を合算すれば答えになる。

各マスについて入る辺と出る辺を調べる。出る辺がないものを順に走査する。それぞれ自身で止まる一回と自身までの移動回数を入る辺をたどった頂点に足していく。辿った辺は消していく。走査済みのものに印をつけておく。

大きいマスから小さいマスへと順に走査済みでないものがあればたどる。

最初は一番大きいところからたどれば良いかと思ったのだけど途中で途切れてしまう可能性があったので途切れるところまで辿って未走査ならそこから再開を繰り返している。

計算量が怪しいけど間に合った。

想定解はメモ化再帰のようだ。それが思いつかないから ABC178 の D を解けなかった。

https://atcoder.jp/contests/abc037/submissions/16768460

リングフィットアドベンチャーを続けている。

週末に映画 TENET を観ることにした。子どもを預けて妻とふたり結婚記念日に映画と食事でも……と考えたからだ。さっそく予約をしようと映画館のサイトを見たところ新型コロナウイルス対策で席がひとつ飛ばしになっていた。ベタベタくっつきたいわけではないのだけどふたりで行ってひとつ空けて座るというのも趣旨にてらしてもなんだかなあと思った。