noya2のブログ

noya2の精進記録

AtCoder Beginner Contest 257 参加記

ooooooo-

A問題。$\lfloor\frac{x-1}{n}\rfloor$ 番目(0_indexed)の英大文字を出力すればよい。

B問題。左から $i$ 番目の駒の位置 $a[i]$ の配列を持ってシュミレーション。

C問題。体重でソートしておく。候補となる $X$ は $W_i$ と $W_i-\varepsilon$ だけとしてよい。同じ体重の人に気をつけて map<体重,pair<その体重の子供の人数,その体重の大人の人数>> などとして管理。候補となる $X$ の昇順に $X$ 未満の体重の子供と大人、$X$ 以上の体重の子供と大人の人数をそれぞれ更新しながら全部試せばよい。難しい。

D問題。答えで二分探索。上限に気をつけないといけないが、3WA した。$S$ を決め打った後は愚直にグラフを構築し bfs などで愚直に判定しても余裕で通る。

E問題。桁数が分かる。最も安い値段でその桁数を稼ぐとして、余った予算で上の桁から貪欲に大きくしていけばよい。

F問題。テレポーターと言えば超頂点。超頂点 $A,B$ を用意する。$(0,v)$ の辺は $v\rightarrow A, B\rightarrow v$ の辺を張ることにする。未確定のテレポーターの行き先が $k$ だとすると、構築したグラフにさらに $A\rightarrow k,k\rightarrow B$ の辺を張ったグラフの最短経路問題になる。これは $1\rightarrow N,1\rightarrow A\rightarrow k\rightarrow N,1\rightarrow k\rightarrow B\rightarrow N,1\rightarrow A\rightarrow k\rightarrow B\rightarrow N$ の $4$ 通りの経路を考えればよく、始点を $1,N,B$ とした各頂点への最短経路を前計算することで任意の $k$ に対して $\Theta (1)$ で求められる。

G問題。後ろから見るDPを考えると、任意の $t$ の suffix に対して $s$ との lcp(longest-common-prefix) を求めたい気がする。ACLのz-algorithmをよく読むと $s+t$ に対して適用すればよさそう。あとは区間最小値一点更新のセグ木を用いて高速化。文字列にあまり慣れていないが通せてよかった。

Ex問題。とりかかった時点でのAC数があまりにも少なくペナもたくさん積んでいたため絶望。問題文を読むと $2$ 乗和の期待値の話をしていて、期待値への苦手意識もあって厳しい気持ちに。結局分からず。