メモ

知らなかったできることのメモとか

1e18+3(codeではll 1LLe18+3)は素数
inv(1e9+7) mod(1<<64) = 13499267949257065399ULL ←これよく考えたら普通にオーバーフローさせながら計算すればよかった
DAGにpathを何個書けば頂点が覆えるか->bipartite matching
和がnになるような1以上の整数達がいる時、種類は√2nくらい (よく考えたら自明だった)
負辺min_cost_flowははじめのポテンシャルだけBellmanFord
木DPでstackoverflow->先にbfsでtopological orderをとる
二人ゲームで手番数が決まっていて相手の手をキャンセルできる手が打てる場合のmin-maxは手番数kとするとk=1,2しか考えなくて良い
挿入,削除ありのk番目の値→setで先頭k個を持つ
Z-algorithmでs[i~]とTのpfx が全部求められる
1文字違い→前からの一致+後ろからの一致=N-1
stack→区間DP
幾何で角度区間のマージ←ベクトルでやると楽かも(ただしもとより180度以上ずれてるとまずそう)
n次関数を足す→差分を取る(BITのあれみたいなのもあるけど,そもそも持つ値を差分にする も有用)
平面上4方向は45度回転で独立なx+y軸,x-y軸になる
数列で大小関係みたいな問題は平面上の点だと思うことが多い そうじゃなくてもdpとかを視覚的に表す方法があるならそれを考えるのもあり(というか図形に落として考えるのが苦手すぎる)(ex.LIS)
tの上限が1e9とかで答えがtの多項式であることがわかってるなら,小さいtについて求めて多項式補間もありうる(数え上げで結構ありそう)(わかんなければ実験も良さそう)
全部がうまく行ってるか みたいなのをクエリごとにはやく判定するためには,何個うまく行っているかを持って更新する 例えば後退解析とかでも,そこに行ける状態の内何個を処理したか を持っておき,それが全部になったらやる、みたいな
DPをデータ構造で高速化するのは貰うDPがいい(範囲のsumやmaxを一気に取りたいんだから).
dp[i]からdp[i+1]への遷移を何も考えずにsegtreeに載せると、区間を意識しなおさなくても連続部分列に対するクエリに応えられる.
連続なものはとりあえず離散的な数え上げ+簡単な積分 に落とす,たとえば∫max(a,min(b,c)) みたいなのはa,b,cの大小関係を決めたものをすべて考える.
こうするとuniform distribution[0,1]からN個独立に取ってきた時のi番目(1-indexed)の値の期待値は? になって、式を描くとベータ関数になることがわかりi/(N+1)になる. (i+1番目)-(i番目) がiによらないので1/(N+1)になることを考えるとわかりやすい.
遷移する順番が関係ないDP→
なんらかの順序でソートすると一部のキーを消せることが多い.あとcount系なら戻せる.
あとこれは最短路問題に落とせて、例えば常にコスト1でbfsになるなら計算量は変わらない.
しかし、「状態を一部に制限しても最短経路が存在する」しかしdpの順としてはこのようなものを実現するうまい順は存在しない,というような状況だと、bfsの方が計算量が良くなる場合がある.
ex:絶対値がK以下の整数がある、何個足せば0にできますか→DPだとO(K^2)状態になるが、bfsだとO(K)状態.

FHC 2018 r2

開始前: ねむい
Sentimental Venus という曲を聞いてウキウキしていた

A: へーこんなの解けるのか
適当にでかくなりそうな例を作る
渡る辺の重みはどんどん小さくなるから実際これがベストっぽい
./a.out < A.in > A.out ってしたらこわれてexpiredしかけたのでこのPCで出るときは注意

B: 読むだけ
Core Dumped して???になった
いろいろ確認してたらexpired
嫌な気持ちになりながら切り替えてCに行く

C: はえーおもしろそう
お絵かきしてみる
_|- みたいなのがあったら切れて、縦横両方向にこれがなければいいのでは?
全く数えられる気がしない
あきらめてとりあえずD読む

