1ヶ月続いたけど既にさぼりそうな気配が出てきている。
競プロで冷えただけの週だった。頭の疲労を効率的に取れるようになりたい。任意のコンテストが塾の後にあるのでまともに頭が働かない...
出たコンテスト
CF#596(Div.1) 589位 1938->1866(???)
IOI2014 Day 1 virtual
30+32+100=162
激冷え。最後の1時間でなんとか息を吹き返した感じ。
0:20 1問目の読解が難しかったので、確認のため8点を取る。
0:31 1問目の30点がすぐにわかったので取る。
~1:30くらい 2問目がセグ木ゲーっぽく見えたので考えると、嘘セグ木解法が生えるのでひたすらそれを詰める。
~2:00くらい 2問目がわからなくなったので3問目に行くが、小課題1もわからない。
~3:00くらい 脳が疲れて何も考えていなかった。3問目の誤読に気づく。
~3:30くらい 部屋を歩き回っていると、3問目の方針が分かる。
3:57 3問目の42点が通る。若干バグらせた。
4:08 3問目の満点に取り掛かる前に自明を通しておく。
4:32 N=1200でO(N^3)のつもりで書いていると、実はO(N^2)であることが実装中にわかる。3問目が通る。
4:47 2問目の小課題2は普通にセグ木で解けることがわかったので通す。
難易度は11-10-10みたいな感じに思えた。
1問目 Rail
解けていないし解説も見ていない。
2問目 Wall
解説を見た。合成は無限に考えていたがこの発想はなかった。
実は、ある数への任意のchmin,chmaxの操作列は、chmax(chmin(x,a),b)の形で表せる。これは帰納的に考えると分かる。
具体的には、
chmin(chmax(chmin(x,a),b),c)=chmax(chmin(x,min(a,c)),min(b,c))
chmax(chmax(chmin(x,a),b),c)=chmax(chmin(x,a),max(b,c))
のように合成できる。よって、(a,b)をセグ木の各ノード上で持っておけば、適当な遅延伝播で最終的な答えが求まる。
3問目 Game
「最後の辺が異なる連結成分を繋ぎ、それによってN頂点が全て連結になる」という条件を満たせばよい。
ある辺を繋ぐことによって、最後の辺が同じ連結成分を繋いでしまう可能性が少しでもできたらダメ。
そのためには、(u,v)を繋げる辺を使う条件を、
・u,vは同じ連結成分内にない
・u,vの連結成分を繋げる(u,v)以外の全ての辺を既に見ている
とすればよい。明らかに最後の辺が同じ連結成分内の頂点を結ぶことはなく、これで必ず最終的にはN頂点が連結になる。
これを愚直に実装するとO(N^4)となり、42点が取れる。
C(i,j):連結成分iと連結成分jを結ぶ辺の本数 というテーブルを計算することを考える。これがわかればO(1)で条件判定ができる。
1回の更新でO(N)かかるが、連結成分のマージはO(N)回しかないので、O(N^2)で解けた。
意外と条件が厳しいので、できることが限られる問題。
解いた問題
技術室奥プログラミングコンテスト#2-E 歩くNPCたち
https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_e
ある定数Bを考え、Vi < BとVi >= Bで場合分けする。
・|Vi| < Bのとき
同じ傾きの直線同士の順序は変化しないことに注目すると、「ある傾きの直線の集合についてのクエリ」には二分探索でO(logN)で答えられる。
傾きの種類数はO(B)だから、このようなクエリには全体でO(QBlogN)で答えられる。
・|Vi| >= Bのとき
Rの上限をmaxRとおくと、直線iは、T <= maxR/Viなるクエリでのみ考慮すればよい。
各直線について愚直にクエリに答えたとしても、考慮すべきクエリの数から、全体でO(NmaxR/B)で答えられる。
これで、計算量がO(QBlogN+NmaxR/B)となる。B=100などにすれば間に合う。
CODE FESTIVAL 2018 qual A-D 通勤
https://atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d
「建て替えない集合」の個数を求めればよい。
実は、「補給する場所の組み合わせ数」をベースに考えればよい。なぜなら、補給場所の集合が異なるならば必ず建て替えない集合も異なり、被りが起こらないからである。
dp(i):iで最後に補給することになるようなそこまでの建て替えない集合の組み合わせ数 というDPを考える。
このとき、dp(j)がdp(i)へ寄与する条件は、F-T < Xi-Xj <= F⇔Xi-F <= Xj < Xi+T-F というような区間になり、この前計算は二分探索でO(NlogN)でできる。
また、寄与する値は、Xj+F-T < Xtを満たす最も左のtについて、2^(t-j-1)*dp(j)となる。
これで累積和を用いてO(N)で計算でき、後は答えを適当に求めばよい。最後は区間の右端条件が必要ないことに注意。
これでO(NlogN)で解けた。
