解けなかった。 発想１．(Xi + Xj + Xk) + (Yi + Yj + Yk) + (Zi + Zj + Zk) を (Xi + Yi + Zi) + (Xj + Yj + Zj) + (Xk + Yk + Zk) とみて考える。 これは添え字が同じになるように移項するのと同じ発想なので思いつくべきだった。 発想２．- (Xi + Xj + Xk…

ずっとほったらかしていた問題。 dfs で全探索するのだけど、愚直に計算すると間に合わない。 • 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。 • 中途半端に解く配点があるなら、それは完全に解く配点以外の配点…

３次元 dp するときに、r,c,k のうち k だけ、計算量が小さいときは、 dp = [[[0]*c for _ in range(r)] for _ in range(k)] と書いた方が実行時間が短くなるという知見を得た。というかこう書かないと TLE するのだがなぜ？ def main(): import sys r,c,k =…

atcoder 再開。水色になった。 01-bfs というやつらしい。+0 を append で、+1 に遷移するものを appendleft でdeque に入れてあげると、O(1) で heap みたいなことができる。heap で回したら TLE した。 よくある bfs や今回初めて書いた 5*5 の移動をメモ…

ほぼこれ。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 ] =…

4完 パフォ1412 でした。最近パフォが1400 くらいで安定している。今はいいけど水色になってからは困るなあ。 コンテスト後に F を通しました。考察はあと一歩だったけど、実装の場合分けは無理でした。まず、Nim の必勝法は A1^A2^...^An = 0 なら 後手が必…

区間dp の問題。区間dp とは、dp[ i ][ i+j ] = list[ i : i+j ] での最大(最小)値として、最大値の遷移を考えるもの。 今回は、dp[ i ][ j ] = ケーキが i+1 番から i+j+1 番まで残っているときの JOI 君の取り分の最大値 として問題を解く。 ケーキが円状…

python だと難易度が爆上がりするやつ。 E - Exclusive OR QueriesCPSCOのsession1のEをPythonで通そうと頑張ってみたけどダメそうということがわかった(はい)(ごめんなさい)— てんぷら (@tempura_cpp) May 12, 2019 本編まで飛ばしていいよ。 やるべき動作…

これの下位互換。 F - Absolute Minima abc 127 F - Absolute Minima (python) - aacord’s memo import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1…

BIT木。初見で解いているときは BIT木を知らなくて TLE を出し続け、諦めて解説読んでナニコレとなった。 BIT木の使いどころは、BIT木を2本持つことで、小さい方から i 番目の値の探索を log(N) を行える点である。値の追加、探索、削除を log(N) でできるの…

NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

タイトルからして dp だと思ったら解説は全探索だった。本質的には dp もメモ化全探索みたいなところあるけど。 w_i の制約が特徴的で max(w_i) - w_1 dp[ i ][ j ][ k ] で i 番目の荷物まで見たときに、j 個の荷物を入れて、 重さが j * w_1 + k となって…

bit dp の問題。ゴールした順に bit を作っていくとうまく dp が作れる。 例えば 1 よりも 2 が早くゴールしているときは、今ゴール済みの人を s で表すと、 s & 1 == 0であれば、まだ１がゴールしていないので s から s | 1 n,m = map(int,input().split())…