けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder450点

AtCoder ABC 357 E - Reachability in Functional Graph (1D, 水色, 450 点)

久々! Functional Graph のサイクル検出と DP 問題へのリンク 問題概要 頂点数 の functional graph が与えられる (出次数 1 の有向グラフ)。 このグラフの 2 頂点 からなる順序対 であって、頂点 から頂点 へと至るウォークが存在するものの個数を求めよ (…

AtCoder ABC 354 D - AtCoder Wallpaper (1D, 水色, 450 点)

周期性をうまいこと活用してなんとかする問題! 問題へのリンク 問題概要 座標平面上で下の図のような白黒模様が与えられる (問題文より)。 左下の頂点が 、右上の頂点が であるような長方形領域内部の黒色部分の面積 (の 2 倍) を求めよ。 制約 考えたこと …

AtCoder ABC 325 E - Our clients, please wait a moment (緑色, 450 点)

少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…

AtCoder ABC 325 D - Printing Machine (水色, 450 点)

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

AtCoder ABC 323 E - Playlist (水色, 450 点)

よくある区間分割の DP だけど、それでよいことに思い至るのが難しいかもしれない。 問題へのリンク 問題概要 曲あって、それぞれの曲の長さは である。 今、時刻 0 から開始して「曲を一様ランダムに流し、それが終わったらまた一様ランダムに曲を選択して…

AtCoder ABC 321 E - Complete Binary Tree (青色, 450 点)

この問題をキッカケに準完全二分木のライブラリを拡充した! 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。頂点番号は である。各頂点 (> 2) について、親頂点は である。 この根付き木において、頂点 からの距離が であるような頂点の個数を求…

AtCoder ABC 318 E - Sandwiches (緑色, 450 点)

色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…