uwiさんから 長さNの、整数列(全部の要素が1 ~ N, 全部の要素はdistinct)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める N = Q = 100,000 TLE2s 重要事項 僕はまだ解法を考えてないです…
長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要素を全部反転させる(0だったら1に, 1だったら0に) N = Q = …
RBSTは万能かつ簡潔な平衡二分木として有名ですね Q.でもこれって計算量どうなんやろ A.なんかいい感じやねんのままだとよくないかなぁと思ってちょっと考えてみました注意点として今回の記事では全部i番目というのは0-indexedです あと、スピリチュアルです…
T: フィボナッチ - Typical DP Contest | AtCoder僕はこれの解法の理解に非常に時間がかかりました。なので他の人もきっと時間がかかるよね？ということでメモを残しますまず数列 について となるが与えられているここでf(n) = {}となる関数f(x)を定義する(…
子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。D: Longest Path - Indeedなう（オープンコンテスト） | AtCoderとかが簡単に解けたりします頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて…
RUPCに参加しました。1日目は立命館セットで、evimaさんとNOxさんと出ましたがーっと時系列で書くとBをevimaさんがコーディング AはNOxさんがコーディング Aが♨️したためDをevimaさんがコーディング 僕とNOxさんでAをデバッグしたら日本語読解に失敗している…
総評 お疲れ様でした。 問題タイトルが全部英語なのはデレマスの影響です 問題解説 C,D,Eの想定解は長いので後ろにまとめます A問題 Trouble Busters (面倒)100なA問題もいいかなって思った。 next_permutationを使うのが多分一番楽です。 一人ぐらい六重ル…
一気に書くのは面倒なのでチマチマ追加していきたい。AA Treeとは平衡二分木の一種で、赤黒木の亜種。赤黒木より実装が楽で速度はあまり変わらないらしい。http://web.eecs.umich.edu/~sugih/courses/eecs281/f11/lectures/12-AAtrees+Treaps.pdf図がわかり…
嘘解法かも。 まず考察する。 とにかく2パターンの使い方ができるIが面倒。 仮に、IOIが爆破されたら(使用できるのがJOIだけだったら)ハジから貪欲にほいほいつくればいい。 なので、文字列中のIを何文字かJに変換し、貪欲に取るという事を考える。 Iの何文…
CF #286のDiv2C/Div1AとDiv2E/Div1Cのwriterをしていました せっかくなのでこの2問について解説を書きます Div2C/Div1A 想定より難しかったようです。ごめんなさい。M=島の数=30001とします。 O(M^2)解 dp[i][j]: 今番号iの島にいて、前回距離jジャンプを行…
競技プログラミングTCのレート2600CFのレート2400正直厳しいけど、1年間での†圧倒的成長†に期待なんらかの(無限人行けるものでは無い)オンサイトに行くなんらかの海外オンサイトに行く一番希望があるのは天下一かなぁ海外はまあリクのルートに期待だよね賞金…
Problem - E - Codeforces 本質は定数倍改善。 7個の行列をそれぞれ行列累乗して掛けるだけ
lcm(2,3,4,5,6) = 60なので60個SegTreeを作れば良い seg[l][r][k] = l~rを通るのにかかる時間、ただしlに突入した時点での時刻%60はk CFはこういうのをTLE2sN=100000で出してくるの怖い
Problem - E - Codeforces RMQでドミノを伸ばせるだけ伸ばして遅延評価SegTree
朝起きる。集合時間まであと30分。朝食が食べられなくて非常に残念。 まぁ間に合うだろと思って電気ポットでお湯を沸かしその間にお風呂に。お風呂を出て紅茶を飲む。飲んでたら電話が鳴る。ちーん(笑)。ガイドの人に遅いと言われた。最悪集合時間電話起きを…
起きる。9:45。朝ご飯を食べ損ねたと思ったが実は10:30までだったらしい(朝食の時間が書かれた紙を紛失していた)、やったぜ。 mathさんと朝ご飯を食べる。やっぱり美味しいなあ。 昼ご飯。また回転皿が同じ物に見える…。メインは北京ダックだった。これは本…
朝起きる。お風呂に入る(2回目)。 適当に部屋でだらだらして朝食を食べにいく。ビックリするほど朝食は美味しかった。ビックリ。 しおりに書かれている時間と本当の集合時間が違うとかいう意味不明な罠によって今何時か知っていますかした この日はコンテス…
1000なだけあって非常に悩んだけど、面白かった。 すべての道は交差しないというのが非常に強い制約。 まずは円環はNGなので切って伸ばして列にする。 これのおかげで区間DPとして考えられる。 また、n % 2 == 1の場合は答え1になる事と(r-l) % 2 == 0となる…
朝5時30分ぐらいに家を出る。数学演習のレポートを出しに大学へ向かう。 無事空港に到着する、遅くも速くもないくらい。 空港で朝飯を買って食べて飛行機に乗る。機内食が非常に美味しかった 上海に着く。ちょっと空気が汚れている気がしたが、殆ど気になら…
Programming Problems and Competitions :: HackerRank 問題は登録しないと見れなかったりするのかな？ 問題概要 N頂点のツリーが与えられる、頂点はそれぞれf(x) = ax+bという形で表せる関数を持っている 二種類のクエリが飛んでくる クエリ1.変更 u, v, a,…
Do use segment treeだけどHL分解は怖いしやり方がよく分からないのでSegment Treeは使わずLink-Cut Treeを使用。 めちゃ雑に書いたけど想像の10倍ぐらい速かった。いつかSplay木のポテンシャル云々を読んでおこう… 平衡二分木の子が左右入れ替わっても値が…
問題を読むと明らかにフローだし辺の張り方が明らかに二部グラフだし… 本当にフロー流すだけ問題。 #include <iostream> #include <cstdio> #include <complex> #include <set> #include <vector> #include <stack> #include <tuple> #include <algorithm> #include <cassert> #include <cstring> #include <queue> using namespace std; typedef long lo</queue></cstring></cassert></algorithm></tuple></stack></vector></set></complex></cstdio></iostream>…
I: Shapes - CODE FESTIVAL 2014 決勝（オープン） | AtCoderこの問題は 平面走査をして木を作る LCA の二つのフェーズに分かれています 平面走査 解説にはBITでごり押しすると書いてありますが、 平衡二分木ライブラリがあれば割とよくあるタイプの木になる…
CPUが200倍の速度だとしたら通る解法を考えます 200倍速くしようとします 出来ない（◞‿◟） CPUが20倍の速度だとしたら通る解法を考えます 20倍速くしようとします 出来ない（◞‿◟） CPUが2倍の速度だとしたら通る解法を考えます 2倍速くしようとします 出来る…
平衡二分木は、定数倍は遅いしコード長がアホみたいに長くなりますがとても強力なデータ構造です。 そんな平衡二分木を使う事が最近多いので、使った問題を紹介します。 木の種類 RBST 軽実装かつコピー可能な(追記:不可能です。)プロコンなら最強感のある木…
ICPCのジャカルタ大会に参加して来ました。コンテストについての記録を残します。来年以降の参加を考えて居る人のためになれば幸いですね。環境OS:Windows, CPUとかメモリはまともPCのスペック:Core i3か5、メモリは4GB？至ってまともコンパイラ:MinGW、コン…
やったことD言語で参加しました最初APIごとにそれを叩いて結果を返す関数を作るとりあえずテストとして色々召喚してみる(SSS石とか使っちゃった)モンスターリストはファイルサイズがでかくて怖いどうせ沢山の種類の石を使って召喚したほうが効率がいいんだろ…
インドネシアに飛ぶので過去問を解いた。10:52 ~ 15:52 AC Penalty 8 1192(932+260) A B C D E F G H I J 11(+3) 299(+6) 43 33 - 79 61(+1) 235(+2) 171(+1) - 2位(Bが通せてなかったら5位)初liveachieveなので 別の問題にsubmitしていた*3 gccだとコンパイ…
スプレー木についてのメモ(1)普通のrotr, rotlを実装する(2) zig->そのまま zigzig->親を回転,自分を回転 zigzag->自分を回転*2 でSplayを実装(3) merge->左の木のMaxをSplay,左の木のRootの右に右の木のRoot split->k番目をSplay,そのまま分ける
CODE FESTIVALに参加してきました。前日 kagamizに会おうと言われたので会う。 神田明神に行ったり竹むらに行ったりkitayutaと合流したりわふれるかと合流したりカレーを食べたりした。 DDRは12のクリアが増えた。半年ぶりにビートおたくしたら四段がギリギ…
