atcoder.jp 解説読むとめっちゃ簡単ですよね...。 なぜ解けなかったのか...。 こちらの動画のコードを丸パクリさせて頂きました。 他の人のコードを読むのも勉強になります。 youtu.be N = int(input()) N += 1 A = [0] + list(map(int, input().split())) A…

atcoder.jp コンテスト中はコストの計算量の抑え方が分からずにsubmitできませんでした。 公式解説にもあるように生徒hを昇順にソートし、前と後ろからの累積和を予め計算しておけば$O(1)$でコストが計算できます。 累積和系のテクニックの大事さを痛感しま…

文字列に含まれる数字の順番を入れ替えて8の倍数が作れるかどうかを判定する問題です。 atcoder.jp 1000が8の倍数で割り切れるのがポイントです。 1000が8の倍数で割り切れるので当然それより桁の大きい10000も8で割り切れます。 つまり並べ替えた数列の下３…

巡回セールスマン問題(TSP)です。 atcoder.jp $N$が17なのでビットDPを使えば計算量的に間に合うようです。 $S$をビット列の集合として以下のDPを作成します。 DP[S][v]: 訪問済みの集合Sの頂点vからスタートする時の距離の総和 例えば$N=5$の場合、右から順…