人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

yukicoder レベル 2.5 問題

yukicoder:No.817 Coin donation

問題 解法 解答 問題 yukicoder.me 解法 コインの枚数の境目は最大でも 2 * N 個しかできないので,コインの数字を座標圧縮することを考える.そうすると,空間計算量を O(N) に減らせる.各コインの枚数の区間において,その区間に属するもともとのコインの…

yukicoder:No.812 Change of Class

問題 解法 解答 問題 yukicoder.me 解法 まず,各クエリで与えられる頂点を始点としてダイクストラ法を用いて全頂点への最短距離を求める.ここで,到達できる頂点の数が最大の友達の数になる. 次に,各頂点と始点の頂点が何日で友達になるかを調べる.1 日…

yukicoder:No.807 umg tours

問題 解法 解答 問題 yukicoder.me 解法 ツーリストチケットはツアーの中で1回しか使えないので,行きか帰りかのどちらかで使うことになる.なので,頂点 1 から各頂点へツーリストチケットを使って行くときの最小コストと,使わないで行くときの最小コスト…

yukicoder:No.800 四平方定理

問題 解法 解答 問題 yukicoder.me 解法 2つ目の条件式の左辺に x, y, z の 3 文字,右辺に w の 1 文字となっていて全探索するには O(N^3) かかってしまい間に合わない.そこで,この式を変形して,x^2 + y^2 = -z^2 + w^2 + D とすることで左辺・右辺の取…