naoya_t@hatenablog

いわゆるチラシノウラであります

codeFlyer予選

oox-- 400位

A - 本選参加者数

割って掛ける
→AC
https://bitflyer2018-qual.contest.atcoder.jp/submissions/2596588

B - 洋菓子店

シミュレーション
→AC
https://bitflyer2018-qual.contest.atcoder.jp/submissions/2597721

C - 徒歩圏内

都市jから左に距離D以内の都市:before_j
都市jから右に距離D以内の都市数:after_j
はlower_bound(), upper_bound()でそれぞれlogNで求まるのでO(NlogN)
before_j\cdot after_j で、区間i-jと区間j-kを徒歩で行くことになるパターン数
ここからi-kがD以内になるケースを引きたいのだけれど…
→考えがj(tripletの真ん中の都市)に固定しすぎてて、「距離D以内の区間でjを跨ぐもの」を数えて引くような実装をしていた(これはi-kに収まらない区間も入るから駄目なのでは?という)
→WA(1)
https://bitflyer2018-qual.contest.atcoder.jp/submissions/2601073

飛ばしてDへ

【解説を読んで】
左の端iを固定して、そこから距離D以内、ってのは先に求めた after_i があるからそれを使う。
n=after_i のとき、都市i+1 から 都市i+n までの全ての都市が、都市iから距離D以内である。2≦d≦n なd を取り、都市i+d を右端(k)としたとき、真ん中の都市(j)として取れるのはd-1通り、ということは全部で
$$ \sum_{d=2}^{after_i}{d-1} = \frac{after_i(after_i-1)}{2} $$
通りの、i-kが距離D以内という条件を満たすtripletが都市iについて存在する。 従って

$$ \sum_{j=1}^{N-1}{before_j\times after_j} - \sum_{i=0}^{N-1}{\frac{after_i(after_i-1)}{2} } $$
→AC
https://bitflyer2018-qual.contest.atcoder.jp/submissions/2603263

D - ハンコ

幅がmin(W, 2M-1) になるように(重ねながら)引き伸ばして
高さがmin(H, 2N-1) になるように(重ねながら)引き伸ばして
幅と高さが2M-1, 2N-1を超えるときは真ん中の行(ないし列)の和に超過分を掛けたやつを足して(真ん中でクロスする分は引いて)出来上がり
計算量的にはO(MN)かな

Cではまってて時間足りなかった…
→事後AC
https://bitflyer2018-qual.contest.atcoder.jp/submissions/2602964

E - 祝日

開いてない