最小流量制限付き最大流
勉強した。
snuke.hatenablog.com
ikatakos.com
難しいしよく理解できてない気がするので考えたことのメモ。
上の記事のS→Tのフロー、s→Tのフロー、S→tのフローをできるだけ流した後のことを考えるとイメージがついた。
この状態で超頂点S,Tを作る逆の処理をするとどのような状態か考えてみる。S,Tを作るとき、u→vの辺を、u→v、S→v、u→Tの3つに分解した。後ろ2つの辺は今ともに最小流量b流れている。（流れていない場合は条件を満たすフローは存在しない）なのでu→vのフローにb加えてS→v、u→Tは消せばいい。こうして最小流量制限付きのグラフに戻すと、全ての辺において最小流量を満たすフローが流れている。各vの流入量=流出量も当然満たしているし、そのために最初流量+α流れている辺もある。
最後のS→s、t→Tに無限辺を張ってフローを流す操作では追加で流せるだけ流して最終的な値を計算している。Sに入る辺はないので、このタイミングで満たした必須辺からフローが減るようなことはない。
こうして得られた値は辺を分解したときに最小流量bを2つに分けたので2回分計算されている。本来の最大流と合わせるために全辺のbの和を引かないといけない。
わからなかったこと。
- 必須辺に全て流れることを確認した後なら（S→Tへの最大流 - 全ての辺の最小流量制限の和）がs→tの本来の最大流になるらしい（蟻本より）。このとき必須辺を満たさないけど、上手くやって本来より大きなフローを流すようなことは何故起こらないのか。
- 他にもあった気がしたけど忘れた。
educational codeforces 159
最近、コドフォに復帰しつつある。
エデュフォはpython のメモリエラーに苦しめられて散々だった。
A:全部1の時以外できる。
B:文章が長い
C:ソートしてan-1-anのgcd、an+1=an-k*gcdでできるだけ大きく取る。
E: トライ木でやるとメモリエラーに。versionをpypy3 64bitからpypy3に帰ると少し改善するがだめ
ロリハでやるとTLEするかmod小さすぎて衝突するかを繰り返す。ロリハでググってきて
ABC331F Palindrome Query
— ネイヴル (@navel_tos) 2023年12月3日
Rolling Hash + 平方分割でギリギリAC！
mod = 2^61-1 のロリハ演算が本当に速い、PythonのO(Q√N)解を通してくれるとは思いませんでしたhttps://t.co/dISv4v4t9y
実装にあたり、keymoonさんの記事を参考にしました
ありがとうございました！https://t.co/QNV1ojL9UG
などのようにするがTLE。
pypy3 64bitに戻してコンテスト後AC
import sys;input=sys.stdin.readline
from collections import defaultdict
D = defaultdict(int)
N, = map(int, input().split())
X = list()
#MOD = 228216557729
MOD = 2**61-1
def mul(a,b): #a*b MOD 2^61-1 を高速に求める
mask30, mask31, MOD = (1<<30)-1, (1<<31)-1, (1<<61)-1
p,d = a>>31, a & mask31 #a = p*mask31+d
q,e = b>>31, b & mask31 #b = q*mask31+e
m = p*e + q*d
x,y = m>>30, m & mask30
ans = p*q*2 + x + (y<<31) + d*e
if 0 <= ans < MOD: return ans
elif MOD <= ans:
r,s = ans>>61, ans & MOD
return r+s if r+s<MOD else r+s-MOD
else: return ans % MOD
r = 27
for _ in range(N):
X.append([ord(c)-97 for c in input().strip()])
R = 0
for x in X:
R += 2*N*len(x)
hsh = 0
kk = 1
for i in range(len(x)):
c = x[i]
hsh += mul((c+1),kk)
hsh %= MOD
kk = mul(kk,r)%MOD
D[hsh] += 1
for x in X:
idx = 1
hsh = 0
kk = 1
for i in range(len(x)-1,-1,-1):
c = x[i]
hsh += mul((c+1),kk)
hsh %= MOD
kk = mul(kk,r)%MOD
R -= 2*D[hsh]
idx += 1
print(R)
Codeforces Round #669 (div2) 参加記録
久々の更新です。Codeforces Round #669 (div2) に参加しました。
A~Cの3完でレートは少し下がりました。Eがギリギリ間に合わなかった（1分遅れ...）のが悔しいです...
A Ahahahahahahahaha
1と0のみからなるリスト（リスト長は偶数）からn/2こ除去してa1-a2+a3...=0にする方法を見つける問題です。（n<103） Aにしては難しく多くの人が時間がかかっていたようです。 1と0の少ない方全部除去すれば大体OK。111000のように同数の時は0の方を消して、1110みたいに1が奇数のこる場合はもう１つ1を消せばOK。
B Big Vova
簡単枠です。a1...anが与えられるので並び替えてb1..bnを作る問題。ただし、ci=gcd(b1,b2..bi)としたときにCが辞書順最大にならないといけない。（n<103）
貪欲にgcdが大きくなるのを選んでいけばです。n2で解けます。（雑）
C Chocolate Bunny
インタラクティブ問題です。 リストP は1..Nを並びかえたもの。クエリは"? i j"の形で聞ける。Pi%Pjの値が帰ってくる。Pを復元する問題。クエリは2*N回可能。
i=1, j=2とi=2, j=1を投げます。それぞれの答えをa, bとします。P1>P2ならb=P2%P1=P2になり、またa=P1%P2<P2です。P1<P2ならその逆です。 なので、a, bのうち大きい方がP1, P2の小さい方と一致します。P1, P2のどちらかは決まるので決まっていない方とP3について同じことをします。 これをPnまで順にやれば完成です。
実装とテストに詰まりました。
D Discrete Centrifugal Jumps
わかりませんでした。終了後、以下を参考にACしました。
ある塔から飛べる次のタワーは4箇所以下になるということです。 AC時には上記コードから少し変えてbfsしました。本質的には同じです。
E Egor in the Republic of Dagestan
問題文がはじめ理解できず苦しみました。考えると結構すぐ（数分くらい？）で解法がわかりました。Dの後ということと読みにくい問題文のせいで回答者が少なかった気がします。
NノードM辺の有向グラフが与えられます。辺には0, 1のラベルが付いています。 各ノードに0, 1のラベルを貼る問題です。 あるノードに0を貼るとそのノードから出るラベル0の辺は通れなくなります。 1の場合も同じです。 上手くノードに0or1を付けてノード1からノードNまでの最短距離を最大化する問題です。
後ろからbfs（有向辺を逆向きとしてみる）して訪れるノードのラベルが決まってなかったらそのリンクを使えないようにノードのラベルを設定すればいいです。訪れたノードのラベルが既に決まっている場合はその道のラベルと一致していないなら無視、一致していればそこから先も探索って感じでOKです。 ちなみに本番ではN=1のときに最短距離無限となってしまうコードを書きWAしました。N>=2にして欲しかった。
WikiExtractor を使って Wikipediaの情報を収集するための備忘録
WikiExtractor
Wikipediaが持つ大規模なテキスト情報を利用すれば様々なサービスやツールを開発できると思われますが、WikiExtractorはWikipediaのテキスト部分だけを抽出することができるツールです。 以下から最新版を入手できます。 github.com
下準備 : Wikipediaをダウンロードする
Wikipediaでは負荷軽減のために直接クロールすることを禁じています。 代わりにミラーサイトからダウンロードできるようになっていて、以下からダウンロードできます。
色々あってよくわかりませんが、私は名前から判断してjawiki-latest-pages-articles.xml.bz2 をダウンロードしました。
実行
基本的には以下のようなコマンドで解析結果が出力されます。
python WikiExtractor.py ./jawiki-latest-pages-articles.xml.bz2 -o 出力先ディレクトリ
解析結果は以下のような形式です。
<doc id="5" url="https://ja.wikipedia.org/wiki?curid=5" title="アンパサンド"> アンパサンド アンパサンド (&、英語名：) とは並立助詞「…と…」を意味する記号である。ラテン語の の合字で、Trebuchet MSフォントでは、と 表示され "et" の合字であることが容易にわかる。ampersa、すなわち "and per se and"、その意味は"and [the symbol which] by itself [is] and"である。 その使用は1世紀に遡ることができ、5世紀中葉から現代に至るまでの変遷がわかる。 Z に続くラテン文字アルファベットの27字目とされた時期もある。 ... </doc> <doc id="10" url="https://ja.wikipedia.org/wiki?curid=10" title="言語"> 言語 ,,,
オプション 一覧
Wikipediaはある程度構造化されたデータなので欲しいデータの種類は色々考えられます。 WikiExtractorではオプションを追加するだけで色々な情報を取得できます。 WikiExtractorのREADMEを見れば何が利用できるかはわかるのですが、一部Wikipediaについての知識不足で戸惑ったので今後使いそうなものを選んで軽く説明を残しておきます。
--links リンクを残す。<a href=...></a>のようにhtmlタグと中身が保存されます。
--sections sectionを残す。 <h3></h3>のようなheddingタグが残ります。
--list listを残す。リストは箇条書きのことです。(https://ja.wikipedia.org/wiki/Help:箇条書き)
--min_text_length 一定値以上のtextサイズの記事のみを処理します。
--filter_disambig_pages
曖昧さ回避のページは解析しません。例えば次のようなページです。(https://ja.wikipedia.org/wiki/109_(曖昧さ回避))
-de gallery,timeline,noinclude
gallery,timeline,noinclude を除去します。
links, sections, lists って？
linksはリンク、sectionは小見出し、listsは箇条書きを表します。
例えばこれらを残すオプションをつけると、wikipedia記事「日本語」の中にあるsection「題述構造」の処理結果は以下のようになります。
Section::::題述構造. また、日本語文では、主述構造とは別に、「題目‐述部」からなる「題述構造」を採ることがきわめて多い。題目とは、話のテーマ（ 主題）を明示するものである（<a href="%E4%B8%89%E4%B8%8A%E7%AB%A0">三上章</a>は「what we are talking about」と説明する） 。よく主語と混同されるが、別概念である。主語は多く「が」によって表され、動作や作用の主体を表すものであるが、題目は多く 「は」によって表され、その文が「これから何について述べるのか」を明らかにするものである。主語に「は」が付いているように 見える文も多いが、それはその文が動作や作用の主体について述べる文、すなわち題目が同時に主語でもある文だからである。その ような文では、題目に「は」が付くことにより結果的に主語に「は」が付く。一方、動作や作用の客体について述べる文、すなわち 題目が同時に目的語でもある文では、題目に「は」が付くことにより結果的に目的語に「は」が付く。たとえば、 BULLET::::- 4. 象は 大きい。 BULLET::::- 5. 象は おりに入れた。 BULLET::::- 6. 象は えさをやった。 BULLET::::- 7. 象は 鼻が長い。
gallery, timeline, noincludeとは？
gelleryについては以下に説明があります。 ja.wikipedia.org
timelineは以下のようなものです。
また、noincludeについては以下に説明があります。 https://ja.wikipedia.org/wiki/Help:テンプレート
いずれも普通の用途では必要がなさそうです。（この部分のテキスト情報だけあっても使いにくくないですか？）
その他のオプション
まだ使ったことがないので詳しくは書けませんが、カテゴリを限定できるfilter_categoryオプションやnamespaceを指定できるnamespacesは使うこともありそうです。 また追記します。
ABC127-F Absolute Minima
二通りの方法で通した。
- 優先度付キュー
- Binary indexed tree + 二分探索
始め思いついたのは2つ目の方法。 これには座標圧縮なども必要になり大変だった。 1つ目の方法は公式pdfを参考にしたもの。
共通して必要な考察
|x-ai| + bi を順に足していって任意のタイミングで最小値と最小を取るxを求める問題。
|x-a1|+|x-a2|+...+|x-ak|+b1+b2+... +bk の 最小値はどう求めたらいいでしょうか。
|x-ai|が正になる項と負になる項の数が同じなら、絶対値記号を外したとき+xと-xの数が同じになるので定数項のみが残る。 aiでソートしておいて、（大きい方半分のaiの和）- （小さい方半分のaiの和）+ sum(bi) を計算すればいい。 （kが奇数の時は中間値のaiを無視して前半のk//2こと後半のk//2このみ見る。）
また最小を取るxは偶数の時はa{k//2} < x < a{k//2 + 1}の任意のxとなり、奇数の時はx = a_{k//2 + 1}となる。(aiはソート済みとして1-indexとする。)
ソートしながらaiをリストに格納していき、k//2番目の要素にアクセスできること、また、その要素までのsumを取ること、ができればこの問題は解ける。
解法1. 優先度付キュー
解説pdf通りに解いた。頭のいい解法だと感じた。
優先度付キューではソートしながら値を格納することが可能だが、最小値しか取得できない。 そこで優先度付キューを２つ用意して小さい方半分を扱うリストと、大きい方半分を扱うリストを用意することで解決できる。 また、普通にやると全体の要素数が偶数の時と奇数の時で場合分けが必要だが、一度に値を2つ更新することでこれも解決できる。 例えば、1, 3, 4と数値を入れた後、2つのリストはこうなる。
[1, 1, 3] [3, 4, 4]
次に２を入れると
[1, 1, 2, 2] [3, 3, 4, 4]
次に5を入れると
[1, 1, 3, 3] [4, 4, 5, 5]
というように境界をずらしながら入れていくと良い。 全体の要素数が奇数の時も、偶数のように扱えるのが頭いいポイントだと思う。
また、合計値を取るのも前回からの差分のみを取れば良いが、これも結構悩んだ。解説pdf参照。
from heapq import * import sys;input=sys.stdin.readline Q, = map(int, input().split()) qs = [] c = 0 for i in range(Q): q = input().split() if len(q) == 1: c += 1 else: a, b = int(q[1]), int(q[2]) qs.append((a, b, c)) c = 0 if c: qs.append((a, b, c)) R = [10**18] L = [10**18] ss = 0 for a, b, c in qs: xs = [] if c: x = heappop(L) for _ in range(c): print(-x, ss) heappush(L, x) x = heappop(R) y = -heappop(L) if x < a: heappush(R, a) heappush(R, a) heappush(L, -x) heappush(L, -y) ss += a-x elif y > a: heappush(L, -a) heappush(L, -a) heappush(R, x) heappush(R, y) ss += y-a else: heappush(L, -a) heappush(R, a) heappush(L, -y) heappush(R, x) ss += b
解法2. Binary indexed tree + 二分探索
とりあえずコードだけ...
class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) def sum(self, i): s = 0 while i > 0: s += self.tree[i] i -= i & -i return s def add(self, i, x): while i <= self.size: self.tree[i] += x i += i & -i def bsearch(mn, mx, func): #func(i)=True を満たす最大のi (mn<=i<mx) idx = (mx + mn)//2 while mx-mn>1: if func(idx): idx, mn = (idx + mx)//2, idx continue idx, mx = (idx + mn)//2, idx return idx import sys;input=sys.stdin.readline Q, = map(int, input().split()) qs = [] c = 0 j = 0 for _ in range(Q): q = input().split() if len(q) == 1: c += 1 else: a, b = int(q[1]), int(q[2]) qs.append((a, b, c, j)) c = 0 j+=1 if c: qs.append((a, b, c, j)) m = j qqs = sorted(qs, key=lambda x:x[0]) qid2i = dict() i2a = dict() for i, (a, b, c, qid) in enumerate(qqs): j2i[qid] = i+1 i2a[i+1] = a m = len(j2i) st = Bit(m) st_sum = Bit(m) asum=bsum=0 for a, b, c, i in qs: if c: j = bsearch(0, m+1, lambda x: st.sum(x)<ci) for _ in range(c): if not i%2: print(i2a[j+1], -2*st_sum.sum(j+1)+asum+bsum) else: print(i2a[j+1], -st_sum.sum(j)+(asum-st_sum.sum(j+1))+bsum) asum += a bsum += b st.add(j2i[i], 1) st_sum.add(j2i[i], a) ci = -(-(i+1)//2)
AtCoder ABC160 参加メモ
全完できて黄色パフォでした！嬉しい！
全方位木をあまり理解していなかったためFが遅くなってしまいましたが、方針自体はすぐたったのでまだ上を目指せそうです。
E Red and Green Apples
貪欲で解けます。 時間がかかった人も割といたようですが早く解けました。 いつもは貪欲に気づくの苦手の部類なんですが... Pの上位A個分、Qの上位B個分を連結しソートします。Rもソートしておいて、max(R) > min(P+Q)だったら入れ替えるのを繰り返して解きました。
F Distributing Integers
全方位木です。以前EDPCで出たのをよくわからず通したままになっていたので復習しないとなあと思っていたのですが、出てしまい困ってしまいました。 atcoder.jp
本番ではEDPCの解説記事を読みながらゆっくり書いてギリギリACできました。
たくさんの方が解説ブログを挙げています。以下を参考にすればよくわかりそうです。
AtCoder Beginner Contest 160 F - Distributing Integers - ARMERIA
AtCoder Beginner Contest 160 解法 - ブログ名
ここではpythonで書いた自分のコードを整理してコメントをつけたのを公開しておきます。 pythonでは再帰がとても重いので非再帰で解いています。
import sys;input=sys.stdin.readline mod = pow(10, 9) + 7 def mul(a, b): return ((a % mod) * (b % mod)) % mod def cmb(n, r): if ( r<0 or r>n ): return 0 r = min(r, n-r) return g1[n] * g2[r] * g2[n-r] % mod g1 = [1, 1] g2 = [1, 1] inverse = [0, 1] for i in range(2, 2*10**5 + 1 ): g1.append( ( g1[-1] * i ) % mod ) inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod ) g2.append( (g2[-1] * inverse[-1]) % mod ) # ここまでライブラリ N, = map(int, input().split()) d = [list() for _ in range(N+1)] for _ in range(N-1): a, b = map(int, input().split()) d[a].append(b) d[b].append(a) # 予めノードをdfs順に保持 vs = set([1]) stack = [1] vs_dfs = list() parents = [0] * (N+1) while stack: v = stack.pop() vs_dfs.append(v) for u in d[v]: if u in vs: continue parents[u] = v vs.add(u) stack.append(u) # 根を1として計算、同時に部分木のサイズも計算しておく dp1 = [0 for _ in range(N+1)] size = [0 for _ in range(N+1)] for v in vs_dfs[::-1]: t = 1 tmp = 0 for u in d[v]: if u == parents[v]: continue t = mul(dp1[u], t) tmp += size[u] t = mul(t, cmb(tmp, size[u])) size[v] = tmp + 1 dp1[v] = t # v=1以外を根にして計算 for v in vs_dfs[1:]: p = parents[v] dp1[v] = mul( mul(dp1[p], size[v]), inverse[N-size[v]] ) for i in range(1, N+1): print(dp1[i])
ABC041-D 徒競走
青diff下位に設定されていて比較的昔のコンテストだったので解けるだろうと思ったが苦戦した。 結局わからず解説AC。典型ということだがこのdiffだと初見でも解けた人が多そう。
公式解説pdfがわかりやすい。 しかし、「vからS−{v}へ向かう有向辺がない」を判定する部分で二重ループを書いてしまった。 これでも通るのだが他人のコードを見ていると、有向グラフ部分もbitで表現することで簡潔に書けていたので、今後使っていきたい。 コメントをつけて書き直した。
N, M = map(int, input().split()) b = [0]*N for _ in range(M): x, y = map(int, input().split()) b[x-1] += 1<<(y-1) # x から yへの辺があるときb[x-1]のy-1 bit目が1になるようにする dp = [0]*(1<<N) dp[0] = 1 jbs = [(j, 1<<j) for j in range(N)] for i in range(1<<N): for j,jb in jbs: if i&jb<1 and i&b[j]<1: # jは1bitだけ1、i&j=0。 jからiに向かう有向辺がない dp[i|jb]+=dp[i] print(dp[-1])
