文化祭でまともに競プロができていなかったので2週まとめて。
AtCoderのレートがいっぱい上がったしHTTFもユース枠で通ったのでよかった。
出たコンテスト
AGC040 90位 2043->2111
HTTF2020予選 73位
第2回全統プロコン予選 102位 2111->2163
解いた問題
ABC144-F Fork in the Road
https://atcoder.jp/contests/abc144/tasks/abc144_f
消す辺を全探索すると間に合わない。Nが小さいので、頂点ごとにそこから出る中でどの辺を消すのが最適かがわかればよい。
Nから逆順に「dp(i):iからNまでの通る辺数の期待値」をO(M)で求める。すると、各頂点ごとに、向かう先のdpの値が最大であるような辺を使えばよいと分かる。dpの遷移を考えると明らか。
これで消す辺の候補がO(N)本になったので、あとは各場合について愚直に計算すればO(NM)で解けた。
CF1246B Power Products
https://codeforces.com/contest/1246/problem/B
なんでコンテスト中に解けなかったんだろう...。
条件は、「ai*ajの素因数の指数が全てkの倍数である」ということに言い換えられる。
各aiについて、「根」を「aiの各素因数の指数をmod kしたものの積」とおくと、ai*ajが条件を満たすようなajの「根」が一意に定まる。よって、各aiについて素因数分解して「根」を求めれば、O(N√maxa)で解けた。
ABC020-D LCM Rush
https://atcoder.jp/contests/abc020/tasks/abc020_d
S(i):gcd(j,K)=i なるjの和(iはKの約数,1<=j<=N) とする。Kの約数の個数をLとおく。
T(i):iの倍数であるようなjの和 とすると、O(L)で全てのTが求まる。
S(i)=T(i)-(iの倍数jについてのS(j)の和) となるので、iを降順に見ていけば、O(L^2)で全てのS(i)を求められる。
lcm(i,K)=i*K/gcd(i,K) から、答えがS(i)*K/i の和だと分かるので、全体でO(√K+L^2)で答えが求まる。
第4回 ドワンゴからの挑戦状 予選-E ニワンゴくんの家探し
https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_e
重心分解をすることを考える。
次のような戦略でできる。
・今の部分木の重心を取り、その子をサイズの大きい順に並べる。
・2つずつ調べ、返ってきた方の部分木に潜る。
・もしなければ重心が答え。
サイズに大きい順に見ているのがミソ。
1回で見つかれば木のサイズが1/2以下になる。
2回で見つかれば木のサイズが1/3以下になる。
3回で見つかれば木のサイズが1/5以下になる。
全部3回必要になるケースで通るか怪しいが、N<=2000なおかげでギリギリ通る。
JSC2019予選-E Card Collector
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e
Ri-Ciグラフを考えると、「全頂点の出次数が1を超えないように向き付けられるような辺集合について、重み和の最大値を求めよ」という問題になる。
実は、各連結成分について「辺数<=頂点数」を満たす時が最適。これは木+1辺、または木となるので、適当に向き付けていけば上の条件を満たすことがわかる。逆に、それ以上辺が増えると条件を満たすことがない。
後は、辺を重みの大きい方から見ていき、加えても条件を満たすなら加える、というクラスカル法のようなことをすればよい。正当性はクラスカル法と同様に示せる。
第二回全国統一プログラミング王決定戦予選-D Shortest Path on a Line
https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d
最終的な最短路を考えた時に、辺の張り方から、「逆行」がないようなものが必ず存在。つまり、DAGとして考えてよい。
dp(i):iまでの最短路の長さ というDPをする。区間を終点でソートして考える。
ある区間［L,R］を見ている時、実はdp(R)のみ更新すればよいことが示せる。
遷移は、dp(R)=min(dp(k)+C)(L<=k < R) となり、これはセグ木でO(logN)ででき、全体でO(NlogN)で解けた。
感想
文化祭休み最高！