D: 普通に問題っぽい
入力が嫌すぎるだろ
ちょっと考えてCに戻る

C:
冷静に考えると2個でいいな
Sの方から見てくと適当なDPになる
書く
バグる
なおす
Bの失敗を鑑みて手元でテストしてからinをダウンロード

D:
図を書いてもよくわからなかったのでとりあえずDPを考える
普通に実家だった
stackで今のoffsetを持っておけば実装が楽(左端はクエリ投げるときだけ変えて、offset変更のときには無視する)
眠かったので微妙にバグらせた
テストせずに(は?)出した

ねむ

例年よりかなり問題の質が良いのでうれしい データ構造ゲーといっても今年のは面倒とかじゃなくて小奇麗な感じ(は?)

B: スタックオーバーフローだったっぽい 最近踏んでないから忘れてた デバッグオプションのGLIBC系のせいで制限超えてしまったっぽい? 外したら大丈夫だった
というか速度の問題もあるしinに対して実行するときはdebugはずそう(提出したあとにやればいい)

MUJIN 2018

開始前: 賞金あるやん!ありがとうございます 海外勢もいないし頑張りたい

A,B:無
C: Bとの落差で少したまげたけどやるだけ
D: 設定が意味不明すぎて混乱したが結局サイクル検出のようなことをやればいい バグるだろうなあと思って書いたらバグらなくてたまげた サイクル検出はライブラリ化してるけど、それの最終状態でvis=1になるやつをcountすればいい(自分用メモ)
E: また迷路かよ… よくあるdijkstra亜種, 辺の長さが今いる時刻によって変わるけど、別にトポロジカル順に見れることに変わりはない
F: 去年のTCO final でみて結構なるほどなって思った 大きさ順でdpしていくと候補が増えていくDPになる
G: 係数a,b,cとしてabc空間を考えると三角錐みたいになる, 同値条件を考えるとa-a' : b-b' : c-c' = A:B:C ただしA,B,CはAp+Bq+Cz=0なるもののうちgcd=1のやつ になるので、同値類を数えたければ(a,b,c) in X かつ (a+A,b+B,c+C) notin X みたいなのを数えれば良くて, 式立てればできる まあ式を写し間違えて死ぬほどバグらせたんですが

H: それになりうる状態のmaskを持ってDP みたいなやつ たまに見る(ex. 去年のTCOのbreakfastみたいな名前の問題)
実際は状態が少ない 系
慣れてないと実装がちょっと混乱する 集合の集合が出てくるし
元のDPを考えると、DPのキーの集合がキーになる

CF #500

大失敗。


記念すべき500回目らしい
出ちゃうか
6問

C読む
うーん
とりあえずAに行く

A:
Aにしてはむずくない?
AGCのyosupo回でみた
mxとmnが同じ側なら幅N最小で違う側なら半分ずつだな

