ABCのD問題が久しぶりに解けなかったので解説しながら理解を深めます． atcoder.jp 問題概要 単純無向グラフG(V, E)が与えられます．u < vを満たす頂点(u, v)の組で次の2つを満たす組の総数を出力してください． 頂点uと頂点vを結ぶ辺は存在しない． Gに辺(u…

問題 atcoder.jp 読み替え グラフを扱う問題です． N個の頂点とN-1本の辺が与えられます．これで作られるグラフは連結*1です． ある頂点uと頂点vの間に辺を1本張ることを考える時，サイクル*2ができる場合があります．このとき．サイクルの長さの最大値を求…

問題 atcoder.jp 学生がN人います．各学生の所属するクラス(1 or 2)と試験の成績が与えられます． 校長先生からQ回，次の質問がくるのでうまく答えたいです． 校長先生「L番目からR番目の学生の期末試験の点数の合計をクラス別で教えてくれ」 解説 制約を見…

問題 atcoder.jp 解説 H × Wの数字がはいったマスが与えられるので，それぞれのマスについてマスと列が等しいか行が等しい全てのマスの数字の総和を出力する問題です． (実際には数字が各マスに入っています) 例えば赤のマスについて調べたいとき，赤のマス…

問題 atcoder.jp 解説 正整数Nが与えられるので，長さがNの正しく整合している括弧列をすべて出力する問題です． ここでの整合とは左括弧と右括弧が正しく対応していることです． OK ( ( ) ( ) ) , ( ( ) ( ( ) ( ) ) ) ( ), NG ( ( ), ( ) ), ) ( ( ) ), 最…

問題 atcoder.jp 解説 L cmのようかんをK+1個に分割するとき，分割したようかんの大きさの最小値をできるだけ大きくする問題です． 図1. ようかんの例(ようかんには見えませんが) 最小値の最大値が求められるような場合，二分探索が有効です． 二分探索を簡…

学習モチベを保つために競プロ典型90問の解説を書きます． 解いたら順次書く感じでやりたいとおもいます． atcoder.jp リスト たのしく二分探索: 競プロ典型 90 問 001 - Yokan Party（★4） - ・ワ・ : 001 - Yokan Party（★4） たのしくbit全探索: 競プロ典…

問題 atcoder.jp 要点 DPに強くなりたい AtCoder Libraryは偉大 すぐに考えついたこと 普通にO(n2)は無理 それぞれの数字に付く+の数と-の数出すと良さそう? 思いつかないので要素全て1で手書き全列挙してパターン探る(DPを頭から外す) 列挙した N = 7まで手…