人権なし

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

yukicoder レベル 2.5 問題

yukicoder:No.826 連絡網

問題 解法 解答 問題 yukicoder.me 解法 P = 1 または N / 2 より大きい素数のとき答えは 1.なぜならば,前者は自明で,後者は 2 * P が N を超えてしまうため,1 ~ N の数の中で 2 と P をかけて合成数を作ることが出来ないから. そうでないとき,家 i(i…

yukicoder:No.821 Making Integers

問題 解法 解答 問題 yukicoder.me 解法 操作を行った後の数列 A の和が最も大きくなるのは,1 回も操作を行わないときになる(つまり (1, 2, ... , N)).この和を max ( = N * (N + 1) / 2) とおく.また,操作を行った後の A の和が最も小さくなるのは,A…

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 とすることで左辺・右辺の取…