ほぼこれ。abc 137 E - Coins Respawn (python) - aacord’s memo 頂点１からNまでに通りうる経路だけ抜き出して、その中で bellman-ford を使う。更新回数が m 回をこえたら inf を出力する。 from collections import deque def belman(s,n,w,es): d = [-fl…

連続する部分列→累積和を取る 累積和をとって、差を考える 余りの種類は m 個あるけど、数列の長さから高々 n 個に座圧できる。 基本テクの詰め合わせ。 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.std…

サンプルを使ってワーシャルフロイドした結果が、サンプルと一致していなければ答えは -1 となる。 そうでない場合は存在する道の和を出力しないといけないが、それは i から j に道が引かれているとき == min( d[ i ][ k ] + d[ k ][ j ] ) > d[ i ][ j ] …

場合分けが無限にある。 条件がきつい順に 全部０の場合→０ ５が含まれていない場合→ No 全部５以下の場合→１ min(h, w) > 1 なら 最大値 9 → 4 最大値 8 → 3 最大値 6,7 → 2 となり、 そして上記以外で、h or w = 1 のときは、５の左右の列で最大値ごとに計…

久しぶりに拡張ダイクストラの問題 day2 にも拡張ダイクストラが出ていたりする。 ダイクストラといっても、距離は一切出てこなくて、休憩回数の最小値を求める問題。 heap で (累計の休憩回数、前の隙間、今いる頂点）を保管して、今いる頂点から次の頂点に…

結局、フェルマーの小定理から x = i のとき 1 で、それ以外の時に 0 となるような p-1 次式が作れてしまうというだけの問題。賢い。 あとは a[ i ] = 1 のときに毎回 1 - (x-i)^(p-1) の係数を二項定理で作るだけ。 p = int(input()) a = list(map(int, inp…

一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

結局注目する点は、隣り合う2数を足したときに、繰り上がって桁数が変化しない時は、全体の数の和が9減るということのみ。桁数が減る時は繰り上がりがないため、全体の和は変化しない。 なので求める回数は、全体の和を S, 桁数を T とすると、T-1 + (S-1)//…

stack, dict, set 全部使った。盛りだくさん。 まず、降順ソートしてｋ個選んだ時に、L 種類の寿司が含まれているとき、当然それはL 種類の寿司を選ぶ美味しさの中での最大値となる。同様にして、k > L なら種類が被っている寿司を食べているので、k =L にな…

始点ソートして、L ≦ i ≦ R でd[ i ] = min( d[ i ], d[ L ] + c ) で更新していけば終わり。 答えは d[ n-1 ] で、d[ n-1 ] = INF なら -1 を出力する d[ i ] の一点取得、L ≦ i ≦ R の区間更新なのでセグ木を使えば簡単。 import sys read = sys.stdin.buf…

まず、根になる頂点は、Bには含まれておらず、そのような点 a がただ一つ存在することが分かる。 そして、次に Ai = a となっている辺を全て取り除くと、Bに含まれない点 b が新たに1個以上現れる。その点は、a しか親になりえないので b の親は a とわかる…

dp の巻き戻しするやつ。dfs をして頂点を探索する際に、stack (deque) に次の頂点を入れる前に、dp を変更する前の要素を入れておくことで、dfs順に頂点を探索するときに、行き止まりについてから、一つ前の頂点に戻る時にその時点での dp を再現することが…

約数系の包除原理の問題として解いたけど、どう帰着するのかわからなかった。 まず lcm ではなくて最大公約数 gcd で考える。 lcm( i,k ) = i*k//gcd( i,k ) で求まる。 すると、1 ≦ i ≦ n, k なので、k の約数の集合を g とすると、g = gcd( i,k ) になる i…

172 4完 パフォ1421 173 4完 パフォ1319 まあ失敗ではないけど大成功でもない感じ。次で水色なりたいね。 172は包除原理の一般法則を知らなかったのが原因。Fは難しかった。 #172 E import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.re…

頂点１を根として、dfs をしていき、それまでの xor 和を defaultdict (D) で管理して、現在のxor和 = X^a を満たす a が今までの xor和に含まれていればいいので、dfs 順に D [ 現在のxor和^X ] を足していけばいい。根からの xor和がちょうど X になるとき…

解法１ dp[ i ][ j ][ k ] : i 行 j 列まで見たときに差が k になれるかどうか、なれるなら１、なれないのなら０を記録する。遷移は c = abs(a[ i ][ j ] - b[ i ][ j ]) として (dp[i+1][ j ][k+c] = 1, dp[i+1][ j ][abs(k-c)] = 1 if dp[ i ][ j ][ k ] =…