B:
できる限り操作をすると長方形いくつかになる
これを得れば答えもすぐわかりそう
(x,y) と (x,y') に辺を生やせば
冷静に考えると x-y で辺を生やせばいいな
答えは連結成分-1

C:
取るべき値は少ないので現在の値を持ってDP?
ちょっと面倒そう
選ぶやつを固定すると、適切な位置でコストを発生させれば (何個選んだか, 直前選んだか, 2狛江選んだか) でやれるな
TLE
は?
内側でK * 3 の vectorを毎回宣言してたのを外側にしたらTLEが取れた
5000 * 2500 * 3 でこんなに遅いのか・・・

順位絶望だったが順位表見てもD以降全然解かれてなくてたまげる
とりあえずD読む
D:
はえ
とりあえず手でいろいろ試す
連結成分の数は高々2しか減らないことによる下限があるな
(abab,baba) みたいなのならこれを達成できる
2kなら一回使えば↑の王道ルートに乗せれそう?
2k+1 も一回使えばいけそう こっちはこれで最適
逆から考えると場合分けがわかりやすいな

何通りか場合分けして書く
WA
えー
場合分けが足りてないことに気づく
書く
WA
えー
手元で試すとまだ場合分けが足りてないことに気づく
終了

結局a abab みたいなケースは2回ですら無理だったのでまだおかしかったんですね

異常な場合分けによらない解法:
2減らせるなら2減らす, みたいな貪欲を実装すればよかったっぽい?
yosupoのコードはかなり短かった

反省:
実装方針(こいついつも同じ反省してんな(いや今回は行けると思ってしまったのがなあ... 実際もうちょい時間あれば行けたとは思う))


E,F: まだ読んでない

TCO2018 r4

開始前:
かなり体調管理に成功した
3-7-8 ...

easy:
これほんとにround4か?
何回かテストして提出

med:
とても解ける問題に見えない
よく読むとunzipしても高々hoge回と書いてある...
これほんとにround4か?
そっ閉じ

hard:
これほんとにround4か?
とりあえず手で試してみる
常にcyclicな区間になってるな
じゃあ和は行列累乗でできるので区間を求めるのが本質
今N個ものがあってT回やったときにx番目がどこに行くかという関数を作る?
よく考えると逆向きでちょっと変
じゃあT回やったときにN個ものがあるうちのx番目にいくのはどの区間かという関数を作る?
逆向きに展開していくときにいくつをマージしてできたかみたいな情報がいるから変

結局前からシミュレーションで、個数,はじめの物体の区間のはじめの値, 各物体のサイズ , 最後の物体のサイズ をもって頑張ればいけるな
間に合わず

chal:
何もできず
redが3人easy落としててたまげた

反省:
できることはわかるけど実装がわけわからん系は解けてないのと同じなのでちゃんと落ち着いて方針を考える
まあ今回はこれを意識したら一生方針が決まらなかったんですけど
だめやんけ

hard:
謎(Kankuro)
苦行(tourist)
マシなシミュレーション(Um_nik)
謎を思いつくのはかなり難しそう かなり賢い
トーナメント表みたいなものだと思うと、2回戦進出したやつの重みを1/Bにするというのはそこまで不自然ではない気がする 今度からトーナメント表っぽいのはこれを考えよう(ただ再びそれがN個並ぶっていうのが非自明なんだよなあ)

CF #499

開始前:
辛いカレーをお腹いっぱい食べてしまった
6問か

C:
まずCから開く
読めない
読めた

(8)

D:
読めた
マージテクで終わりだな
UnionFindのほうが楽かな
0になるやつの親と1になるやつの親と普通にやるとどっちになるか持てばいいな
ここで実装で何故か混乱する
今頭が働いてないのでやめたほうがいいなとなってAに行く
(35)

A:
読めない
読めた

たしかクソしょうもないバグで時間とかした、こんなのバグるか?
(46)

B:
読めない
読めた

WA on 1 (は?)
よく見るとT回しか回してない
書き直して再提出
WA on 1 (は?)
よく問題文を読むと、-1を出力してはいけなかった(下の方に書いてある intじゃないとhogehogeみたいなのを見て勘違いしていた)
AC
(65)

D:
頭が働いてなさすぎてうつ病
普通にマージテクのほうが楽なので書く
普通にかけた
(83)

E:
順位表見たらメチャクチャな場所にいたので嫌な気持ちになる
F解かれてないしEだな
データ構造じゃん
まずoのやつを含む最小の直方体を考える
それにクエリが入ったらo
xにできるかは?
そいつをoだとおもって追加したときに内部にxがいるか?
3次元点存在クエリになった
z軸をtime sweepすると、2次元で点add,長方形countになる
あらかじめ点がわかってるやつなので、マージソートのやつでいいな
ライブラリにあるので貼る
(113)

順位表見たらhack横行しまくっててこわい
見直して終了

反省:
Dまでで信じられないパフォーマンス出したのはカレー食べ過ぎたせいなのでコンテスト直前に食いすぎない(事前に食べておく)
言い訳がましくて嫌だけど明らかにパフォーマンス落ちるから気をつけないと

F:
どうせいい感じに多項式持ってFFTだろうって感じだけど、まずcutされた頂点数を固定すると割り振り方がクッソ自明になることに気がつく必要がある
これは fv(x) = fa(x)*fb(x)*fc(x)*x + 1 って感じになるんですが
とりあえずline graph ですらこれが解けないとどうしようもないのでそれを考えます
(((1*x+1)*x+1)*x+1 .. みたいな感じになってこれは自明
line graph にちょっと増やしたようなグラフだと各xの部分がなんか一般の多項式になる
(((1*a+1)*b+1)*c+1 ..
abcd + bcd + cd + d + 1
これはcd (ab+b+1) + (d+1) とかなので半分(多項式の次数の和で分けないとだめかも)ずつに分ければできる
で、一般の木の場合にどうするかというとだいたい一緒で、とりあえずHLDします
で、heavy path の部分は (((1*a+1)*b+1)*c+1 .. みたいなformで持っていく
その時light から入ってくるfu(x) は上のようにexplicitに評価する
計算量は、各heavy path の一番上でexplicit に計算するので、
vでexplicitに計算するとき、s = sz[v] とすると O(s log^2 s) でできるので
lightを降りた段数でまとめて数えると全体で O(n log^3 n)
重すぎィ!

これってこの形以外で出るのか?(出ないなら今後出たらこっからコピーしてこよう)
HLDでマージをなんとかするのは普通だけどそもそもline graph で D&C っていうのがちょっと面白かった

AGC026

開始前:
久々の? sugim回
楽しみ

A:
普通だな!
(2)

B:
見た瞬間落ち着きをなくすことを確信したので飛ばす

C:
設定おもしろい
普通にDPはできない
左半分を決めると・・・
右半分も決めて半分全列挙、できた文字列のペアをハッシュにぶち込めばOK
もしかしなくてもハッシュいらなかったね
(15)

D,E,F を眺める Dが数え上げなのでこれからやる

D:
ちょうど2個か
0,2,4だとこの前見た感じで行がflipで全て一緒になる(縦と横のxorとる)みたいな感じ
ちょうど2個だと、縦横の配列のどちらかには二連続で同じものが出てこない という条件
これで長方形だと解けた
ぐにょぐにょしてると?
階段状なら左から見れば順次増やしていける気がする
減らすのが厳しい
冷静に考えると上からだと増えるだけだな
これ実装辛くないか?(区間を列挙してマージとかする必要あるし今2個が連続してるかみたいなのもキーにいる)
まあ行けるな! (30)
とけました (93)
は?

焦って順位表を見るとE,Fともに早い段階で解かれてる
F自分が出てきたので考えようと思ったけど読んだら混乱しそうな雰囲気を感じたのでEに行く

E:
はえーおもしろい こいつ良問しか作れないのか
両方とる/とらない なので、1-Nのsubsetを取る問題
辞書順最大なので貪欲
はじめにb何個置ける?
bの区間→aの区間が完全にdisjointならおける
こういうのをとるときはindexのsubsetは連続したものしか取らなくて良い
これ全部試せるね
そうするとbbbaaaみたいなので区切れて完全に別の問題(後ろで再帰的に解く)に出来る?
よく考えると違って、bbbaaba みたいな感じでまだbが紛れ込むことがある
でもこれは絶対とったほうがいいな
もっと一般になんかb???a ってのをとったら間にあるbは絶対とっていい
始点を固定してこれを繰り返すと・・・?
うまく完全に2箇所に切れた→再帰できる
同様にa???bをとると、あいだのaは絶対とっちゃダメ
これも同様に2箇所に切れる やったぜ。(128)

流石にFは無理そう
B:
落ち着く
解けました(137)

Fの出演料を嘆願する(1pt でももらえるとすごいうれしいので)

おわり

反省: Dで見通しが甘いまま強実装を始めたこと AGCなんだからもうちょい実装軽く出来るはず(どうやるんだろう)