問題 解法 解答 問題 https://yukicoder.me/problems/no/915 解法 まず C が 1 であるときはクッキーを増やすことが出来ないので，答えは -1 となる．そうでないときは必ず A 枚まで増やすことが出来る． 操作を逆に考え，A 枚あるクッキーを 0 枚まで減らす…

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

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

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

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

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

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