http://kutimoti.hatenablog.com/entry/2018/11/14/194510 前回です 今回でわかったんですけど,日記なので前回の実装ミスったとか普通にあります p.q.2 とは p.q.2(priority queue 2)も重み付き最大マッチングで高速化に使われるものです.p.q.1を使って実装…

これからこの論文にもとづいて 重み付き最大マッチングをO(EVlogV)で実装するアルゴリズムを書いていきたいと思います.よろしくお願いします. またkutimoti/MaximalWeightedMatching - GitHubでソースコードは見られます. 言語はC++です. p.q.1 とは p.q.1(p…

非再帰SegmentTreeと一緒にはしたくない() 経緯 トイレでなんとなく思いついたデータ構造がうまくいったので好きになっているだけの話です(論文があったというのは内緒で) BIT(BinaryIndexedTree)を知っていますか? このような感じでそれぞれの要素を持ち,[0…

なんやこのテク...っていう気持ちになったので記事を書きます http://community.topcoder.com/stat?c=problem_statement&pm=14929 問題の解説...https://www.topcoder.com/blog/single-round-match-735-editorials/ りんごさんの参考解説動画(ICPCの類似した…

https://beta.atcoder.jp/contests/arc074/tasks/arc074_c 解法 左から色を決めていくとする. すでに塗った部分の色をすべて覚えておくことはできないので、情報量を落とさなければならない. どうしよう? ここで問題の性質である色の種類がxiであるについて…

問題URL : https://beta.atcoder.jp/contests/arc100/tasks/arc100_c 問題 長さ2^Nの整数列A(0-indexed)がある. 1 <= K <= 2^N - 1を満たすすべての整数 K について, 次の値を求める. 0 <= i < j <= 2^N - 1,(i or j) <= K のとき, A_i + A_jの最大値を求め…

http://codeforces.com/problemset/problem/1000/C 問題概要 時間 0,a1,a2,...,aN,M のタイミングで明かりがON,OFFを繰り返す. ここで最大1個,タイミングを増やすことができる. 明かりがついている時間を最大化せよ. 解法 onの区間にXを挿入する a_i-2 [off]…

こんなツイートが bitDPのほうが集めるイメージ強くない？(なんか結局bitの表現に慣れれるかどうかみたいなあれな気がしてきた)— てんぷら (@tempura_pp) June 20, 2018 このときは「わかる」ってなってたんですけど いざ問題を解いてみるとそんなこと無いな…

chokudaiしゃんに投げられたので解きましたー 問題 https://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_d いわゆる構築 解法 常に最高効率で構築するのはとても大変 無駄があったり制約を満たさない解法であっても、必ず成立させられる…

経緯 結構前にclang Adaptaを使ったvscodeの環境構築方法の記事を書きました kutimoti.hatenablog.com が、これ最悪ですね??? ・重い ・エラーチェック遅い ・重い ・VSじゃん() LSPのcqueryを使えばバク速です!!! (Windowserはおとなしくclangdを使いましょ…

なかなかおもしろい問題が出たので、主な考察の流れを書いておこうかなと思います 問題 https://abc099.contest.atcoder.jp/tasks/abc099_c ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかとなっています。 1…

つい最近clangdについて記事を書きました kutimoti.hatenablog.com なんか矛盾してませんか clangd,とっても優秀なのですが ・別ファイルにある定義先に飛べない ・メモリ消費量がエグい(6GB...) などの欠点がありました 実はclangdを導入する前にcqueryを使…

つい最近,vscodeにC++導入の記事を書きました kutimoti.hatenablog.com vscodeのMicrosoftが作ったC++拡張機能にはLanguage Server Protocol(LSP)という技術が使われています qiita.com LSPは他の言語にももちろん対応しています(C#のOmniSharpとか) これが…

絶対既存(調べ方がわからない) なんかよくわからないタイトルになってしまったけど() ちょっとしたテクも書いていこうかなみたいな備忘録 問題 codeforces.com 問題概要 W * Hの大きさの板チョコがあり、格子に沿って切ろうとしている (xi1,yi1)から(xi2,yi2…

ARC038-C 茶碗と豆 -Segment Tree上の二分探索- 才能がないね。悔しい https://beta.atcoder.jp/contests/arc038/tasks/arc038_c 100点解法 grundy数を使い、遷移は i - C[i] ~ i - 1だけ注目すればOK 104点解法 高速化すべきは遷移にO(N)かかる部分である …

ありがとうございます ありがとうございます ありがとうございます 水色から青色になるまでにやったことメインで書きたいと思います 緑後半、水色前半の方に届いたらいいなーという気持ちです 終始適当なテンションなのでご了承下さい 絶望のJOI本選 100点台…

精進してるとやっぱり出てきた区間DP... 避けてきたけど、今回は少しコツをつかもうと思って勉強してみました What's 区間DP? 区間についての動的計画法です。はい。 .... は？ 訳がわからんから取り敢えず問題解いてみよう だるま落としぃ http://judge.u-a…

何するか分かるけど、どうしたらいいのか分からないことが多かったので 書いておく 解法 1.S から各頂点への距離をDijkstraで求める 2.S から各頂点への経路数 各頂点からTへの経路数を求める 3.(全経路の組み合わせ) - (すれ違ってしまう組み合わせ) が答え…

dp解けなくて悲しいね... 解法 要するに、「根をそれぞれの色で塗った時の合計がX_i以下になる」を満たせば 頂点に重みをつけることで満たすことができる じゃあどうやって求めるのか、ということですが... 根をどちらかに塗った時の値は X_iの値(定義から自…

VSCodeにC++の環境を作るのに手こずっている人をいっぱい観測して このままじゃ広がらない(宗教的)と思ったので書いてみました 環境はSurface Pro 2017 , Windows10です VSCodeインストール code.visualstudio.com ここから 一番左を選択 インストーラーがダ…

とあるツイートが流れてきたので勉強してみた 参考になった記事 ACM-ICPC Dinic's Algorithm Dinic法-Algoogle 流れ level graph(Sからの最短距離)をつくる(BFS) このとき必ず、まだflowを流せる辺(許容範囲が0より大きい辺)を選ぶ 2.level graphでのpathを…

すごくいい経験になったと思う これからも使いそうな考え方を書いておく この問題の特徴 まず、目に付くのは 「Kの正の倍数」という制限 僕は、このような「上に無制限」な問題に慣れていなかったのがダメだった思う じゃあどうするの なんとかして、この「K…

何をしても時間がかかりそう... と悩んでいたが解説見てー あーなるほどってなった わかってたこと r - l + 1 > d を満たす区間は必ず１回以上通る それ以外は通らない、または１回だけ通る(つまり分からない) わからなかったこと 倍数の計算量の抑え方 方針…

おおー500点とかびびってたけど 最近の精進が効いてきてるみたいで自力で解けた嬉しい さて方針 吸収していく、というイメージを持ちました 入力例1 2 3 1 4 1 5 9 これを右側と左側で分けてみると [ 3 1 ] 4 1 [ 5 9 ] 左側は大きく、右側は小さくしていく…

途中まで気付けていたのですが 二分探索が分からなかった... 二分探索できない、勉強しなきゃ どこまで気づいていたか ・ナップサック的にギリギリまで詰め込む ・ソートしておく ・不必要以下の大きさのカードは不必要 ・必要以上の大きさのカードは必要 以…

あーこんなに簡単だったのか.... 気づくの苦手すぎるので意識することを書いておく どの問題でも「何が決まればいいのか」を把握しておく 広義昨日のForestも 「辺の数」と「森の形」と「頂点の小さい順」が決まれば 答えが導ける ということだった そういう…

こういう考え方が足りなさ過ぎてつらい 頑張らないとね 精進1 理想な考察の仕方を連ねてみるが(あっている保証がない) 要するに何するんですか (What is this?) 森を木にするための最小コストを調べます 答えはどんな形ですか (Answer?) 森にある木をすべて…

お疲れさまでしたーーーーーー だがしかし大爆死.... 来年頑張るね 次出ようかなとか考えてる人も参考までに プラクティスの日 はい誕生日() 僕は会場に受付終了30分前ぐらいにつきました や歩く pic.twitter.com/e0H2VInI5n— くちもちとくら (@Kutimoti_T) …

結論 自力 6/10 解説 4/10 あーっていう感じです あみだくじ 自力 何も取り除かなかったときの経路を記録しておき 取り除いた時の経路を調べる 散歩 解説 マスを進めるごとにx2ずつ変更の周期が上がることはわかっていたが そこからが無理だった... 認証レベ…

情報オリンピックまであと2週間! まだまだアルゴリズムを覚えれていない気がするのでちょっと整理 情報落ちしていることが多数なので 参考までにお願いします ダイクストラ法 AiとBiを距離Ciで結ぶなんか出てきたら疑っていい //距離記録用のテーブル ll dis…